7.02a Graphs: vertices (nodes) and arcs (edges)

Kruskal's algorithm finds a minimum spanning tree for a connected graph with \(n\) vertices.

1. Explain the terms
   1. connected graph,
   2. tree,
   3. spanning tree.
   \hfill [3]
2. Write down, in terms of \(n\), the number of arcs in the minimum spanning tree. \hfill [1]

The table below shows the lengths, in km, of a network of roads between seven villages, A, B, C, D, E, F and G.

1. Complete the drawing of the network on Diagram 1 in the answer book by adding the necessary arcs from vertex C together with their weights. \hfill [2]
2. Use Kruskal's algorithm to find a minimum spanning tree for the network. You should list the arcs in the order that you consider them. In each case, state whether you are adding the arc to your minimum spanning tree. \hfill [3]
3. State the weight of the minimum spanning tree. \hfill [1]

1. Explain why a network cannot have an odd number of vertices of odd degree. (2)

\includegraphics{figure_4} Figure 4 shows a network of paths in a public park. The number on each arc represents the length of that path in metres. Hamish needs to walk along each path at least once to check the paths for frost damage starting and finishing at \(A\). He wishes to minimise the total distance he walks.

1. Use the route inspection algorithm to find which paths, if any, need to be traversed twice. (4)
2. Find the length of Hamish's route. [The total weight of the network in Figure 4 is 4180 m.] (1)

(Total 7 marks)

1. Explain why it is impossible to draw a network with exactly three odd vertices. [2]

\includegraphics{figure_1} The Route Inspection problem is solved for the network in Fig. 1 and the length of the route is found to be 100.

1. Determine the value of \(x\), showing your working clearly. [4]

A puzzle involves a 3 by 3 grid of squares, numbered 1 to 9, as shown in Fig. 1a below. Eight of the squares are covered by blank tiles. Fig. 1b shows the puzzle with all of the squares covered except for square 4. This arrangement of tiles will be called position 4. \includegraphics{figure_1} A move consists of sliding a tile into the empty space. From position 4, the next move will result in position 1, position 5 or position 7.

1. Draw a graph with nine vertices to represent the nine positions and arcs that show which positions can be reached from one another in one move. What is the least number of moves needed to get from position 1 to position 9? [3]
2. State whether the graph from part (i) is Eulerian, semi-Eulerian or neither. Explain how you know which it is. [2]

Each of the following symbols consists of boundaries enclosing regions. \includegraphics{figure_1} The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for \includegraphics{figure_2} is \(\bullet \longrightarrow \bullet \longrightarrow \bullet\).

1. Produce the graph for the symbol \includegraphics{figure_3}. [1]
2. Give two symbols each having the graph \(\bullet \longrightarrow \bullet\). [2]
3. Produce the graph for the symbol \includegraphics{figure_4}. [2]
4. Produce a single graph for the composite symbol \includegraphics{figure_5}. [2]
5. Give the name of a connected graph with \(n\) nodes and \(n - 1\) arcs. [1]

An adjacency matrix for the simple graph \(G\) is shown below. \includegraphics{figure_5}

1. Using the adjacency matrix, explain why \(G\) is not a complete graph. [2 marks]
2. State, with a reason, whether \(G\) is Eulerian, semi-Eulerian or neither. [2 marks]
3. Draw a graph that is the complement of \(G\) [3 marks]

The simple-connected graph \(G\) has the adjacency matrix $$\begin{array}{c|cccc} & A & B & C & D \\ \hline A & 0 & 1 & 1 & 1 \\ B & 1 & 0 & 1 & 0 \\ C & 1 & 1 & 0 & 1 \\ D & 1 & 0 & 1 & 0 \\ \end{array}$$ Which one of the following statements about \(G\) is true? Tick \((\checkmark)\) one box. [1 mark] \(G\) is a tree \(\square\) \(G\) is complete \(\square\) \(G\) is Eulerian \(\square\) \(G\) is planar \(\square\)