關於一個圖的最小生成樹（minimum spanning tree），下列敍述何者錯誤？
A具有唯一的最小生成樹正確答案
B最小生成樹的邊個數是節點個數減 1
C最小生成樹是一個連通圖（connected graph）
D在最小生成樹中的任兩點之間加入一個邊之後會產生一個迴路（cycle）
答案與詳解
為什麼答案是 A
錯誤敘述（即題目要選的答案）。MST 不保證唯一：若圖中存在相同權重的邊，可能產生多棵權重總和相同的最小生成樹。只有當所有邊權重互不相同時，MST 才唯一。
考點：MST 唯一性考點：樹的邊數考點：連通性考點：樹加邊成環
載入中…
