NZ Level 7 (NZC) Level 2 (NCEA) Prim's algorithm

## Interactive practice questions

The direct flight routes between $5$5 major cities of the same country are shown in the graph below. Each edge is marked with the distance (in km) travelled on each route.

To optimise the investment put into these routes, the operating airline wants to find the minimum spanning tree for the graph. a

How many edges will be a part of a spanning tree for this graph?

b

Using Prim's algorithm or otherwise, find a minimum spanning tree for the graph.

Which of the following edges are part of this spanning tree? Select all that apply.

$DE$DE

A

$AB$AB

B

$BC$BC

C

$AE$AE

D

$BD$BD

E

$CE$CE

F

$DE$DE

A

$AB$AB

B

$BC$BC

C

$AE$AE

D

$BD$BD

E

$CE$CE

F
c

Select the diagram which represents the minimum spanning tree. A B C D A B C D
d

Using these flight routes, what is the minimum distance connecting these major cities?

Easy
Approx 4 minutes

At the university, there is a new plan to connect all the campus buildings using underground fiber optic cables. The network to the right was suggested by the engineer.

In a certain area, new underground cables need to be laid to connect electric substations. The graph to the right displays the current connection layout.

### Outcomes

#### M7-5

Choose appropriate networks to find optimal solutions

#### 91260

Apply network methods in solving problems