※ 引述《metalalive (想玩音樂)》之銘言：
: 想問 7.d 小題的寫法
: http://rapid.lib.ncu.edu.tw:8080/cexamn/exam/EC02_97_01.pdf
: 這題答案是 true
: (參考洪傑的書,不過他沒解釋做法)
: 那我是要給他一個反例 & 另一個可以work 的例子嗎?
: 因為敘述是說 "...part of SOME MST" , 不是所有S.T.都成立
: 謝謝
給定任一棵 MST T, 假定 e 不屬於 T, 那麼把 e 接上 T. 這會形成一個環.
因為 e 是唯一的最輕的邊, 所以環中其他邊都比 e 重. 拔掉環中任一其他邊,
我們獲得生成樹 T' 且 cost(T')＜cost(T), 矛盾.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.35.102