3
\includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-4_399_1331_255_367}
- By listing the vertices passed through, in the order they are used, give an example for the graph above of:
- a walk from A to H that is not a trail,
- a trail from A to H that is not a path,
- a path from A to H that is not a cycle.
The arcs are weighted to form a network. The arc weights are shown in the table, apart from the weight of arc AG. The arcs model a system of roads and the weights represent distances in km.
| A | B | C | D | E | F | G | H |
| A | - | 3 | - | 8 | - | - | \(x\) | - |
| B | 3 | - | 5 | - | - | - | - | - |
| C | - | 5 | - | 4 | 3 | - | - | - |
| D | 8 | - | 4 | - | 5 | - | - | 9 |
| E | - | - | 3 | 5 | - | 7 | 6 | - |
| F | - | - | - | - | 7 | - | - | - |
| G | \(x\) | - | - | - | 6 | - | - | 2 |
| H | - | - | - | 9 | - | - | 2 | - |
- Use the matrix form of Prim's algorithm to find a minimum spanning tree, of total weight 30 km , that does not include arc AG.
The road modelled by arc AG is now reopened.
- For what set of values of \(x\) could AG be included in a minimum spanning tree for the full network?
- Which arc from the minimum spanning tree in part (b) is not used when arc AG is included?