6.2. The exhibition design problem.

Another problem from the practice: How shall we plan the corridors of an exhibition?

If the entrance and the exit are the same, a visitor can walk along every corridor once iff the corresponding graph has an Eulerian circuit.

In a well-planed exhibition a visitor avoids going along the same corridor twice and continues his walk until there were no new not-visited corridor ahead of him. He chooses his way randomly. If it is possible to to walk along an Eulerian circuit then we call the correspoding graph randomly Eulerian. In this case the graph G is randomly Eulerian from a vertex v if any maximal trail starting at v is an Euler circuit.

 

 

 Figure 6.2. A randomly Eulerian graph from the vertex v.