Walks, Trails, and Paths

 

Some graph problems involve "walking" from one vertex to another by moving along a sequence of edges, where each edge shares a vertex with the next edge in the sequence. In formal terms, a walk from x0 to xn is a sequence of edges that we denote by a sequence of vertices x0, xl,..., xn such that there is an edge from xi-1 to xi, for 1 ≤ i ≤ n. A walk allows the possibility that some edge or some vertex occurs more than once. For example, in the graph of Figure 3.6, the sequence b, c, d, b, a is a walk that visits b twice and the sequence a, b, c, b, d is a walk that visits b twice and also uses the edge between b and c twice.

A trail is a walk in which no edge appears more than once. So vertices can be revisited in a trail, but edges cannot. For example, in the graph of Figure 3.6, the sequence b, c, d, b, a is a trail that visits b twice but the sequence a, b, c, b, d is not a trail.

A path is a walk in which no edge appears more than once and no vertex appears more than once, except possibly when the beginning vertex is also the ending vertex. For example, in the graph of Figure 3.6, the sequence a, b, c, d is a path, but the sequence a, b, c, d, b is not a path because the vertex b occurs twice. A cycle is a path whose beginning and ending vertices are equal. The sequence a, b, c, a is a cycle, but the sequence a, b, a is not a cycle because the edge from a to b occurs twice.

The length of a walk (also trail and path) is the number of edges on it. So the length of the walk x0, xl,..., xn is n. For example, in the graph of Figure 3.6, the path a, b, d has length two and the cycle a, b, c, a has length three.

Figure 3.6

 

Let's emphasize here that the definitions for walk, trail, path, and cycle apply to both graphs and directed graphs. But now we come to an idea that needs a separate definition for each type of graph. A graph is connected if there is a path between any two vertices. A directed graph is connected if, when direction is ignored, the resulting undirected graph is connected. A graph with no cycles is called acyclic. A directed graph that is acyclic is sometimes referred to as a "DAG" to mean a directed acyclic graph.

Let's look at two famous graph problems that you may have seen. For the first problem you are to trace the first diagram in Figure 3.7 without taking your pencil off the paper and without retracing any line.

 

Figure 3.7

 

After some fiddling, it's easy to see that it can be done by starting at one of the bottom two corners and finishing at the other bottom corner. The second diagram in Figure 12.6 emphasizes the graphical nature of the problem. From this point of view we can say that there is a walk that travels each edge exactly once. In other words, there is a trail that includes every edge. Since the trail visits some vertices more than once, our walk is not a path.

The second famous problem is named after the seven bridges of Kenigsberg that, in the early 1800s, connected two islands in the river Pregel to the rest of the town. The problem is to find a trail through the town by walking across each of the seven bridges exactly once. In Figure 3.8 we've pictured the two islands and seven bridges of Kenigsberg together with a multigraph representing the situation. The vertices of the multigraph represent the four land areas and the edges represent the seven bridges.

Figure 3.8

 

The mathematician Leonhard Euler A707-1783) proved that there aren't any such trails by finding a general condition for such trails to exist. In his honor, any trail that contains every edge of a graph is called an Euler trail. For example, the graph for the tracing problem has an Euler trail, but the seven bridges problem does not. We can go one step further and define an Euler circuit to be any trail that begins and ends at the same vertex and contains every edge of the graph. There are no Euler circuits in the graphs of  Figure 3.7 and Figure 3.8.