Graph Theory - The Mouse problem

182 Views Asked by At

Edward the mouse has just finished his brand new house. The floor plan is shown below:

enter image description here

  1. Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.

  2. Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.

  3. After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

If I get it right, this problem is about Euler paths, is it ? Can I look at every door way as an edge, and each room as a vertex of a graph ? Is it correct to say that since there are more than 2 rooms with an odd number of door ways, such a path is not available ? How do you solve (2) and (3) ?

1

There are 1 best solutions below

1
On

If I get it right, this problem is about Euler paths, is it?

Question (1) is about Eulerian paths, yes. Question (2) is essentially about Hamiltonian paths, and question (3) is about one of the most immediate combinatorial [bijective] results in graph theory.

Can I look at every door way as an edge, and each room as a vertex of a graph?

Yes. This would be the most appropriate way to associate an abstract graph with the floor plan.

Is it correct to say that since there are more than 2 rooms with an odd number of door ways, such a path is not available?

Such an argument would be correct if it were sound. In your case, the degrees of the vertices in the graph are $4,4,3,3,2,2,2$, which in particular only has two odd numbers, so the assertion there are more than 2 rooms with an odd number of doorways is incorrect.

How do you solve (2) and (3)?

For (2) I'd just start drawing such paths. Many of the rooms only have two doorways, so that part of the path is already fixed. The rest should yield to a few attempts.

For (3), there are two questions:

  1. How many rooms are there?
  2. What do you know about the sum of the degrees of all the vertices in a graph?