In graph theory there is a famous problem known as konigsberg bridge problem. In this problem the main theme was to cross the seven bridges exactly once to visit various cities.
Euler Circuits
In graph
theory there is a famous problem known as konigsberg bridge problem. In this
problem the main theme was to cross the seven bridges exactly once to visit
various cities. The Swiss mathematician Leonhard Euler solved this problem in
1736. From this problem, the concept of Euler circuit is developed. Let us
define the terminologies Euler path and Euler circuit.
Euler path A path in a graph G is
called Euler path if it includes every edge exactly once and every vertex gets
visited. Euler circuit on graph G is an Euler path that visits each vertex of
graph G and uses every edge of G.
For example
The
Euler circuit is A - B – E – A – D – B – C – E – D - C - A.
Ex. 5.12.1 Find an Euler path or an Euler circuit using DFS for the following graph.
Euler
circuit is a circuit that uses every edge of graph exactly once. It starts and
ends at the same vertex.
Review Questions
1. Give a short note on euler
circuits.
2. Explain euler circuit with an
example.
Data Structure: Unit IV : Multiway Search Trees and Graphs : Tag: : Euler path, Operations | Graphs | Data Structure - Euler Circuits
Data Structure
CS3301 3rd Semester CSE Dept | 2021 Regulation | 3rd Semester CSE Dept 2021 Regulation