572
Graph Algorithms
Definition euleR PAth
An euler path in a graph G is a path that uses each arc of G exactly once.
1
2
5
(b)
(a)
4
7
1
2
4
5
3
6
3
Figure 7.6
For this discussion we will assume that all graphs are connected, since an
Euler path generally cannot exist otherwise. 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. It turns out that every graph has an even number of
odd nodes. To see this, choose any graph and let N be the number of odd nodes in
it, N(1) the number of nodes of degree 1, N(2) the number of nodes of degree 2, and
so on. Then the sum S of the degrees of all the nodes of the graph is
S = 1 # N(1) + 2 # N(2) + 3 # N(3) + c + k # N(k)
(1)
for some k. This sum is, in fact, a count of the total number of arc ends in the
graph. Because the number of arc ends is twice the number of arcs, S is an even
number. We will reorganize equation (1) to group together terms for odd nodes
and terms for even nodes:
S = 2 # N(2) + 4 # N(4) + c + 2m # N(2m)
('''''''''''')''''''''''''*
even nodes
+1 # N(1) + 3 # N(3) + c + (2n + 1) # N(2n + 1)
('''''''''''''''')''''''''''''''''*
odd nodes
The sum of the terms representing even nodes is an even number. If we subtract it
from both sides of the equation, we get a new equation—
S′ = 1 # N(1) + 3 # N(3) + c + (2n + 1) # N(2n + 1)
(2)
—where S′ (the difference of two even numbers) is an even number. Now if we
rewrite equation (2) as
S′ = 1 + 1 + c + 1
(''''')''''*
+ 3 + 3 + c + 3
(''''')''''*
+ c
N(1) terms
N(3) terms
+ (2n + 1) + (2n + 1) + c + (2n + 1)
('''''''''''')''''''''''''''*
N(2n + 1) terms
praCtiCe 7 Do Euler paths exist for either graph in Figure 7.6? (Use trial and error to answer. This
is the old children’s game of whether you can trace the whole graph without lifting your
pencil and without retracing any arcs.)
■