State number of edges formula

3

1. 1. State the number of edges in a minimum spanning tree of a network with 11 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 11 vertices, \(A , B , \ldots , K\). The number on each edge represents the distance, in miles, between a pair of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4c5c963b-0183-4dc7-9054-b2c7a3eb8c1b-03_1468_1239_721_404}
   1. Use Prim's algorithm, starting from \(A\), to find a minimum spanning tree for the network.
   2. Find the length of your minimum spanning tree.
   3. Draw your minimum spanning tree.

3

1. 1. State the number of edges in a minimum spanning tree for a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree for a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The number on each edge represents the distance between a pair of adjacent vertices. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-06_921_1710_717_150}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your minimum spanning tree.
   3. Draw your minimum spanning tree. \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_38_118_440_159} \includegraphics[max width=\textwidth, alt={}, center]{44bbec2c-32f4-4d28-9dd6-d89387228454-07_40_118_529_159}

6

1. Greatest number of arcs
   for a network with five vertices \(=\) \(\_\_\_\_\) for a network with \(n\) vertices \(=\) \(\_\_\_\_\)
2. (a) For a network with five vertices
   maximum number of passes \(=\) \(\_\_\_\_\) maximum number of comparisons
   in the first pass \(=\) \(\_\_\_\_\) in the second pass = \(\_\_\_\_\) in the third pass = \(\_\_\_\_\) maximum total number of comparisons = \(\_\_\_\_\) (b) For a network with \(n\) vertices
   maximum total number of comparisons = \(\_\_\_\_\)

3. M1 Vertices in tree	M2 Arcs in tree			M3 Vertices not in tree
   				A B C D E
   DE	D 2 \(E\)			\(A B C\)
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_109_220_1879_786}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_163_220_2005_786}
   				\multirow{3}{*}{}
   	\includegraphics[max width=\textwidth, alt={}]{e1495f6b-c09f-46a1-a6f8-02354e28887a-11_231_220_2174_786}

   \(\boldsymbol { M 4 }\)
   Sorted list

   \(|\)

   \(D\)	2	\(E\)
   \(A\)	3	\(E\)
   \(A\)	4	\(C\)
   \(C\)	5	\(D\)
   \(B\)	6	\(E\)
   \(B\)	7	\(C\)
   \(A\)	8	\(B\)
   \(C\)	9	\(E\)

4. \(\_\_\_\_\)

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{194d16e0-8e05-45c0-8948-99808440ed2a-004_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

3

1. 1. State the number of edges in a minimum spanning tree of a network with 10 vertices.
   2. State the number of edges in a minimum spanning tree of a network with \(n\) vertices.
2. The following network has 10 vertices: \(A , B , \ldots , J\). The numbers on each edge represent the distances, in miles, between pairs of vertices. \includegraphics[max width=\textwidth, alt={}, center]{4a186c87-5f84-4ec3-8cc3-a0ed8721b040-03_1294_1118_785_445}
   1. Use Kruskal's algorithm to find the minimum spanning tree for the network.
   2. State the length of your spanning tree.
   3. Draw your spanning tree.

6 A garden has seven statues \(A , B , C , D , E , F\) and \(G\), with paths connecting each pair of statues, either directly or indirectly. To provide better access to all the statues, some of the paths are being made wider.
6

1. State why six is the minimum number of paths that need to be made wider. 6
2. The table below shows the number of trees that need to be removed to make the path between adjacent statues wider. A dash in the table means that there is no direct path between the two statues.

   Statue	\(\boldsymbol { A }\)	\(\boldsymbol { B }\)	C	\(\boldsymbol { D }\)	\(E\)	\(F\)	\(G\)
   \(\boldsymbol { A }\)	-	4	7	-	-	-	-
   B	4	-	6	2	3	-	-
   C	7	6	-	-	3	-	4
   \(D\)	-	2	-	-	4	5	-
   \(E\)	-	3	3	4	-	3	7
   \(F\)	-	-	-	5	3	-	6
   G	-	-	4	-	7	6	-

   Find the minimum number of trees that need to be removed. Fully justify your answer.
   6
3. A landscaper identifies that two new wide paths could be constructed without removing any trees. However, there are only enough resources to build one new wide path. The new wide path could be between \(A\) and \(D\) or between \(A\) and \(F\).
   Explain clearly how the solution to part (b) can be adapted to find the new minimum number of trees that need to be removed.
   [0pt] [2 marks]