If all the edge weights of an undirected graph are positive, then any subset…
2006
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a
- A.
Hamiltonian cycle
- B.
grid
- C.
hypercube
- D.
tree
Attempted by 95 students.
Show answer & explanation
Correct answer: D
Answer: A tree (specifically, a minimum spanning tree).
Explanation:
A subset of edges that connects all vertices is a connected spanning subgraph.
If such a subgraph contains a cycle, then because all edge weights are positive, removing any edge from that cycle keeps the subgraph connected and strictly reduces the total weight. Therefore a minimum-weight connected subgraph cannot contain a cycle.
A connected acyclic spanning subgraph is, by definition, a tree. Hence the minimum-weight connecting subset is a tree.
This minimum-weight tree is commonly called a minimum spanning tree (MST); it can be found by algorithms such as Kruskal's or Prim's.