【用戶】talehearts
【年級】高二下
【評論內容】在一個連通加權無向圖中，最小生成樹（minimum spanning tree, MST）的定義是：(A) 最小生成樹是連通圖中權值最小的生成樹。這是最小生成樹的正確定義。(B) 如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。這是正確的，因為當所有邊的權值都唯一時，不會有相同總權值的不同生成樹。(C) 最小生成樹不一定存在。這是錯誤的。對於連通圖，最小生成樹總是存在的，因為圖是連通的，所以至少存在一棵生成樹，而且由於我們可以比較不同生成樹的權值，必然存在權值最小的那一棵。(D) 一個連通圖可能有多個生成樹。這是正確的，因為一個連通圖可以有多種不同的樹形結構，包括所有節點。因此，錯誤的敘述是： (C) 最小生成樹不一定存在。