Eulerian From Non Eulerian Graphs

Any network containing odd nodes is non – Eulerian. This means every arc cannot be traced just once, returning to the starting point and returning to the start point. Such a route, from a point traversing every arc once and returning to the start point, is called an Eulerian path.

A network containing odd arcs is non – Eulerian because each node must be entered and exited from separate arcs, so that the number of arcs connected to a node is twice the number of exits or entrances to that arc in traversing the network.

If a network is non Eulerian, we can modify it so that it becomes Eulerian by simply replicating each arc. Each node then becomes even and the network becomes Eulerian.

An attempt to construct an Eulerian path for the network on the left may start DCABCD. The path AD has not been traversed, and if it is there is no way to return to D without travelling over at least one path at least one, since every path has been traversed.

The network on the right has Eulerian path DCABCABCDAD.

Add comment

Security code