Trails and Circuits, Part I

In the last section we used some long-winded phrases like "a path that crosses every edge exactly once". In this lesson we'll develop some short-hand phrases that make describing paths within a graph simpler. Then we'll look at another application that leads into another classic problem, in this case one that still hasn't been solved.

What You Should Learn

  • The technical terms for various kinds of paths on a graph: walks, trails, circuits and cycles.
  • How the various types of paths build on each other.
path through woods

If u and v are vertices in a graph then a u-v walk is a series of vertices, starting with u and ending with v, such that every vertex in the series is connected by an edge to the vertices before and after it in the series.

A walk is just what the name implies: a path between two points. If you think of the graph as a set of walkways connecting play areas in a park then a "walk" exists between two areas if there's a series of walkways connecting them.

graph 8Look at the graph to the right. (Think of it as the map of a park if you like.) In that graph there exists a v1-v4 walk: v1, v2, v4. Notice that the definition doesn't say anything about walks being unique. You can easily come up with several more ways to get from v1 to v4. The definition also doesn't say anything about repetition. For example, v1, v3, v2, v1, v3, v4 is a perfectly good walk even though it crosses the v1v3 edge twice. If we want to simplify the language we used to discuss the Konigsberg Bridge Problem we're going to need something more limited.

If u and v are vertices in a graph then a u-v trail is a u-v walk that doesn't repeat any edges. A u-v circuit is a u-v trail that contains at least three edges and that has u = v. A circuit that doesn't repeat any vertices, except the first/last, is called a cycle.

Both of these definitions narrow down our definition of a walk. A trail is a special case of a walk where none of the edges is crossed twice. A circuit is a special kind of a trail that finishes at the same place that it started. A cycle is a cicuit that doesn't repeat any vertices. Take special note of that. We're talking about vertices this time, not edges. This is a much more limiting case - if you're looking at the drawing of a graph, a cycle looks like a circular path.

Trails and Circuits, Part II >><< The Konigsberg Bridge Problem, Exercises