8.04 Applications of paths, walks and trails

A walk describes the process of starting at a vertex and moving along an edge (in the direction of the arrow) to a new vertex. Continue the walk by following another edge to a second vertex, a third edge to a third vertex, and so on. In a simple network a walk is represented by a sequence of vertices.

Here is a simple, undirected network, with the green arrows representing a walk around the network.

We can describe this walk as the sequenceA, \, B, \, A, \, E, \, F, \, D, \, E.

A walk that starts and ends at the same vertex is closed, and if it starts and ends at different vertices it is open.

The walk above is open - below is a different walk on the same network.

This walk has sequence A, \, B, \, A, \, D, \, F, \, C, \, G, \, D, \, E, \, A.

Since it starts and ends at the same vertex, it is closed. We can also tell by looking at the sequence (and not the diagram) that’s the walk is closed, since the sequence starts and ends with the same letter.

A walk is the most general definition of how we can move around a network. Sometimes we want to impose a stricter condition - if we say that the walk cannot use the same vertex more than once, we call it a path (we can reuse the start/end vertex only). If the path is closed, we call it a cycle.

Here are two different paths on the same graph:

The green walk DGCFEA on the left is an open path, since no vertex is used more than once, and it starts and ends at different vertices. The orange walk BCFDEAB on the right is a closed path(cycle), since no vertex is used more than once, except for the vertex at the start/end.

Examples

Example 1

Which of the following graphs is connected? Select all the correct options.

A

B

C

D

Worked Solution

Create a strategy

Choose graph(s) that have path between every pair of vertices.

Apply the idea

Among the chocies, options C and D have vertices that cannot be reached from every other vertices. This means that their graph is not connected.

So, options A and B are connected as there are paths between each pair of their vertices.

Watch question walkthrough

If a walk cannot use the same edge more than once, it is a trail if it’s open and a circuit if it’s closed. Here is one of each on the same network:

The blue walk ADFEDGCF on the left is a trail, since no edge is used more than once, and it is open. The red walk GCFEDFADG on the right is a circuit, since no edge is used more than once, and it is closed.

• All paths are trails

• All cycles are circuits.

Examples

Example 2

Which of the following is a circuit in the network shown?

A

C,\,B,\,A,\,E,\,D,\,C

B

B,\,A,\,E,\,C,\,D,\,B

C

B,\,C,\,A,\,E,\,D,\,C

D

D,\,C,\,B,\,A,\,E,\,D

Worked Solution

Create a strategy

Choose the trail that starts and ends on the same vertex and has no repeat edges.

Apply the idea

Option A starts and ends on C. The edges covered are CB, BA, AE, ED, and DC. So no edges are repeated. So it is a circuit.

Option B starts and ends on B. The edges covered are BA, AE, EC, CD, and DB. So no edges are repeated. So it is a circuit.

Option C is not a circuit because it does not start and end on the same vertex.

Option D starts and ends on D. The edges covered are DC, CB, BA, AE, and ED. So no edges are repeated. So it is a circuit.

So the correct answers are options A, B, and D.

Watch question walkthrough

Example 3

Which of the highlighted edges in the network is a bridge?

A

Edge 3

B

Edge 1

C

Edge 4

D

Edge 2

E

None

Worked Solution

Create a strategy

Choose an edge that would cause the graph to break into two pieces.

Apply the idea

Based on the given network, removing among the four edges will still make the network be connected as you can still reach every other vertices through vertex F. This means that no edges are considered as bridges.

So, the correct answer is option E.

Watch question walkthrough

If a network has a trail or circuit that uses every edge, it is described as traversable (sometimes semi-Eulerian). This special walk is then called an Euler trail - If it’s open or an Euler circuit if it’s closed, named after the same Euler that gave us Euler’s formula. If a network has an Euler circuit we call it an Euler network (sometimes Eulerian).

Some texts refer to such a trail as an Euler path, but this special walk is a trail (since vertices can be repeated), not a path.

You can think about a traversable networks as ones where you can start at a vertex and draw in all the edges without taking your pen (or finger or stylus) off the page (or screen). Here are two traversable networks, the one on the right is an Euler network:

Each network has a trail that uses every edge exactly once. The trail on the right is closed, so it is a circuit, and any vertex can be the start/end.

Examples

Example 4

Consider the networks below:

A

B

C

D

a

Which one of the networks is traversable?

Worked Solution

Create a strategy

Choose a network where you can draw the network by passing through each edge exactly once without taking your pen/finger/stylus off the page.

Apply the idea

Among the choices, only Option C is traversable since we can move through all its vertices and edges without crossing an edge more than once on this network.

Watch question walkthrough

b

The traversable network from part (a) has been labelled below:

Which vertices can you start at in order to traverse the network? Select the most correct answer only.

A

A,C and G

B

D \text{ and } F

C

Just C

D

B and E

E

Any of the vertices

F

Just D

Worked Solution

Create a strategy

Find a way of traversing the network by choosing which vertex to start and which vertex to finish at.

Apply the idea

Notice that we can traverse this network by doing a loop and ending up where we started. This means that we can start at any of the vertices in order to traverse this network, and ending on the same vertex where you begin to trace the path.

So, the correct answer is Option E.

Watch question walkthrough