9.2. Digraph Walks and Paths 237
wherehvi!viC 1 i 2 E.G/fori 2 Œ0;k/. The walk is said tostartatv 0 , toendat
vk, and thelength,jvj, of the walk is defined to bek. The walk is apathiff all the
vi’s are different, that is, ifi¤j, thenvi¤vj.
Aclosed walkis a walk that begins and ends at the same vertex. Acycleis a
closed walk whose vertices are distinct except for the beginning and end vertices.
Note that a single vertex counts as a length zero path, and also a length zero
cycle, that begins and ends at itself.
Although a walk is officially an alternating sequence of vertices and edges, it
is completely determined just by the sequence of successive vertices on it, or by
the sequence of edges on it, and we will describe walks that way whenever it’s
convenient. For example, for the graph in Figure 9.1,
.a;b;d/, or simplyabd, is (a vertex-sequence description of) a length-2
path,
.ha!bi;hb!di/, or simplyha!bihb!di, is (an edge-sequence de-
scription of) the same length-2 path, abcbdis a length-4 walk,
dcbcbdis a length-5 closed walk, bdcbis a length-3 cycle, hb!cihc!biis a length-2 cycle, and hc!bihb aiha!diisnota walk. A walk is not allowed to follow edges
in the wrong direction.
Length-1 cycles are also possible. The graph in Figure 9.1 has none, but ev-
ery vertex in the divisibility relation digraph of Figure 9.5 is in a length-1 cycle.
Length-1 cycles are sometimes calledself-loops.
If you walk for a while, stop for a rest at some vertex, and then continue walking,
you have broken a walk into two parts. For example, stopping to rest after following
two edges in the walk (9.1) through the divisibility graph breaks the walk into the
first part of the walk
1 h 1! 2 i 2 h 2! 4 i 4 (9.2)
from 1 to 4, and the rest of the walk
4 h 4! 12 i 12 h 12! 12 i 12 h 12! 12 i12: (9.3)from 4 to 12, and we’ll say the whole walk (9.1) is themergeof the walks (9.2)
and (9.3). In general, if a walkfends with a vertex,v, and a walkrstarts with the