7.02c Graph terminology: walk, trail, path, cycle, route

1. \begin{figure}[h] \end{figure}

1. Define the terms
   1. tree,
   2. minimum spanning tree.
2. Use Prim's algorithm, starting at A , to find a minimum spanning tree for the network shown in Figure 1. You must clearly state the order in which you select the arcs of the tree.
3. Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book and state the weight of the tree.

2. A simply connected graph is a connected graph in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself.

1. Given that a simply connected graph has exactly four vertices,
   1. write down the minimum number of arcs it can have,
   2. write down the maximum number of arcs it can have.
2. 1. Draw a simply connected graph that has exactly four vertices and exactly five arcs.
   2. State, with justification, whether your graph is Eulerian, semi-Eulerian or neither.
3. By considering the orders of the vertices, explain why there is only one simply connected graph with exactly four vertices and exactly five arcs.

3. \begin{figure}[h] \end{figure} [The total weight of the network is 120]

1. Explain what is meant by the term "path".
2. State, with a reason, whether the network in Figure 2 is Eulerian, semi-Eulerian or neither. Figure 2 represents a network of cycle tracks between eight villages, \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } , \mathrm { G }\) and H . The number on each arc represents the length, in km , of the corresponding track. Samira lives in village A, and wishes to visit her friend, Daisy, who lives in village H.
3. Use Dijkstra's algorithm to find the shortest path that Samira can take. An extra cycle track of length 9 km is to be added to the network. It will either go directly between C and D or directly between E and G . Daisy plans to cycle along every track in the new network, starting and finishing at H .
   Given that the addition of either track CD or track EG will not affect the final values obtained in (c),
4. use a suitable algorithm to find out which of the two possible extra tracks will give Daisy the shortest route, making your method and working clear. You must

2 Two simply connected graphs are shown below. \begin{figure}[h] \end{figure} \begin{figure}[h] \end{figure}

1. 1. Write down the orders of the vertices for each of these graphs.
   2. How many ways are there to allocate these vertex degrees to a graph with vertices \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T }\) and U ?
   3. Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
2. Show that graphs 1 and 2 are not isomorphic.
3. 1. Write down a Hamiltonian cycle for graph 1.
   2. Use Euler's formula to determine the number of regions for graph 1.
   3. Identify each of these regions for graph 1 by listing the cycle that forms its boundary.

5 [Figure 3, printed on the insert, is provided for use in this question.]

1. James is solving a travelling salesperson problem.
   1. He finds the following upper bounds: \(43,40,43,41,55,43,43\). Write down the best upper bound.
   2. James finds the following lower bounds: 33, 40, 33, 38, 33, 38, 38 . Write down the best lower bound.
2. Karen is solving a different travelling salesperson problem and finds an upper bound of 55 and a lower bound of 45 . Write down an interpretation of these results.
3. The diagram below shows roads connecting 4 towns, \(A , B , C\) and \(D\). The numbers on the edges represent the lengths of the roads, in kilometres, between adjacent towns. \includegraphics[max width=\textwidth, alt={}, center]{92175666-ef7a-4dca-9cdb-ebde1b40b2c9-05_451_1034_1160_504} Xiong lives at town \(A\) and is to visit each of the other three towns before returning to town \(A\). She wishes to find a route that will minimise her travelling distance.
   1. Complete Figure 3, on the insert, to show the shortest distances, in kilometres, between all pairs of towns.
   2. Use the nearest neighbour algorithm on Figure 3 to find an upper bound for the minimum length of a tour of this network that starts and finishes at \(A\).
   3. Hence find the actual route that Xiong would take in order to achieve a tour of the same length as that found in part (c)(ii).

6 A connected graph is semi-Eulerian if exactly two of its vertices are of odd degree.

1. A graph is drawn with 4 vertices and 7 edges. What is the sum of the degrees of the vertices?
2. Draw a simple semi-Eulerian graph with exactly 5 vertices and 5 edges, in which exactly one of the vertices has degree 4 .
3. Draw a simple semi-Eulerian graph with exactly 5 vertices that is also a tree.
4. A simple graph has 6 vertices. The graph has two vertices of degree 5 . Explain why the graph can have no vertex of degree 1.

1 The famous fictional detective Agatha Parrot is investigating a murder. She has identified six suspects: Mrs Lemon \(( L )\), Prof Mulberry \(( M )\), Mr Nutmeg \(( N )\), Miss Olive \(( O )\), Capt Peach \(( P )\) and Rev Quince \(( Q )\). The table shows the weapons that could have been used by each suspect.

1. Draw a bipartite graph to represent this information. Put the weapons on the left-hand side and the suspects on the right-hand side. Agatha Parrot is convinced that all six suspects were involved, and that each used a different weapon. She originally thinks that the axe handle was used by Prof Mulberry, the broomstick by Miss Olive, the drainpipe by Mrs Lemon, the fence post by Mr Nutmeg and the golf club by Capt Peach. However, this would leave the hammer for Rev Quince, which is not a possible pairing.
2. Draw a second bipartite graph to show this incomplete matching.
3. Construct the shortest possible alternating path from \(H\) to \(Q\) and hence find a complete matching. Write down which suspect used each weapon.
4. Find a different complete matching in which none of the suspects used the same weapon as in the matching from part (iii).

7

1. 1. Complete Figure 4 to identify the feasible region for the problem. \begin{figure}[h]
      \captionsetup{labelformat=empty} \caption{Figure 4} \includegraphics[alt={},max width=\textwidth]{5a826f8b-4751-4589-ad0a-109fc5c821f2-12_922_940_849_552}
      \end{figure} 7
      1. (ii) Determine the maximum value of \(5 x + 4 y\) subject to the constraints.
         7
   2. The simple-connected graph \(G\) has seven vertices. The vertices of \(G\) have degree \(1,2,3 , v , w , x\) and \(y\) 7
   3. 1. Explain why \(x \geq 1\) and \(y \geq 1\) 7
      2. Explain why \(x \leq 6\) and \(y \leq 6\) 7
      3. Explain why \(x + y \leq 11\) 7
      4. State an additional constraint that applies to the values of \(x\) and \(y\) in this context.
         7
      5. The graph \(G\) also has eight edges. The inequalities used in part (a)(i) apply to the graph \(G\).
      7
   4. 1. Given that \(v + w = 4\), find all the feasible values of \(x\) and \(y\).
         7
   5. (ii) It is also given that the graph \(G\) is semi-Eulerian. On Figure 5, draw \(G\). Figure 5

1. Explain what is meant by the term 'path'. [2]

\includegraphics{figure_3} Figure 3 shows a network of cycle tracks. The number on each edge represents the length, in miles, of that track. Mary wishes to cycle from A to I as part of a cycling holiday. She wishes to minimise the distance she travels.

1. Use Dijkstra's algorithm to find the shortest path from A to I. Show all necessary working in the boxes in Diagram 1 in the answer book. State your shortest path and its length. [6]
2. Explain how you determined the shortest path from your labelling. [2]

Mary wants to visit a theme park at E.

1. Find a path of minimal length that goes from A to I via E and state its length. [2]

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]

A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.

1. What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
2. What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
3. What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
4. State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]

\includegraphics{figure_2}