Transcript ch06s2

Graph Algorithms
Mathematical Structures
for Computer Science
Chapter 6
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Graph Algorithms
Euler Path





Section 6.2
DEFINITION: EULER PATH
An Euler path in a graph G is a path that uses each
arc of G exactly once.
We want to find if an Euler path exists in graph G.
Whether an Euler path exists in a given graph hinges
on the degrees of its nodes.
A node is even if its degree is even and odd if its
degree is odd.
THEOREM ON ODD NODES IN A GRAPH
The number of odd nodes in any graph is even.
Euler Path and Hamiltonian Circuit
1
Euler Path



Section 6.2
THEOREM ON EULER PATHS
An Euler path exists in a connected graph if and only
if there are either no odd nodes or two odd nodes. For
the case of no odd nodes, the path can begin at any
node and will end there; for the case of two odd nodes,
the path must begin at one odd node and end at the
other.
The theorem on Euler paths is actually an algorithm to
determine if an Euler path exists on an arbitrary
connected graph.
We make the simplifying assumption that the graph
has no loops. If G has loops, we remove them and call
the graph H. If H has an Euler path, then so does G,
and vice versa.
Euler Path and Hamiltonian Circuit
2
Euler Path Algorithm






Section 6.2
In the Euler Path algorithm, the input is a connected graph
represented by an n  n adjacency matrix A.
The algorithm counts the number of nodes adjacent to each
node and determines whether this is an odd or an even
number.
If there are too many odd numbers, an Euler path does not
exist.
The variable total keeps track of the number of odd nodes
found in the graph.
The degree of any particular node, degree, is found by
adding the numbers in that node’s row of the adjacency
matrix.
The function odd results in a value “true” if and only
if the argument is an odd integer.
Euler Path and Hamiltonian Circuit
3
Euler Path Algorithm

Section 6.2
ALGORITHM EulerPath
EulerPath (n  n matrix A)
//Determines whether an Euler path exists in a connected graph with
//no loops and adjacency matrix A
total = 0
i=1
while total  2 and i  n do
degree = 0
for j = 1 to n do
degree = degree + A[i, j ] //find degree of node i (*)
end for
if odd(degree) then
total = total + 1 //another odd degree node found
end if
i=i+1
end while
if total > 2 then
write (“No Euler path exists”)
Else
write (“Euler path exists”)
end if
end EulerPath
Euler Path and Hamiltonian Circuit
4
Euler Path Algorithm Example




Section 6.2
Given the following adjacency matrix:
When the algorithm first enters the while loop, total is 0
and i is 1, then degree is 0.
Within the for loop, the values of row 1 of the adjacency
matrix are added in turn to degree, resulting in a value for
degree of 3.
The odd function applied to degree returns the value
“true,” so the value of total is increased from 0 to 1; one
node of odd degree has been found.
Euler Path and Hamiltonian Circuit
5
Euler Path Algorithm Example






Section 6.2
Then i is incremented to 2.
Neither the bounds on total nor the bounds on the array
size have been exceeded, so the while loop executes again
for row 2.
degree is found to be odd, so the value of total is changed
to 2.
When the while loop is executed for row 3 of the array, the
value of degree is even (4), so total does not change, and
the while loop is executed again with i = 4.
Row 4 again produces an odd value for degree, so total is
raised to 3.
This terminates the while loop. There is no Euler path
because the number of odd nodes exceeds 2.
Euler Path and Hamiltonian Circuit
6
Euler Path Analysis



Section 6.2
In the worst case, the while loop in the algorithm is
executed n times, once for each row.
Within the while loop, the for loop is executed n
times, once for each column.
EulerPath is therefore an Θ(n2) algorithm in the worst
case.
Euler Path and Hamiltonian Circuit
7
Hamiltonian Circuit Problem




Section 6.2
A Hamiltonian circuit is a cycle using every node of
the graph.
A Hamiltonian circuit requires that each and every
node of the graph be visited once and only once
(except for the start node, which is also the end node)
There can be unused arcs but no arc can be used more
than once.
No efficient algorithm has ever been found to
determine if a Hamiltonian circuit exists.
Euler Path and Hamiltonian Circuit
8