Wednesday, October 10, 2012

How to construct a Eulerian Tour graph


1. Randomly pick 2 nodes and connect them
2. Randomly pick a disconnected node and connect it with one of the connected node
3. Repeat step 2 util all the nodes are connected
4. Highlight the nodes that has odd degree
5. Find any node that has odd degree and connect it with another node with odd degree
6. Repeat step 5 until all nodes are having add degree

Trick:
If there odd degree node that are already connected another odd degree node. We can connect it with a even degree node, and from that we can connect the newly odd degree node with other odd degree node.

See demonstration from this video: