下圖之邊長（edge length）均為不一樣的整數，邊上之數字表示長度。若其最小生成樹（minimum spanning tree）含有連接 b 與 c 的邊(b, c)，則(b, c)之長度最大值為何？
A19
B25正確答案
C27
D29
答案與詳解
B
正確答案
由 MST cycle property，(b,c) 在每個含它的 cycle 中皆不能是最大邊；最緊約束來自 cycle b-c-d-g-b（最大邊 dg=26），加上邊長為相異整數，故 (b,c) ≤ 25，答案為 (B) 25。
載入中…
