CMIS 160
Discrete Mathematics
Erich Prisner
UMUC SG
Spring 2002

Project #6

This project is due on Thursday, May 3 (firm deadline).

1. Moving Animals

The zoo director's face was green with anger. The new animal guard had put some of the wild animals in the wrong cages. "Bring them back in the right cages" ordered the director, "but take care that at no time two animals are in the same cage." (see: "99 Logeleien von Zweistein", Hamburg 1968)

Note that between adjacent cages there are doors. You can move the animals by going with the mouse over a full cage (thereby catching the animal) and moving it to an adjacent free cage (dragging it to the new cage). Note also that moving a tiger takes usually 10 minutes, whereas moving a fox takes only 1 minute. The number of steps and minutes used so far can be seen below the picture. To the right is the desired final configuration.

If you like this kind of game, try also a related one where you can even automatically find best solutions to move animals.
AIM

Minutes so far: Steps so far: Reset:

a) How many ways are there to distribute the animals on the cages? Note that the two tigers, as well as the three foxes are indistinguishable.

b) Now consider the (huge) graph who has all these configurations in (a) as vertices. Twi such configurations are adjacent in the graph if one can be derived from the other in one move. Why do we get an undirected graph in this way?

c) What is the degree (in this graph in (b)) of the initial configuration (which only shows after reloading, make sure to print this configuration since it changes whenever you move the mouse over the picture)

d) What is the maximum degree of the graph in (b)?

e) What is the shortest cycle in the graph obtained in (b)?

f) Use Breadth First Search to find all configurations (vertices of the graph in (b)) that have distance 2 to the vertex of the initial configuration.

g) In how many steps can you transform the initial configuration into the final configuration shown to the right?

h) What is the shortest time needed (remember: 10 minutes for each tiger move, 1 minute for each fox move) to transform the initial configuration into the final configuration shown to the right? If you cannot show that your method is optimal, list it to me anyway for partial credit.

i) Show that the diameter of the graph in (b) is larger than 4!

2. Interconnection Networks

It is often desirable to have a graph with small diameter, where each vertex also has small degree, but where the number of vertices is still large.

a) Find a large (12 vertices or more) graph with diameter 3 where each vertex has degree at most 3.

b) (Challenge, Extra Credit) Show (convince me) that there is no graph of diameter 3 with 54 vertices where each vertex has degree smaller or equal than 4.

Go back to Project # 5.

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.