(15p) Minimum spanning trees (MSTs).

3.1 (5p) The notion of a minimum spanning tree is applicable to a connected weighted graph. Do we have to check a graphs connectivity before applying Prims algorithm or can the algorithm do it by itself? What is the result of Prims algorithm on a disconnected graph?

3.2 (5p) What about Kruskals algorithm ? Does it work on a disconnected graph ? How would you modify Kruskals algorithm to find a minimum spanning forest on a disconnected graph.

3.3 (5p) Does Prims and Kruskals algorithms always work correctly on graphs with negative edge weights? Find an easy way to prove your answer.