Networks

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$`D``E`

A

$AB$`A``B`

B

$BC$`B``C`

C

$AE$`A``E`

D

$BD$`B``D`

E

$CE$`C``E`

F

$DE$`D``E`

A

$AB$`A``B`

B

$BC$`B``C`

C

$AE$`A``E`

D

$BD$`B``D`

E

$CE$`C``E`

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

Sign up to try all questions

Choose appropriate networks to find optimal solutions

Apply network methods in solving problems