CODEWITHSUNDEEP
algorithmgraphtreeminimum-spanning-tree
Ayechan_San
Ayechan_San

Reputation: 175

Negative weight edges

Full question: Argue that if all edge weights of a graph are positive, then any subset of edges that connects all vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive.

My answer: Since the edges connects all vertices, it must be a tree. In a graph, you can remove one of the edges and still connect all the vertices. Also, negative edges can be allowed in a graph (e.g. Prim and Kruskal's algorithms).

Please let me know if there's a definite answer to this and explain to me how you got the conclusion. I'm a little bit lost with this question.

Upvotes: 0

Views: 2023

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490623

With non-negative weights, adding an edge to traverse from one node to another always results in the weight increasing, so for minimum weight you always avoid that.

If you allow negative weights, adding an edge may result in reducing the weight. If you have a cycle with negative weight overall, minimum weight demands that you stay in that cycle infinitely (leading to infinitely negative weight for the path overall).

Upvotes: 2

Edward Peters
Edward Peters

Reputation: 4062

First off, a tree is a type of graph. So " In a graph, you can remove one of the edges and still connect all the vertices" isn't true. A tree is a graph without cycles - i.e., with only one path between any two nodes.

Negatives weights in general can exist in either a tree or a graph.

The way to approach this problem is to show that if you have a graph that connects all components, but is NOT a tree, then it is also not of minimum weight (i.e., there is some other graph that does the same thing, with a lower total weight.) This conclusion is only true if the graph contains only positive edges, so you should also provide a counterexample - a graph which is NOT a tree, which IS of minimum weight, and which IS fully connected.

Upvotes: 2

Related Questions