21 下列關於連通圖（connected graph）的最小生成樹（spanning tree）之敘述何者正確？
(A)最小生成樹裡兩節點間可能具有兩條路徑
(B)最小生成樹可能不唯一
(C)最小生成樹可能不存在
(D)最小生成樹的權重小或等於圖中任一子樹的權重

答案：登入後查看
統計： A(68), B(306), C(50), D(114), E(0) #1372595

詳解 (共 2 筆)

#4089616

最佳解的解釋怪怪的，我說一下我的看法好了。

所謂的連通圖，指的是任兩點之間均存連通，均存在路徑

(A)最小生成樹兩節點間只會有一條路徑

(B)對，當有些邊的權重是一樣的時候，生成樹可能不唯一

(C)連通圖一定會有最小生成樹(因為任兩點間均連通)

(D)圖的子樹不一定會包括所有的點，所以子樹權重可能比生成樹小(不確定這個選項回答的對不對，有誤請指教)

10
0
#3814923
最小生成樹強調可利用最少的邊、並且最小的...
(共 89 字，隱藏中）
前往觀看
3
1