Graphs (Edexcel International AS Maths: Decision 1): Exam Questions

Figure 1 shows a graph, T.

Write down an example of a path from A to J on T.

State, with a reason, whether A – B – C – D – E – G – F – H – J is an example of a tour on T.

The numbers on the 15 arcs in Figure 2 represent the distances, in km, between nine vertices, A, B, C, D, E, F, G, H and J, in a network.

Use Kruskal’s algorithm to find the minimum spanning tree for the network. You should list the arcs in the order in which you consider them. In each case, state whether or not you are adding the arc to the minimum spanning tree.

Draw the minimum spanning tree using the vertices given in Diagram 1 .

State the weight of the minimum spanning tree.

Explain what is meant by the term ‘path’.

Figure 1 represents a network of roads. The number on each arc represents the length, in km, of the corresponding road. Piatrice wishes to travel from A to J.

Use Dijkstra’s algorithm to find the shortest path Piatrice could take from A to J. State your path and its length.

Piatrice needs to return from J to A via G.

Find the shortest path Piatrice could take from J to A via G and state its length.

Define the terms

(i) tree,

(ii) minimum spanning tree.

Use Kruskal’s algorithm to find the minimum spanning tree for the network shown in Figure 1. You must clearly show the order in which you consider the edges. For each edge, state whether or not you are including it in the minimum spanning tree.

Draw the minimum spanning tree using the vertices given in Diagram 1 below and state the weight of the minimum spanning tree.