Posted by buh on August 01, 2001 at 16:09:21:
In Reply to: Re: Eularian Trails posted by kalpol on July 31, 2001 at 20:10:27:
yeah.... but i thought that he said there was ONE way to solve it.
: : has anyone solved the eularian trail problem he posted on monday???
: : he said there was ONE answer.. that required a trick...
: it's spelled Eulerian, after Johannes Euler (not your fault, he wrote it wrong on the board.)
: basically it goes(i think, if i'm wrong correct me):
: An Euler cycle exists if every node in an undirected graph is of even degree (has an even number of edges incident on it).
: So for the Seven Bridges of Konigsberg (which isn't in Russia), you can divide the town up into nodes, and call the bridges edges connecting them, and prove there is no Euler cycle, i.e., no way to cross all the bridges without crossing one twice.
: If you guys haven't had CS336 yet, take Misra, he rocks.