The minimum spanning tree problem was one of finding a subset T of the edges of

Question

The minimum spanning tree problem was one of finding a subset T of the edges of a connected graph G such that all of the vertices remain connected in the subgraph whose edges are only T, and the sume of the weights of the edges in T is as small as possible. Stating the problem in this way, we can extend the problem to the case where the edge weights are not necessarily all positive (i.e., allow negative weights)

A) In the case of positive and negative weights (no zero weights, though), show that the subset T that minimizes total weight need not be a tree

B) Adapt either Kruskal's or Prim's algorithms to solve this more general problem

Explanation / Answer

A)

Yes, previously, that is before krushkal algorithm there was problem with negative edges. Especially with algorithms like Dijikstras algorithm. It cannot handle the negative edges. Issue with negative edges are, while we are modifying edhes weights, they become modified to negative weights and result may not be exact tree. So, we have to handle negative edges. One of the simplest solution is , when we encounter negative routes
multiply with large constant number, so we will found any difficulty. Exactly this is the solution followed in famous krushkals algorithm.

And with graph having negative edges , we can't guarantee that the spanning tree that we get is a tree.
Let us consider one simple example...
One gragh G has three vertices and three edges with weights -1
We may get minimum spanning graph but not minimum spanning tree.
since we cant get exact tree.. all ways are get minimum value and also we are having same weights.
So finally, if we have negative edges then it is not a tree , it is graph.

---------------------------------------------------------------------------------------------------------------------------------------------------

B)

In krishkals algorithm we can solve above situation. The concept of minimum spanning tree
allows weights of an arbitary sign. We can add a constant positive number to all negative
edges, generally choosing a big positive number is better, to avoid clash between remaining
positive edges. Then tree is remain same as MInimum Spanning tree.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.