Exercise 1
There are 5 cities. The cost of building a road directly between i and j is the entry a(i,j) in the matrix below. An undefined entry indicates that the road cannot be built. Determine the least cost to make all cities accessible from each other.
We order the edges according to the weights: 12, 23, 13, 45, 25, 15, 24, 35, 14 (row-column). Kruskal's algorithm accepts edges 12, 23, then rejects 13, then accepts 45, 25, then stops. Thus, the least cost to build the road network is 3 + 3 + 7 + 8 = 21.
Exercise 2
Professor Herr Guerard proposes a new divide-and-conquer algorithm for calculating minimum spanning trees, which goes as follows.
Given a graph G = (V, E), partition the set V of vertices into two sets V1 and V2 such that |V1| and |V2| differ by at most 1. Let E1 be the set of edges which are incident only at the vertices of V1, and let E2 be the set of edges which are incident only at the vertices of V2. Recursively solve a minimum spanning tree problem on each of the two subgraphs G1 = (V1, E1) and G2 = (V2, E2). Finally, select the edge of minimum weight in E that crosses the cut V1, V2 and use this edge to unite the two resulting minimum spanning trees into a single spanning tree.
Either argues that the algorithm correctly computes a minimum spanning tree of G, or provides an example for which the algorithm fails. Find an example where it works and where it doesn't.
We assert that the algorithm will fail. A simple counterexample is shown below. The graph G = (V, E) has four vertices: {v1, v2, v3, v4} and is divided into subsets G1 with V1 = {v1, v2} and G2 with V2 = {v3, v4}. The MST of G1 has a weight of 4, and the MST of G2 has a weight of 5, and the minimum weight edge crossing the cut (V1, V2) has a weight of 1, in sum the spanning tree formed by the proposed algorithm follows {v2, v1 , v4, v3} which has a weight of 10. On the contrary, it is obvious that the MST of G follows {v4, v1, v2, v3} with a weight of 7. proposed algorithm therefore fails to obtain an MST.
Exercise 3
Show that if G is a weighted graph and e is an edge whose weight is less than any other edge, then e must belong to every spanning tree of minimum weight for G.
Suppose that T is a spanning tree of minimum weight for G that does not contain edge e. Consider then the graph T+e. This graph must contain a cycle C which contains the edge e. Let f be an edge of C different from e, and let T*=T+e−f. Then T* is also a spanning tree for G, but w(T*)=w(T+e−f)=w(T)+w(e)−w(f) < w(T), unlike T being a spanning tree of minimum weight. Therefore, such a tree T (i.e. without e) cannot exist.
Exercise 4
Show that if all the weights of the weighted graph G are distinct, then there is a unique spanning tree of minimum weight for G.
The proof somewhat mimics that of the proof of Kruskal's algorithm. Suppose that T is a tree generated by Kruskal's algorithm (in fact, a moment of reflection shows that with the conditions of the problem, only one such tree could be generated).
We assert that there are no other spanning trees of minimum weight for G. Assume (and we will show that this leads to a contradiction) that there exist other spanning trees of minimum weight, and choose any one, T'. Suppose then that e is the first edge of T which does not belong to T'. That is, suppose the edges of T, in the order they were added to form T, are e1, e2 , …, ek , …en−1 and that e = ek and for all i <k, ei ∈T’ .
Let C be the cycle at T'+ e which contains e. let f be an edge of C which is not in T'. We note that by the nature of Kruskal's algorithm, the weight of f must be greater than the weight of e. Indeed, at the time we placed e in T, f was also available and would not have produced a cycle (since all edges of T up to that point are also in T'). So if w(f) <w(e), nous aurions utilisé f à ce stade. Alors maintenant l’ensemble T*=T’+e−f est un arbre couvrant de poids inférieur à T’, une contradiction.
Exercise 5
Consider an "inverted" Kruskal algorithm for calculating an MST. Initialize T to be the set of all edges of the graph. Now consider the edges from greatest to least cost. For each edge, remove it from T if that edge belongs to a cycle in T. Assuming that all edge costs are distinct, does this new algorithm correctly compute an MST?
Yes. At step k (starting ak = 1), the algorithm considers the k-th largest cost advantage. If this edge belongs to a cycle in the remaining graph T, then all the edges of this cycle (and in fact of T) must have a cost lower than that of the considered edge. Thus, the edge cannot belong to the MST (per the previous question).
The algorithm cannot end with T having a cycle, because the algorithm would have considered every edge in such a cycle and would have removed the highest cost edge when it considered that edge. The algorithm also cannot end with T disconnected, because edges are only removed when they belong to a cycle, and disconnecting an edge that belongs to a cycle does not disconnect the graph. Thus, the algorithm ends with T being a spanning tree.
It is the MST because all the edges that have been deleted have the property of not belonging to the MST. Since the only edges that could belong to the MST are the remaining ones, and they do indeed define a spanning tree, it must be the MST.
EN 
FR 
ES