為什麼這篇A cut B cut 意思鄉民發文收入到精華區：因為在A cut B cut 意思這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者newpuma (還很新)看板Grad-ProbAsk標題[理工] 資演 最小生成樹時間Fri ...
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正向為滿找符合的邊切下去～12/23 15:45
推 garyhsu1209: 先回你最後問的 Min cut = Max flow12/23 15:46
所以如果同一張圖問max flow跟min cut，其實是在同個問題喲？推 krusnoopy: cut就是把點數分成兩堆,兩堆會有很多邊連接,light edge12/23 16:41
→ krusnoopy: 就是兩堆的連接邊中,權重最小的12/23 16:41
→ krusnoopy: A選項說,如果某邊是屬於MST的一邊,則該邊是某個cut的li12/23 16:43
→ krusnoopy: ght edge12/23 16:43
→ krusnoopy: 該邊好像很難聽....不過算了...12/23 16:47
XD 但那個cut是隨便分嗎？※ 編輯: newpuma (223.140.213.159), 12/23/2016 16:50:00
推 krusnoopy: 我想了一下,覺得prim的演算法就是一直找light edge來12/23 16:50
→ krusnoopy: 做出生成樹的,所以選項是對的12/23 16:50
→ krusnoopy: some cut就是任意的意思12/23 16:50
→ krusnoopy: b的反例12/23 17:00
如果只是說最小權重邊我可以理解，但換成cut就覺得有點難懂，難道一定會被cut到嗎，有沒有可能最小權重剛好沒有被cut到？
※ 編輯: newpuma (223.140.213.159), 12/23/2016 17:03:12
推 krusnoopy: 假設是(u,v)邊權重最小,你把u一個點當一堆,其他所有點 12/23 17:07
→ krusnoopy: 當一堆就是light edge了,其實就是prim的切法 12/23 17:07
推 krusnoopy: cut是分兩堆S,T. ST交集空,ST聯集是所有點 12/23 17:10