Weighted graph problems, TRUE/FALSE + explanation
I'm trying to get some true/false questions done. I'm getting worried when I'm answering many of them with true... Please assume that all graphs are undirected and do not have distinct weights. Negative weights should be fine.
Qa) If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
My answer is true. For example, we have a graph with nodes A, B, C, D, E.
AB = 1
BC = 2
BD = 3
CD = 100
DE = 4
As you can see, BCD is a cycle. My argument is that since it is a cycle, we can always avoid the unique heaviest edge CD by taking other routes. Therefore it is true. Is my argument sound (enough)?
Qb) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST.
My answer is true, but my instinct tells me something's wrong. Well... Disjkstra's and Prim's are both greedy algorithms. They both go for the lightest weighted edge every time. Are there any cases that a shortest-path tree is NOT a minimum spanning tree? I actually have a hard time understanding the difference between these two guys.
Qc) Prim's algorithm works with negative weighted edges.
My answer is true. Because that's what wiki said... :p The algorithm is about finding the lowest-cost edge among all edges. So a negative weighted edge shouldn't matter, is it? But what about negative weighted cycle?
Qd) If G has a cycle with a unique lightest edge e, then e must be part of every MST.
My answer is true. We have to access all nodes in an MST. In a cycle of length 3, for instance, we can always traverse all nodes in that cycle with 2 steps. If there is a unique lightest edge, we'll most certainly choose it in our MST.
Are my claims sound? Perhaps they are insufficient? So are there any suggestions?
Answer
Suggestion for b): Your instinct says it's wrong, so try to construct a counterexample. If you find one, it's settled, otherwise you can often see why a claim is true by analysing why your construction of a counterexample failed. I'm not telling you whether your answer or your instinct is right, though.
The homework certainly has been due long ago, so the answers:
Qa) If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.
True. Suppose you have a spanning tree T containing the edge e. If you remove the edge e from the tree, you get a graph with two nonempty connected components C1 and C2. At least one of the other edges in the cycle must connect C1 and C2 (otherwise it wouldn't be a cycle). Let g be such an edge. The tree T' obtained from T by removing e and adding g is a spanning tree with smaller weight than T. Therefore T was not an MST.
Qb) The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST.
My answer is true, but my instinct tells me something's wrong.
The instinct was right, that's false. Consider
6
A---B
3 | | 1
C---D
3
where the shortest-path tree is computed from vertex A. The shortest-path tree is
6
A---B
3 |
C---D
3
with total weight 12, but the unique MST is
A B
3 | | 1
C---D
3
with weight 7.
Qc) Prim's algorithm works with negative weighted edges.
True. One way to deduce that from the correctness for positive weights is to add a constant weight W to all edges, so that all edge weights are positive (e.g. W = 1 + max { |weight(e)| : e ∈ E }).
Since a tree with V vertices always has V - 1 edges, the total weights of any spanning tree differ by (V - 1)*W between the modified and unmodified weights, so a tree is an MST for the modified weights if and only if it is one for the unmodified edge weights.
The ordering of the edges by weight isn't changed by adding a constant to all weights, so Prim's algorithm constructs the same spanning tree for the modified edge weights as for the unmodified weights, in the same sequence.
By the correctness for positive weights, the tree constructed by Prim's algorithm with the modified weights is an MST for the modified weights.
Qd) If G has a cycle with a unique lightest edge e, then e must be part of every MST.
False. Consider
1 1
A---B---C
| / \ |
1 | /4 5\ | 1
|/ 6 \|
D-------E
The cycle BDE has a unique lightest edge BD of weight 4, but the MST contains none of the edges of that cycle.
If there is a unique lightest edge e in the graph G, that must, however, be part of every MST. That is dual to a): Consider a spanning tree T of G that doesn't contain e. By adding e to T, we obtain a graph T' that must have a cycle (since T was a spanning tree and e not in T). Any cycle in T' must contain e, otherwise that would be a cycle in T. So pick any cycle C in T' (there is exactly one, but that isn't important) and remove any edge other than e from C. Let the resulting graph be T''.
The total weight ot T'' is smaller than that of T, since T'' is obtained from T by replacing an edge with a lighter one. T'' is connected (since it was obtained from T' by removing an edge of a cycle), and contains V vertices and V - 1 edges. Hence it is a spanning tree, and thus T was not minimal.