1
Chapter four : Eulerian / Hamiltonian
Paths and Circuits in a Graph
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
2
Vertex: Land
Edge: Bridge
Question: Is it possible to walk through
the city that would cross each bridge
once and only once?
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
A path in a graph G is called an Euler path if it includes every edge exactly once.
An Euler circuit is an Euler path that is a circuit.
About Leonhard Euler:
3
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
4
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
5
E
B
D
A
C
An Euler Path: E, D, B, A, C
1
2
5
4
3
An Euler circuit: 5, 3, 2, 1, 3, 4, 5
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
6
E
B
D
A
C
2
1
3
5
6
4
Q: An Euler Circuit?
Q: An Euler Path?
A: No
A: No
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
7
Q: Is it possible to begin in a room or outside and take a walk that goes
through each door exactly once?
Vertex: Room or Outside
Edge: door
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Theorem 1 (Euler circuit) &
Theorem 2 (Euler path)
Fleury’s algorithm
8
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
(a) If a graph G has a vertex of odd degree, there can be no Euler circuit in G
9
E
B
D
A
C
V of odd degree
…
1
2
3
2n
2n+1
Begin at v
V of odd degree
…
1
2
3
2n
2n+1
End at v
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
(b) If G is a connected graph and every vertex has even degree, then there is an Euler circuit in G.
The Strategy of this proof (b) :
Support there is a largest (smallest) object and construct a larger (smaller) object of the same type thereby creating a contradiction.
10
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Induction Step : |V|=1,2…k is true 🡺 |V|=k+1 is true
Since vs has even degree and п0 uses only one edge that has vs as a vertex, there must be an edge e not in п0 that also has vs as a vertex.
If the other vertex of e is not in п0, then we can construct a simple path longer than п0 (why?), which is a contradiction. Thus e has some vi as its other vertex, and therefore we have a simple circuit vi vi+1, … vs, vi in G.
11
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Assuming there is no Euler circuit in G, then п cannot contain all edges of G (why?).
Let G1 be the graph formed from G by deleting all edges in п (but no vertices). Since п is a circuit, deleting its edges will reduce the degree of every vertex by 0 or 2, so G1 is also a graph with all vertices of even degree. Choose any connected component in G1 and call this graph G2 (G2 may be G1).
Then G2 has also a circuit п’ (why?).
12
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
case #1: if п and п’ have vertices in common, e.g. v’, then we can construct a circuit in G that is longer than п by combing п and п’ at v’ (contradiction!)
Case #2: If there is no common vertex in п and п’. Then |VG2| < |VG|, then G2 has a Euler Circuit (why? ) , then G becomes not connected (why?) , which is a contradiction.
Therefore, the assumption is wrong, namely, G has an Euler circuit.
13
п
П’
v’
case #1
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
(a) If a graph G has more than two vertices of odd degree, then there can be no Euler path in G.
Proof: Let v1, v2, v3 be vertices of odd degree. Any possible Euler path must leave (or arrive at) each of v1, v2, v3 with no way to return (or leave) since each of these vertices has odd degree. One vertex of these three vertices may be the beginning of the Euler path and another the end, but this leaves the third vertex at one end of an untraveled edge. Thus there is no Euler path.
14
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
(b) If G is connected and has exactly two vertices of odd degree, there is an Euler path in G. Any Euler path in G must begin at one vertex of odd degree and end at the other.
Proof: Let u and v be the two vertices of odd degree. Adding the edge {u, v} to G produces a connected graph G’ all of whose vertices have even degree. By Theorem 1(b), there is an Euler circuit п’ in G’. Omitting {u, v} from п’ produces an Euler path that begins at u (or v) and ends at v (or u).
15
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
16
Each of the four vertices has degree 3. No Euler path
and Euler circuit.
There has exactly two vertices of odd degree. There is no
Euler circuit, but there must be an Euler path.
Every vertex has even degree, thus the graph must have an Euler circuit.
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
An edge is a bridge in a connected graph G if deleting it would create a disconnected graph.
17
A
B
E
C
D
p
q
r
s
t
u
r is a bridge
s is a bridge
t is a bridge
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Let G={V,E,γ} be a connected graph with each vertex of even degree.
Step 1 Select an edge e1 that is not a bridge in G. Let its vertices be v1, v2. Let п be specified by Vп: v1, v2 and Eп: e1. Remove e1 from E and let G1 be the resulting subgraph of G.
Step 2 Suppose that Vп: v1, v2 … vk and Eп: e1 e2 … ek-1 have been constructed so far, and that all of these edges and any resulting isolated vertices have been removed from V and E to form Gk-1.
Since vk has even degree, and ek-1 ends there, there must be an edge ek in Gk-1 that also has vk as a vertex. If there is more than one such edge, select one that is not a bridge for Gk-1. Denote the vertex of ek other than vk by vk+1, Extend Vп: v1, v2 … vk vk+1 and Eп: e1 e2 … ek-1 ek.
Step 3 repeat Step 2 until no edges remain in E
18
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Use Fleury’s algorithm to construct an Euler circuit for the following graph.
19
A
B
D
C
E
F
H
G
ENSA Agadir, 2014
4.1 Euler Paths and Circuits
Ex. 6, Ex. 12, Ex. 14, Ex. 15, Ex. 21, Ex. 25
20
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
A Hamiltonian path is a path that contains each vertex exactly once.
A Hamiltonian circuit is a circuit that contains each vertex exactly once except for the first vertex.
21
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
22
Loops and multiple edges are of no use in finding Hamiltonian circuits, since loops
Could not be used, and only one edge can be used between any two vertices.
Thus we support that any graph in this section has no loops or multiple edges.
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
23
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
24
a
c
d
b
e
D
A
C
B
Has Hamiltonian path
But no Hamiltonian circuit
Has Hamiltonian path
& Hamiltonian circuit
2
1
3
5
6
4
A
B
E
E
A
No Hamiltonian Path
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
Any complete graph Kn has Hamiltonian circuits? In fact, starting at any vertex, you can visit the other vertices sequentially in any desired order.
25
K3
K4
K5
Q: How about K2?
K2
n should be larger than 2
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
has not been completely answered
is still unanswered.
26
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
Let G be a connected graph with n vertices, n>2, and no loops or multiple edges.
G has a Hamiltonian circuit if for any two vertices u and v of G that are not adjacent, the degree of u plus the degree of v is greater than or equal to n.
Corollary 1
G has a Hamiltonian circuit if each vertex has degree greater than or equal to n/2.
27
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
Let the number of edges of G be m. Then G has a Hamiltonian circuit if m ≥ (n2-3n+6)/2, where n is the number of vertices
Proof: Support u & v are non-adjacent vertices in G. Let deg(x) for the degree of x. Let H be the graph produced by eliminating u and v from G along with any edges that have u or v as end points. Then H has n-2 vertices and m- deg(u) –deg(v) edges.
The maximum number of edges that H could possibly have is
And then we have m – deg(u)-deg(v) <= ½(n2-5n+6 )
thus deg(u) +deg(v) >= n (Theorem 1 holds)
28
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
29
C
B
D
G
H
F
A
E
|V| = 8
For any pair of nonadjacent vertices u and v
deg(u) + deg(v) = 4 < 8
Therefore, the conditions given in Theorem
1 & 2 are sufficient, but not necessary,
for the conclusion.
A Hamiltonian Circuit
ENSA Agadir, 2014
4.2 Hamiltonian Paths & Circuits
Find a Hamiltonian circuit (or path) for which the total sum of weights in the path is a minimum.
For example, the vertices might represent cities, the edges, lines of transportation, and the weight of an edge, the cost of traveling along the edge.
30
B
D
C
A
F
G
H
E
6
2
6
2
3
2
3
4
5
5
4
ENSA Agadir, 2014
4.2 Hamiltonian Paths and Circuits
Ex. 8, Ex. 13, Ex. 18, Ex.20, Ex. 21
31
ENSA Agadir, 2014