Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

eulerian

What are the Eulerian path and circuit in a graph?

abhilash

Eulerian path

An Eulerian path is a path that traverses every edge only once in a graph. Being a path, it does not have to return to the starting vertex.

Let’s look at the below graph.

%0 X X Y Y X--Y Z Z X--Z Y--Z O O Y--O Z--O

There are multiple Eulerian paths in the above graph. One such Eulerian path is ZXYOZY.

g Z Z X X Z->X 1 Y Y Z->Y 5 X->Y 2 O O Y->O 3 O->Z 4

Eulerian circuit

An Eulerian circuit is a circuit that traverses every edge only once in a graph. Being a circuit, the starting and ending node of the traversal should be the same.

Let’s look at the below graph.

g B B C C B--C D D B--D E E B--E C--D A A A--B A--D E--D

There are multiple Eulerian circuits in the above graph. One such Eulerian circuit is BCDBEDAB.

g B B C C B->C 1 E E B->E 4 D D C->D 2 D->B 3 A A D->A 6 E->D 5 A->B 7

RELATED TAGS

eulerian
RELATED COURSES

View all Courses

Keep Exploring