Graph, Eulerian Path, Eulerian Tour

Algorithms areGraph just how we organize computations to solve a particular problem. Some algorithms are really straightforward, but other algorithms take advantage of subtle mathematical properties to quickly and accurately provide an answer.

A set of circles and lines connecting between them is graph.

Eulerian Path – the path that starts off with some node on the graph, and it moves along the edges from node to node, hitting every edge exactly once, and then ending it from node to the graph.
Eulerian Path
Fig 1 – Nodes A/D has a degree of 3, the beginning and ending nodes, the path moves through them and comes up the other side, it either leaves in the beginning or enters at the end without a corresponding other side.

Nodes B/C has a degree of 2, which were not either at the beginning or ending of the Eulerian path, that is even degree because the path has to go in one edge and out another edge.

Every time that node gets passed through, 2 of the edges are visited, and none of them are visited twice and none of them are skipped.

Eulerian Tour – graph is Eulerian path, all of the nodes in the graph are even degree.

Fig 3- E-C-B-D-C-A-B-E, So it looks like we were able to hit all of the edges exactly once.
It is Eulerian path, but started and ended at the same node (E), that node should have even degree, because each time we go into we come out, except for the first time where we go out but then the last time we come back in. Example, start from home, go around, and come back to home.

Fig 2 – All the nodes have odd degree. Try to make an Eulerian path, finally hit a dead end, every part of the path has to come into the node and out of it.

Example,  An eulerian path starting with J will end at what node? M

2T-3M-2S
|     |    |
2H-3J-2C
Every node in the network needs to have even degree, except for the starting and ending nodes, which are odd. In this example, j starting with 3 nodes, ending node m is 3 nodes except all are even.

How many Eulerian paths does the graph has starting from J 6 path?

J C S M T H J M
J C S M J H T M
J M S C J H T M
J M T H J C S M
J H T M S C J M
J H T M J C S M

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: