# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="Ghost Post"]As with the solution to the first edition of this problem, we can see that there is no path or asteroid configuration that will allow us to pass through each door only once. Using some graph theory, construct a graph representing this shed in the following way: Each room is a vertex (label it using the room's name) and let's add a vertex for "outside labeled "O". Add an edge for each door, the edge connects whichever vertices that the door allow passage between. Note that this graph is connected and that the vertices O, C, and E are of odd degree. The solution we are looking for is whether this graph has a Eulerian trail. A Eulerian Trail is a walk on the edges of a graph which uses each edge (door) exactly once. A Connected Graph has an Eulerian trail Iff it has at most two Vertices of Odd Degree. Therefore there is no Eulerian Trai in the orignal configuration. Topology changes the graph (basically, in anyway we want). Keep in mind all vetices connect to O because they have exterior doors (that lead outside) but we can now create topolgies that allow us to make rooms E & C adjacent (or any room for that matter), so these now become even vertices. [/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Ghost Post
Posted: Mon Feb 12, 2001 8:56 pm    Post subject: 1

As with the solution to the first edition of this problem, we can see that there is no path or asteroid configuration that will allow us to pass through each door only once. Using some graph theory, construct a graph representing this shed in the following way:

Each room is a vertex (label it using the room's name) and let's add a vertex for "outside labeled "O".
Add an edge for each door, the edge connects whichever vertices that the door allow passage between.

Note that this graph is connected and that the vertices O, C, and E are of odd degree.

The solution we are looking for is whether this graph has a Eulerian trail. A Eulerian Trail is a walk on the edges of a graph which uses each edge (door) exactly once. A Connected Graph has an Eulerian trail Iff it has at most two Vertices of Odd Degree.

Therefore there is no Eulerian Trai in the orignal configuration.

Topology changes the graph (basically, in anyway we want). Keep in mind all vetices connect to O because they have exterior doors (that lead outside) but we can now create topolgies that allow us to make rooms E & C adjacent (or any room for that matter), so these now become even vertices.