4. [7 marks] Using the following graph representation (G(V,E,w)):

V = {1, 2, 3, 4, 5, 6, 7}

E = {{1, 3}, {1, 5}, {1, 7}, {2, 3}, {2, 4}, {2, 6}, {3, 4}, {3, 5}, {3, 7} {5, 7}, {6, 7}}

W(1, 3) = 2, W(1, 5) = 7, W(1, 7) = 19

W(2, 3) = 12, W(2, 4) = 9, W(2, 6) = 16

W(3, 4) = 4, W(3, 5) = 5, W(3, 7) = 20

W(5, 7) = 18, W(6, 7) = 11

a) [3 marks] Draw the graph including weights.

b) [2 + 2 = 4 marks] Given the following algorithm for finding a minimum spanning tree for a

graph:

Given a graph (G(V,E)) make a new graph (F) with nodes (V) and no edges

Add all the edges (E) to a set S and order them by weight starting with the minimum weight

While S is not empty and all the nodes V in F are not connected:

Remove the edge s from set S with the lowest weight

When s is added to F:

If it does not cause a cycle to form, keep it

Else discard it from F

Using your graph from a) as G,

i. Provide the order of the edges as they are removed from S, and note whether it is kept or

discarded.

ii. Draw the resulting spanning tree F.