[理工] 資演 最小生成樹

[newpuma (還很新)]

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)記得洪逸好像有證過

謝謝大家


--

順帶借題一問，網路流的問題中，minmum cut capacity的求解方法是什麼？一時翻不到
。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.213.159
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1482478517.A.842.html
→ moooner: 逆向為0正向為滿找符合的邊切下去～
推 garyhsu1209: 先回你最後問的 Min cut = Max flow
所以如果同一張圖問max flow跟min cut，其實是在同個問題喲？
推 krusnoopy: cut就是把點數分成兩堆,兩堆會有很多邊連接,light edge
→ krusnoopy: 就是兩堆的連接邊中,權重最小的
→ krusnoopy: A選項說,如果某邊是屬於MST的一邊,則該邊是某個cut的li
→ krusnoopy: ght edge
→ krusnoopy: 該邊好像很難聽....不過算了...
XD 但那個cut是隨便分嗎？
※ 編輯: newpuma (223.140.213.159), 12/23/2016 16:50:00
推 krusnoopy: 我想了一下,覺得prim的演算法就是一直找light edge來
→ krusnoopy: 做出生成樹的,所以選項是對的
→ krusnoopy: some cut就是任意的意思
推 krusnoopy: http://i.imgur.com/hxbMqhe.jpg
→ krusnoopy: b的反例
如果只是說最小權重邊我可以理解，但換成cut就覺得有點難懂，難道一定會被cut到嗎，
有沒有可能最小權重剛好沒有被cut到？
※ 編輯: newpuma (223.140.213.159), 12/23/2016 17:03:12
推 krusnoopy: 假設是(u,v)邊權重最小,你把u一個點當一堆,其他所有點
→ krusnoopy: 當一堆就是light edge了,其實就是prim的切法
推 krusnoopy: cut是分兩堆S,T. ST交集空,ST聯集是所有點