a) A security guard has to go through all rooms of the building (shown to the right) each hour. The question is: Can he make a tour where he visits each room exactly once and ends in the same room (his base) where he starts?
b) Two graphs are associated with this problem. The first, called G1, has the set of all rooms as vertices, and an edge between two rooms if it is possible to go from one room directly to the other. Draw G1.
c) The second graph is called G2. It has the same vertex set as called G1, but now two vertices are adjacent if the two rooms have some common wall. Draw G2.
d) Does G1 have a Hamiltonian cycle? Why or why not?
e) Does G2 have a Hamiltonian cycle? Why or why not?
f) Answer question (a).
g) If such a tour is impossible, could the guard solve his problem by making some additional doors between rooms? If, how many additional doors does he have to create?
|h) Answer questions (a) - (f) for the floorplan shown to the right.|
|i) Answer questions (a) - (f) for the floorplan shown to the right.|
j) Can you generalize your findings in (h) and (i)? If a graph has k vertices such that ............................, then the original graph doesnīt have a Hamiltonian cycle.
k) (Challenge, Extra Credit) Could the following graph be the G1 graph of some floorplan of a one story building? Why or why not?
Anthony : Robin is honest.As you see, the people in this country are much nicer to each other. We have the additional information that out of the 13 people, exactly 7 are honest, only one is a chronical lier, and 5 are occasional liers. The question is: Who is honest?
Bette : Helen is honest.
Robin : Liza is honest.
Diane : Robin is honest.
Elizabeth : Bette is honest.
Tom : Geraldine is honest.
Geraldine : Meryl is honest.
Helen : Meryl is honest.
Ingrid : Robin is honest.
Jodie : Ingrid is honest.
Elizabeth : Tom is honest.
Katharine : Elizabeth is honest.
Liza : Diane is honest.
Meryl : Bette is honest.
Bette : Geraldine is honest.
Elizabeth : Anthony is honest.
Anthony : Jodie is honest.
Jodie : Katharine is honest.
Tom : Katharine is honest.
a) We define a relation R on the set of those 13 people by (X,Y) R if X says that Y is honest. Draw the directed graph G of the relation R.
b) We define a second relation S on the set of those 13 people by (X,Y) S if there is some X-Y path and also some Y-X path in the directed graph G of R. Both paths are allowed to have length 0. Show that this is an equivalence equation, and find the equivalence classes.
c) Who is honest?Go to Project # 6.