CMIS 160
Discrete Mathematics

Erich Prisner
Spring 2002

Project #5

This project is due on Thursday, April 19 (firm deadline).

1. The travelling security guard

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?

2. More Liers

In New Wafabia there are three kind of people. Honest people who will never lie, and (chronical) liers, who will never say a true sentence, and also occasional liers who may lie or say the truth. Let's listen to some conversation on the market place.
Anthony : Robin 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.
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?

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.