__Walks__

Definition: For a graph G=(V(G),E(G)), a Walk is defined as a sequence of alternating vertices and edges such as v0,e1,v1,e2,…,ek,vk where each edge ei={vi−1,vi}. The Length of this walk is k. |

For example, the graph below outlines a possibly walk (in blue). The walk is denoted as *abcdb*. Note that walks can have repeated edges. For example, if we had the walk *abcdcbce*, then that would be perfectly fine even though some edges are repeated.

Note that the length of a walk is simply the number of edges passed in that walk. In the graph above, the length of the walk is *abcdb* is 4 because it passes through 4 edges.

__Open / Closed Walks__

Definition: A walk is considered to be Closed if the starting vertex is the same as the ending vertex, that is v0=vk. A walk is considered Open otherwise. |

For example, the follow graph shows a closed walk in green:

Notice that the walk can be defined by *cegfc*, and the start and end vertices of the walk is *c*. Hence this walk is closed.

__Trails__

Definition: A Trail is defined as a walk with no repeated edges. |

So far, both of the earlier examples can be considered trails because there are no repeated edges. Here is another example of a trail:

Notice that the walk can be defined as *abc*. There are no repeated edges so this walk is also a trail.

Now let’s look at the next graph:

Notice that this walk must repeat at least one edge.

__Paths__

Definition: A Path is defined as an open trail with no repeated vertices. |

Notice that all paths must therefore be open walks, as a path cannot both start and terminate at the same vertex. For example, the following orange coloured walk is a path

because the walk *abcde* does not repeat any edges.

Now let’s look at the next graph with the teal walk. This walk is NOT a path since it repeats a vertex, namely the pink vertex *c*:

__Cycles__

Definition: A Cycle is defined as a closed trail where no other vertices are repeated apart from the start/end vertex. |

Below is an example of a circuit. Notice how no edges are repeated in the walk *bcgfb*, which makes it definitely a trail, and that the start and end vertex *b* is the same which makes it closed.

__Circuits__

Definition: A Circuit is a closed trail. That is, a circuit has no repeated edges but may have repeated vertices. |

An example of a circuit can be seen below. Notice how there are no edges repeated in the walk *hbcdefcgh*, hence the walk is certainly a trail. Additionally, the trail is closed, hence it is by definition a circuit.

Comments are closed.