Question

Provide a formal proof of the correctness of the algorithm by Boruvka/Solllin for finding a MST.

Answer 1

boruvka/sollin algorithm comes under greedy algorithms

Before understanding the proof you should first know about the red rule and blue rule of greedy algorithms and these rules are explained as below:-

Red rule:-

Let C be a cycle with no red edges. Select an uncolored
edge of C of max weight and color it red.

Blue rule:-

Blue rule. Let D be a cut with no blue edges. Select an uncolored edge
in D of min weight and color it blue.

cut;-

consider a set of nodes s from a graph then the cut is set of all edges with exactly one node in the set s and the other node should not be in set s.

formal proof for boruvka/sollin algorithm:-

let us assume that the graph G that is input to Boruvka's algorithm has distinct edge costs. In the coloring for each blue tree T , an incident edge e with smallest cost is selected. Note that these selected edges need not all be distinct. After the selection of edges is over, the selected edges are colored blue, in some arbitrary order. We now show that any edge e = {u,v} colored blue in the coloring step, is colored according to the blue rule of the greedy method. this means that blue rule should agree with coloring step in boruvka's algorithm. if we could prove this then we can say that boruvka's algorithm is correct.you can also prove this by yourself by taking an example of spanning tree and examine whether edges obtained in coloring step in boruvka's algorithm are same as those edges obtained using the blue rule of greedy algorithms. but actual mathematical proof is explained below.

proof:-

Suppose that e ={u,v} connects blue trees Tu and Tv and further suppose
that e is the edge with smallest cost incident on Tu. In the coloring step in which e is colored
blue, some edges may have been colored blue prior to e. These edges which were colored blue
prior to e (in the current coloring step) may have caused Tu and Tv to belong to be subgraphs
of the same blue tree. We now show by contradiction that this is not possible.
Suppose that just before e is colored blue, there is a blue tree that contains (as subgraphs) Tu and
Tv . Then, even before e is colored blue, there is path between u and v that contains only blue
edges. This path, written as a sequence of edges, can be partitioned into:
path in T1,e1, path in T2,e2,......,ek-1, path in Tk.

where
(a) T1 = Tu, Tk = Tv ,
(b) for each i, ei is an edge from a vertex in Ti to a vertex in Ti+1,
(c) each tree Ti is a blue tree prior to the current coloring step,
(d) and each edge ei is colored BLUE in the current coloring step prior to e.
Since edge (e not equal to e1) is the smallest cost edge incident on T1(= Tu), it must be the case that e1 is the
smallest cost edge incident on T2. This implies that c(e) < c(e1). Using a similar argument, we see
that c(e1) < c(e2) and e2 is the smallest cost edge incident on T3. Continuing this argument we
obtain
c(e) < c(e1) < c(e2) <.....< c(ek1)
and that ek1
is the smallest cost edge incident on Tk. But, this is a contradiction since e is also
incident on Tk.

so edges of spanning tree obtained in blue rule of greedy algorithm are same as edges obtained in coloring step of borovka's algorithm. so we can say that correctness of boruvka's algorithm for finding a MST is justified.