Chapter 9 Directed graphs & Partial Orders238
same vertex,v, we’ll say that theirmerge,fbr, is the walk that starts withfand
continues withr.^1 Two walks can only be merged if the first ends with the same
vertex,v, that the second one starts with. Sometimes it’s useful to name the nodev
where the walks merge; we’ll use the notationfbvrto describe the merge of a walk
fthat ends atvwith a walkrthat begins atv.
A consequence of this definition is that
Lemma 9.2.2.
jfbrjDjfjCjrj:
In the next section we’ll get mileage out of walking this way.9.2.1 Finding a Path
If you were trying to walk somewhere quickly, you’d know you were in trouble if
you came to the same place twice. This is actually a basic theorem of graph theory.
Theorem 9.2.3.The shortest walk between a pair of vertices is a path.
Proof. If there is a walk from vertexutov, there must, by the Well Ordering
Principle, be a minimum length walkwfromutov. We claimwis a path.
To prove the claim, suppose to the contrary thatwis not a path, namely, some
vertexxoccurs twice on this walk. That is,
wDebxfbxgfor some walkse;f;gwhere the length offis positive. But then “deleting”fyields
a strictly shorter walk
ebxg
fromutov, contradicting the minimality ofw.
Definition 9.2.4.Thedistancedist.u;v/, in a graph from vertexuto vertexvis
the length of a shortest path fromutov.
As would be expected, this definition of distance satisfies:Lemma 9.2.5.[The Triangle Inequality]
dist.u;v/dist.u;x/Cdist.x;v/for all verticesu;v;xwith equality holding iffxis on a shortest path fromutov.
(^1) It’s tempting to say themergeis the concatenation of the two walks, but that wouldn’t quite be
right because if the walks were concatenated, the vertexvwould appear twice in a row where the
walks meet.