卷別

資料結構與演算法(A)

選擇

國立臺灣大學 2022 · 考試 · 第 19 題

(5 points) Consider the following undirected graph $G$ . Let $T$ be the minimum spanning tree (MST) of the graph. Which is INCORRECT?

Vertices $V_1, \dots, V_7$ with edges and weights:

$(V_1, V_4) = 1$
$(V_1, V_3) = 3$
$(V_2, V_7) = 2$
$(V_1, V_2) = 8$
$(V_2, V_3) = 14$
$(V_1, V_7) = 16$
$(V_4, V_3) = 20$
$(V_4, V_5) = 21$
$(V_1, V_6) = 25$
$(V_5, V_6) = 28$
$(V_6, V_7) = 15$
$(V_1, V_5) = 36$

(A)
Edge $(V_1, V_4)$ is in $T$
(B)
Edge $(V_4, V_5)$ is in $T$
(C)
Let $w_{4,5}$ be the weight of $(V_4, V_5)$ . If we decrease $w_{4,5}$ by 16 (i.e., $w_{4,5}$ becomes 5), then $T$ remains to be the MST of $G$
(D)
Let $w_{2,3}$ be the weight of $(V_2, V_3)$ . If we decrease $w_{2,3}$ by 10 (i.e., $w_{2,3}$ becomes 4), then $T$ remains to be the MST of $G$
(E)
none of the other choices

標準解析

AI 生成