[理工] 資演 最小生成樹
有點...看不懂題意跟選項
這邊觀念也有點弱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
→
12/23 15:45, , 1F
12/23 15:45, 1F
推
12/23 15:46, , 2F
12/23 15:46, 2F
所以如果同一張圖問max flow跟min cut，其實是在同個問題喲？
推
12/23 16:41, , 3F
12/23 16:41, 3F
→
12/23 16:41, , 4F
12/23 16:41, 4F
→
12/23 16:43, , 5F
12/23 16:43, 5F
→
12/23 16:43, , 6F
12/23 16:43, 6F
→
12/23 16:47, , 7F
12/23 16:47, 7F
XD 但那個cut是隨便分嗎？
※ 編輯: newpuma (223.140.213.159), 12/23/2016 16:50:00
推
12/23 16:50, , 8F
12/23 16:50, 8F
→
12/23 16:50, , 9F
12/23 16:50, 9F
→
12/23 16:50, , 10F
12/23 16:50, 10F
推
12/23 17:00, , 11F
12/23 17:00, 11F
→
12/23 17:00, , 12F
12/23 17:00, 12F
如果只是說最小權重邊我可以理解，但換成cut就覺得有點難懂，難道一定會被cut到嗎，
有沒有可能最小權重剛好沒有被cut到？
※ 編輯: newpuma (223.140.213.159), 12/23/2016 17:03:12
推
12/23 17:07, , 13F
12/23 17:07, 13F
→
12/23 17:07, , 14F
12/23 17:07, 14F
推
12/23 17:10, , 15F
12/23 17:10, 15F