The Graph Abstract Data Type.
Minimum Spanning Tree Algorithms.
Other Data Structures: Priority Queues and Disjoint-Sets

Exercises

All exercises here are to be done on paper.

Simple comprehension exercises

Given the weighted undirected graph in the figure, illustrate the steps of Prim's algorithm. Apply the algorithm illustrating step by step the contents of the data structures that are used (priority queue or distance array).

Given the weighted undirected graph, illustrate the steps of Kruskal's algorithm. Explain each step of the algorithm, and the contents of the additional data structures that are used (disjoint-sets).

Thinking exercises

[SEDGW] Consider the following assertion: You can rescale the weights of the edges by adding the same positive constant to all of them without affecting the MST. True or false? If you think that it is true, give a general proof. If you think that it is false, it is enough to give a counterexample.

[SEDGW] Consider the following assertion: an edge-weighted graph has a unique MST ONLY if its edge weights are distinct. True or false? If you think that it is true, give a general proof. If you think that it is false, it is enough to give a counterexample.

[SEDGW] Consider the following assertion: If a graph's edges all have distinct weights, the MST is unique. True or false? If you think that it is true, give a general proof. If you think that it is false, it is enough to give a counterexample.

[SEDGW] Consider the following assertion: If a graph's edges all have distinct weights, the shortest edge MUST always belong to the MST. True or false? If you think that it is true, give a general proof. If you think that it is false, it is enough to give a counterexample.

[SEDGW] Consider the following assertion: If a graph's edges all have distinct weights, the longest edge will NEVER belong to the MST. True or false? If you think that it is true, give a general proof. If you think that it is false, it is enough to give a counterexample.

[SEDGW] How would you find a MAXIMUM spanning tree of an edge-weighted graph?

[CLRS 23.2-7] Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?

Alternative MST algorithms - correct or not?

[CLRS - problem 23-4] There are given three different algorithms. Each one takes a connected graph and a weight function as input and returns a set of edges T . For each algorithm, either prove that T is a minimum spanning tree or prove that T is not a minimum spanning tree. 
MAYBE-MST-A(G;w)
  sort the edges into nonincreasing order of edge weights w
  T = E
  for each edge e, taken in nonincreasing order by weight
	if T-{e} is a connected graph
		T=T-{e}
 return T

MAYBE-MST-B(G;w)
  T = Void Set
  for each edge e, taken in arbitrary order
 	 if T+{e} has no cycles
                T=T+{e}
 return T 

MAYBE-MST-C(G;w)
  T = Void Set
  for each edge e, taken in arbitrary order              
             T=T+{e}
             if T has a cycle c
                let ee be a maximum-weight edge on c
                T=T-{ee}
 return T
[Divide-and-conquer-MST] We have the following proposalas an alternate algorithmfor finding MST: Given a graph G = (V, E), partition the set V of vertices into two sets V1 and V2 such that the numbers of nodes in V1 and V2 differ by at most 1. Let E1 be the set of edges that are incident only on vertices in V1, and let E2 be the set of edges that are incident only on vertices in V2. Recursively solve a minimum-spanning-tree problem on each of the two subgraphs G1 = (V1, E1) and G2 = (V2, E2). Finally, select the minimum-weight edge in E that crosses the cut V1, V2, and use this edge to unite the resulting two minimum spanning trees into a single spanning tree.

Is this algorithmfor MST correct or not? If you think that it is correct, give a general proof. If you think that it is not correct it is enough to give a counterexample.