Posted by kalpol on July 31, 2001 at 20:10:27:
In Reply to: Eularian Trails posted by buh? on July 31, 2001 at 15:49:47:
: 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.