卷別

資料結構與演算法

選擇

國立臺灣大學 2023 · 考試 · 第 13 題

(5 points) Properties of min. spanning tree (MST): Let $T$ be a MST of a weighted graph $G$ with at least 3 vertices. Which of the following statements is/are correct?

(A)
Given an edge $e$ in $G$ but not in $T$ , we can form a cycle by putting $e$ to $T$ . Then $e$ has the largest weight among edges in $C$ (the cycle).
(B)
If we partition $G$ into two subsets, and let $e$ be the smallest-weight edge across the partition. Then $e$ belongs to some MST in $G$ .
(C)
The edge with the smallest weight in $G$ must belong to some MST of $G$ .
(D)
The edge with the second smallest weight in $G$ must belong to some MST of $G$ .
(E)
The edge with the third smallest weight in $G$ must belong to some MST of $G$ .

標準解析

AI 已複查