Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

graph
graph theory
general

How to detect an Euler path

Muhammad Shmoon

Overview

We can define an Euler or Eulerian path as one that covers all the graph Edges without repetition. An Eulerian Path is one of the essential concepts in Graph Theory.

Background

The term Euler path was coined by Leonhard Euler in 1736. He was working on the famous Seven Bridges of Königsberg problem. Consider that there’re sever bridges connecting four islands. The issue presents when a person wants to visit all the bridges without visiting the same bridge twice.

Seven Bridges of Königsberg Problem

We use an Eulerian path to solve real-world problems. It helps design the path for patrolling the streets of a city or planning for delivering mail or route planning. The modern application can also be found in bioinformatics in finding the DNA Fragments Assembly.

An Eulerian path, generally known as the Eulerian Theorem, can be found in a graph if one of the following conditions is satisfied.

Condition 1

If the graph has not more than two odd-degree Odd degree vertices are those vertices that have an odd number of edges connecting them. vertices, then the graph has an Euler path. The following example can elaborate on this condition.

Example

Graph X
Graph Y

Explanation

  1. In Graph X, four odd-degree vertices (A, E, B, D) are greater than two. So it doesn't have an Eulerian path.
  2. In Graph Y, only two vertices (E, D) are less than 2. So this graph has an Eulerian path. In E D C B F A B D. This covers all the edges without repetition.

Condition 2

A connected directed graph is Eulerian if and only if each of its vertices is balanced. A vertex is balanced if its indegreeThe number of incoming edges is called indegree is equal to its outdegreethe number of outgoing edges is called outdegree.. This results in the formation of the Eulerian CircuitIf starting node and ending node of the eulerian path is same then path is known as Eulerian Circuit . The following example can further elaborate on this condition.

Example

Graph X
Graph Y

Explanation

  1. In Graph X, the D vertex is not balanced as indegree isn't equal to the outdegree. So it doesn't have an Eulerian path.
  2. In Graph Y, the path formed from D C D E A B F A D is an Eulerian path, and all vertices are balanced. The starting and ending node is D. So, this Eulerian path is also known as the Eulerian circuit.

RELATED TAGS

graph
graph theory
general
RELATED COURSES

View all Courses

Keep Exploring