574
Graph Algorithms
assumption that the graph has no loops. If the graph G has loops, we can strip
them off and consider the modified graph H. If H has an Euler path, then so does
G—whenever we come to a node with a loop, we traverse the loop. If H has no
Euler path, then neither does G.
In the accompanying algorithm (algorithm EulerPath), the input is a connected graph with no loops represented by an n × n adjacency matrix a. The essence
of the algorithm is to count the number of nodes adjacent to each node and to
determine 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. (This
is why we exclude loops; a loop at node i adds only 1 to the adjacency matrix at
position 3i, i 4, yet such a loop contributes 2 arc ends.) The function odd results in
a value “true” if and only if the argument is an odd integer.
algoRitHm EulErPath
EulerPath (n × n matrix a)
//Determines whether an Euler path exists in a connected graph with
//no loops and adjacency matrix a
Local variables:
integer total
//number of odd nodes so far found
integer degree //the degree of a node
integer i, j
//array indices
total = 0
i = 1
while total <= 2 and i <= n do
degree = 0
for j = 1 to n do
degree = degree + a3i, j 4
//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