試題詳解

28. Which one of the following statements is not correct?
(A) If an edge is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. (Definition: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.)
(B) If a graph has a unique minimum spanning tree then, for every cut of the graph, there is a unique light edge crossing the cut.
(C) A graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut.
(D) Let e be a maximum-weight edge on some cycle of the graph G = (V, E), then there is a minimum spanning tree of G' = (V, E-{e}) that is also a minimum spanning tree of G = (V, E).
(E) Let (u, ) be a minimum-weight edge in a graph G. Then (u, v) belongs to some minimum spanning tree of G.