This blogs teaches the steps for how to check whether a directed graph is eulerian. A graph is called Eulerian if it contains Euler Cycle o Euler circuit. If graph contains only Euler Path then it is called semi Eulerian. An Euler cycle is a path in the graph which starts and ends at the same vertex. for more details follow the link Euler Cycles and Paths in Graph.

How to check whether a directed graph is eulerian

How to check whether a directed graph is eulerian

Condition for directed graph

A directed graph has an eulerian cycle if following conditions are true. (Source: Wiki)

  1. All vertices with nonzero degree belong to a single strongly connected component.
  2. In degree and out degree of every vertex is same.

A directed graph has an eulerian Path if following conditions are true. (Source: Wiki)

  • All vertices with nonzero degree belong to a single strongly connected component.
  • A directed graph has an Eulerian path if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree.

Ref:

http://mathworld.wolfram.com/EulerianGraph.html




Related Contents to follow