Question

Show Proof of correctness and state, and solve the Recurrence using the Master Theorem. Let G = G(V, E) be an arbitrary, connected, undirected graph with vertex set V and edge set E. Assume that every edge in E represents either a road or a bridge. Give an efficient algorithm that takes as input G and decides whether there exists a spanning tree of G where the number of edges that represents roads is
floor[ (|V|/ √ 2) ]. Do so using the greedy algorithm.

Answer 1

Answer)

Boruvka’s Algorithm is an randomized algorithm for computing the MST .

Boruvka’s Algorithm for computing minimum spaning tree(MST)

Input:connected graph G(v,e)

output:MST T

1. T := ∅.

2. Take the edges of minimum weight and incidents to each vertex.Then add to T.

3. find the connected components made up of marked edges.

4. now we will replace the each connected component by vertex.

5. Remove the each self loops. If the pairs of vertex have the multiple edges then remove all of them , but do not remove the edge with minimum weight .

6. Repeat step from 2 to 5 until only single vertex remains.

Above algorithm efficient algorithm that takes as input G and decides the existence of spanning tree of G .