http://i.imgur.com/dihlryA.jpg
有點...看不懂題意跟選項
這邊觀念也有點弱orz
(a)選項：如果一邊為最小生成樹的邊則light edge crossing some cut of the graph
這是什麼意思？
(b)選項為什麼錯，是因為倒因為果嗎
(b)(c)選項一樣不是很懂light edge crossing the cut的意思
(d)(e)記得洪逸好像有證過
謝謝大家

cut就是把點數分成兩堆,兩堆會有很多邊連接,light edge就是兩堆的連接邊中,權重最小的A選項說,如果某邊是屬於MST的一邊,則該邊是某個cut的light edge該邊好像很難聽....不過算了...我想了一下,覺得prim的演算法就是一直找light edge來做出生成樹的,所以選項是對的some cut就是任意的意思http://i.imgur.com/hxbMqhe.jpgb的反例假設是(u,v)邊權重最小,你把u一個點當一堆,其他所有點當一堆就是light edge了,其實就是prim的切法cut是分兩堆S,T. ST交集空,ST聯集是所有點

先回你最後問的 Min cut = Max flow

逆向為0正向為滿找符合的邊切下去～