CMSC 250 Quiz #13 KEY Monday, Dec. 3, 2001

Write all answers legibly in the space provided. The number of points possible for each question is indicated in square brackets - the total number of points on the quiz is 30, and you will have exactly 15 minutes to complete this quiz. You may not use calculators, textbooks or any other aids during this quiz.
  1. [15 pnts.] Assume the following two sets represent (non-directed) graphs $G$ and $H$. Determine if these graphs are isomorphic. If they are, give the functions that map the vertices and the edges. If they are not, tell the isomorphic invariant they do not share.

    \begin{displaymath} G = \{\{1,2\},\{1,5\},\{2,3\},\{3,4\},\{2,5\}\} \end{displaymath}


    \begin{displaymath} H = \{\{a,b\},\{b,e\},\{e,c\},\{a,e\},\{b,d\}\} \end{displaymath}

    ANSWERS:
    Not Isomorphic [7 points]
    Reason [8 points]:
    One has two verticies of degree three, the other does none
    or One has two verticies of degree one, the other has one
    or Something similar
    NOTE: they do have the same number of verticies and same number of edges

    GRADING: 7 points all or nothing
    8 points - completely correct explanation
    --- take off 4 if you can't quite figure out their reason, but it seems to be on the right track --- take off all 8 if the reason is either not true or you can't understand it
  2. [15 pnts.] In the graph below, determine whether the following walks are paths, simple paths, closed walks, circuits, simple circuits or just walks. The vertices are named by letters of the alphabet and the edges by single digit numbers. If you are not sure of the name, you can get partial credit for writing the properties that are important in determining the name. \includegraphics [height=2in]{quiz13.eps}
    1. path a1e4b8b7c
    2. simple circuit a3c7b2a
    3. path d5b8b7c3a1e
    4. circuit b4e1a2b7c6d5b
    5. circuit a1e4b5d6c7b2a
    GRADING:
    3 points each for correct word up to 2 points each if correct characteristics pointed out, but didn't know the word

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.1 release (March 30, 1999)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -show_section_numbers -split 0 -no_navigation -no_footnode quiz13ans.tex

The translation was initiated by Deep Saraf on 2001-12-12

Deep Saraf
2001-12-12