IE$2108$

$4.($a$)$ Define a Python function to find a Minimum Spanning Tree $($MST$)$ of a graph using Kruskal's Algorithm. Assume the graph is represented as an adjacency list.

$(7$ Marks$)$

$($b$)$ You are given a unidirectional weighted graph in Figure $4,$ in which the vertices are denoted by numbers in the circles, and the edges with weights are represented by lines connecting the vertices. Write a Python program to find an MST for this graph using the function defined in part $($a$).$ Write down the output of your program.

$(6$ Marks$)$

$($c$)$ Explain the steps of Kruskal's Algorithm and justify the output of your Python program in part $($b$).$

$(6$ Marks$)$

$($d$)$ Under what conditions may a graph have multiple MSTs$?$ Can the graph in part $($b$)$ have multiple MSTs$?$ If so$,$ show another MST that is different from the MST that you have obtained in part $($b$).$ If not, why not?

$(6$ Marks$)$