Description
Given a connected undirected graph, tell if its minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected graph
G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'),
with the following properties:
1. V' = V.
2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted,
connected, undirected graph G = (V, E). The minimum spanning tree T =
(V, E') of G is the spanning tree that has the sma......
阅读全文