卷別
資料結構與演算法
選擇國立臺灣大學 2025 · 考試 · 第 12 題
考科演算法
(5 points) Let be an undirected, weighted, simple, and connected graph. Let and be two minimum spanning trees of . Define the set of edges as all edges that are in either or but not in both. Suppose that . Select all correct statement(s) below.
- (A)The subgraph is a disjoint union of cycles and paths.
- (B)All edges in have the same weight.
- (C)There is no edge in that has a unique weight.
- (D)There exists a graph such that .
- (E)Consider the problem MOST-DISTANT-MSTs, which seeks two minimum spanning trees and in order to maximize on . Assume . Then MOST-DISTANT-MSTs is NP-hard.