Chapter 11 Simple Graphs324
11.8 Getting fromutovin a Graph
Walks and paths in simple graphs are esentially the same as in digraphs. We just
modify the digraph definitions using undirected edges instead of directed ones. For
example, the formal definition of a walk in a simple graph is a virtually that same
as Definition 9.2.1 of walks in digraphs:
Definition 11.8.1.Awalk in a simple graph,G, is an alternating sequence of ver-
tices and edges that begins with a vertex, ends with a vertex, and such that for every
edgehu—viin the walk, one of the endpointsu,vis the element just before the
edge, and the other endpoint is the next element after the edge. Thelength of a
walkis the total number of occurrences of edges in it.
So a walk,v, is a sequence of the form
vWWDv 0 hv 0 —v 1 iv 1 hv 1 —v 2 iv 2 :::hvk 1 —vkivk
wherehvi—viC 1 i 2 E.G/fori 2 Œ0;k/. The walk is said tostartatv 0 , toend
atvk, and thelength,jvj, of the walk isk. The walk is apathiff all thevi’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 of length three or more whose vertices are distinct except for the
beginning and end vertices.
Note that a single vertex counts as a length zero path and closed walk. But in
contrast to digraphs, a single vertex is not considered to be a cycle.
As in digraphs, the length of a walk isone lessthan the number of occurrences of
vertices in it. For example, the graph in Figure 11.16 has a length 6 path through the
seven successive verticesabcdefg. This is the longest path in the graph. The graph
in Figure 11.16 also has three cycles through successive verticesbhecb,cdec, and
bcdehb.
11.8.1 Cycles as Subgraphs
A cycle aren’t intended to have a beginning or an end, and so can be described
byanyof the paths that go around it. For example, in the graph in Figure 11.16,
the cycle starting atband going through verticesbcdehbcan also be described
as starting atdand going throughdecbcd. Furthermore, cycles in simple graphs
don’t have a direction:dcbceddescribes the same cycle as though it started and
ended atdbut went in the opposite direction.
A precise way to explain which closed walks describe the same cycle is to define
cycle as a subgraph instead of as a closed walk. Namely, we could define a cycle
inGto be asubgraphofGthat looks like a length-ncycle forn 3.
