We find the path from u to v in tree T, if there is one edge with weight larger than the decreased weight, then we can replace it.
June 24, 2007
Exercises 23.1-10
Suppose that T is not a minimum spanning tree in G with weight w’, then there are at least one different edge with minimum spanning tree T’. The edge must be on the cycle which contains (u,v), but this is impossible.
Exercises 23.1-9
If T’ is not spanning tree, we can find another minimum spanning tree T”. Let M = T” + (T-T’), M will be a spanning tree with smaller weight. Contradiction.
Exercises 23.1-8
Consider the sorted list of T and T’ sequentially. If the first different edge weight occurs, it means the light edge’s weight is not unique. It is impossible.
Exercises 23.1-7
If the subset of edges is not tree, we can remove some edges and the result graph is still connected.
If G is a triangle with all weight -1, then the minimum weight subset of edges is all edges which is not tree.
Exercises 23.1-6
By the Prim’s algorithm, if every cut has unique light edge then the result is unique.
Converse is not true, let G=(V,E), V={1,2,3}, E={(1,2),(1,3)}. Since G has unique minimum spanning tree, but when S={1}, (S, V-S) does not have unique light edge.
Exercises 23.1-5
If e be a maximum-weight edge on some cycle, then e must not be the minimum spanning tree edge besides there are other equal weight edges on the cycle. In the case of equal weight edges, we can select all the cycle edges except e. Hence there is a minimum spanning tree in G and G’.
Exercises 23.1-4
If all edges’ weights are equal, then all edges are light edges. But it may not be a minimum spanning tree.
Exercises 23.1-3
Edge (u,v) must be the light edge of (S, S-u). Otherwise, we can construct another spanning tree with smaller weight.
Exercises 23.1-2
Let G=(V,E), V={1,2,3,4,5}, E={(1,2), (1,3), (2,4), (3,5)} . Weight function is {1,2,3,4}. When S={1,2,3}, A={(1,2),(1,3)}. Edge (3,5) is safe edge but not light edge.
