Question

In this problem, we will develop a new algorithm for finding minimum spanning trees. It is based upon the following property:

Pick any cycle in the graph, and let e be the heaviest edge in that cycle. Then there is a minimum spanning tree that does not contain e.

(a) Prove this property carefully.

(b) Here is the new MST algorithm. The input is some undirected graph G=(V,E) (in adjacency list format) with edge weights {we}.sort the edges according to their weights for each edge $\mathbf{e}\mathbf{\in }\mathbf{E}$, in decreasing order of we:

if e is part of a cycle of G:

G = G - e (that is, remove e from G )

return G , Prove that this algorithm is correct.

(c) On each iteration, the algorithm must check whether there is a cycle containing a specific edge . Give a linear-time algorithm for this task, and justify its correctness.

(d) What is the overall time taken by this algorithm, in terms of $\left|E\right|$? Explain your answer.

Short answer

a).For finding minimum spanning tree which contain cycle in the graph, and a heaviest edge in that cycle. Then there is a minimum spanning tree that does not contain that edge is proved.

b).The new minimum spanning tree algorithm in adjacency list format with edge weights is defined.

c).A linear-time algorithm where a cycle containing a specific edge is given below.

d). The total running time for this algorithm takes $\mathrm{O}\left({\left|\mathrm{E}\right|}^2\right)$.

Step-by-step solution

Minimum spanning tree.

The minimum spanning tree is evaluated by using algorithm that are Kruskal’s algorithm or prim’s algorithm where the shortest distance from the source and the destination is evaluated and check from which path it is minimum and called the minimum cost spanning tree.

Algorithm is checking whether its cycle is containing a specific edge of weights or not. As per the leaner time algorithm is use for specifying edge cycle to get or prove algorithm is correct.

Algorithm where edge base on weights:

a).

Filter the edges by their respective weights. Then starts sorting the edge weights on until edge within tree is found. for every weighted edge $\mathrm{e}\in \mathrm{E}$ in order of decreasing weights:

If edge e is part of tree T's cycle,

remove it from the tree " T."

T = T -e (Remove edge “ e” from tree “ T” ) Execute until the edge in tree T for each edge weight is returned. $\mathrm{e}\in \mathrm{E}$in decreasing order of weights: If edge e is part of tree T's cycle, verify whether it was in the tree " T". Substitute "e " for the edge "e " “ e” from the tree “ ”

(Replace edge “ ” by edge “ ”)

Return the new tree “ T”

Return T'

Assume the smallest spanning tree " T," which includes the edge " e."

Eliminating this graph's edge "e " divides the tree " T" into two linked components, " S" & "$\frac{\mathrm{S}}{\mathrm{v}}$ ". While it is impossible to link all vertices after eliminating the edge " ," at least one edge allows us to do so. “ ”need to get out of the cycle “ S” to “$\frac{\mathrm{S}}{\mathrm{v}}$”. Then, change “ e” by “ e”and now it gives rise to the tree known as “ T”. That is,cos(T')$\le$cos(T) . As a result, tree "T " is a minimal spanning tree, and tree "R " is a minimum spanning tree. “ T”is also a minimal spanning tree which doesn't even have edge “e ” but that have edge “e ”. For example:

Consider the undirected graph given below:

Step 3: New minimum spanning tree algorithm in adjacency list format with edge weights.

Let us just start using vertex " A" on the graph.

• The vertex "A " has two edges with weights of 1 between A and B vertices and 5 between A and D vertices.

• The minimal weight from A to B vertices are 1 in this case, as illustrated below:

After that, start from vertex " B".

• Every vertex " B" has two edges, one from B to A vertices and the other from B to C vertices, both having a weight of one.

• The weight 1 vertices from B to A are already drawn. Then, from B to C vertices, the minimal weight 1 is illustrated below:

Then comes the vertex "C".

• Each vertex "C" has two edges, one from C towards B vertices another from C to D vertices, both having a weight of one.

• Weight 1 has already been drawn from C to B vertices. Then, from C to D vertices, the minimal weight 1 is illustrated below:

The following vertex is "D".

• Each vertex "D" has two edges, one from D to C vertices and the other from D to A vertices, both having a weight of one.

• The weight 1 has already been pulled from D to C. As a result, in vertex "D", there is also no minimum weight. The minimal spanning tree is then displayed below.:

Finally, the minimum spanning tree is shown below:

removing the graph's strongest edge " 3," which would be referred to as "e ," which divides the tree "T " into two linked components, " S" & "$\frac{\mathrm{S}}{\mathrm{v}}$" as illustrated below:

• Replace the edge “e” by “e” to produce the new tree “T” is shown below:

Therefore, both trees “ T” and “ T” are minimum spanning tree but the new tree “ T”does not contain the edge “e ”.

Step 4: A linear-time algorithm where a cycle containing a specific edge.

c).

This new minimal spanning tree (MST ) technique is valid.

O/p: Create a new minimal spanning tree that is devoid of the hardest edge " e."

Proof: Its input of the new MST method is an undirected graph G=(V,E) with edge weights.

• Take the edge weights in decreasing order for each edge.

• Verify that the largest edge weight " e" is part of the graph " G" cycle. If the criteria is met, delete the edge "e " from the graph to build a new tree with the shortest path.

o The method generates a new graph at each step. “G-e ”.That seems to be, the new graph's minimal spanning tree.

• Ultimately, return the "G" tree that was produced.

As a result, the technique generates a new graph that represents the least spanning tree of "" and excludes the largest edge weights " e.". For example:

Consider the undirected graph is given below:

The following are the steps to determining the least spanning tree:

• Arrange the corners in decreasing weight order:AD,CD,BC,AB .

• Inside the ordering, take into account the very first edge AD. Eliminate the edge AD from the graph because it is a component of the cycle.

This graph that results is as follows:

• Take into account the second-to-last CD when placing your purchase. Doing nothing when the edge CD isn't part of the cycle.

• With in ordering, think about the next edge BC. Do nothing since the edge BC may not be a part of the cycle.

• When ordering, take into account the second edge, AB . Do nothing since the edge AB is not part of the cycle.

Finally, this is the minimal spanning tree:

Step 4: The overall time taken by this algorithm, in terms of  |E|.

d).

Linear-time algorithm to check whether there is a cycle containing a specific edge e :

• Make e =(u,v) be the starting point for a DFS.

• Need not evaluate the edge e when evaluating outgoing edges from u .

• Examine the DFS tree to see if the edges e is a back-egde

.

As a result, the linear-time technique is obtained by using depth first search to discover the components.

d) difficulty of algorithm:

In the algorithm,

• Time taken for sorting the edges is $\left(\left|\mathrm{E}\right|\log \left|\mathrm{E}\right|\right)$.

• For each step, check the cycle takes the time of $0(\left|\mathrm{E}\right|$.

o Removing the edges takes the time of $\left|\mathrm{E}\right|-\left|\mathrm{V}\right|+1$.

o Thus, the total time for each step to complete the cycle takes $O\left(\left|E\right|\times \left|E\right|-\left|V\right|+1\right)$.

• Then, add all the above running time $\left(\left|\mathrm{E}\right|\log \left|\mathrm{E}\right|+(\left|\mathrm{E}\right|-\left|\mathrm{V}\right|\mathrm{x}\left|\mathrm{E}\right|\right)=\mathrm{O}\left(\left|\mathrm{E}\right|\log \left|\mathrm{E}\right|+({\left|\mathrm{E}\right|}^2-\left|\mathrm{E}\right|\left|\mathrm{V}\right|\right)$.

Hence, the running time of all the steps are upper bound values, the maximum value of all the upper bound values is considered as the total running time of the algorithm. So, the maximum upper bound limit is $\mathrm{O}\left({\left|\mathrm{E}\right|}^2\right)$. Therefore, the total running time for this algorithm takes $\mathrm{O}\left({\left|\mathrm{E}\right|}^2\right)$.