Discrete Mathematics

Erich Prisner

UMUC SG

Spring 2002

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 *G _{1}*,
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

c) The second graph is called
*G _{2}*. It has the same vertex set as
called

d) Does *G _{1}* have a Hamiltonian cycle?
Why or why not?

e) Does *G _{2}* 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 *G _{1}* 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.Go back to Project # 4.

Projects differ in certain ways from homework. They questions there are more complex, more difficult, have several steps, and sometimes you have to use notions and tools from several chapters to solve them. But in most cases, the theorems and tools learned do not suffice to solve all parts of the project. Rather you have to discover certain facts by yourself. Learning how to make "discoveries" in the field is an important part of the class---in real life you donīt have always a textbook telling you exactly what to do. Of course you are encouraged to use any other material---books, webpages, and so on.