[理工] 演算法 圖論

[mistel (Mistel)]

https://i.imgur.com/86wzad1.jpg
請問第三小題的敘述一定成立嗎？
立宇老師上課是說maximal flow problem拿來解決所有有理數，那maximal flow不是應該有
可能有分數嗎？


第47題
https://i.imgur.com/WveKymu.jpg
請問這題的是要做什麼？看不懂題意

第43題第2小題的(c)選項
https://i.imgur.com/ePS3fSn.jpg
https://i.imgur.com/uYcTt3e.jpg
雖然我直覺選下去了但我看不懂@@
請問w(ai)<=w(ei)是什麼意思？ 為什麼G中的任意點ai也會有權重？
我看題目並沒有更新過G中各點的權重，回去翻kruskal's也沒有調整過點的權重啊@@


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.137.50.75 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1569171135.A.395.html
推 FRAXIS: 一般都只討論整數的情況 因為分數你只要全部乘以最小公倍
→ FRAXIS: 數就變成整數了
推 FRAXIS: 47 題就只是問當 edge weight 有上限時 如何實作
→ FRAXIS: priority queue 來加速
感謝F大！
另外再請教一下為什麼第二小題在這種情況下會用到雙向鏈結呢？看不懂解答的建法為什麼
是這樣子
補充另一半的解答
https://i.imgur.com/vhSMZrS.jpg
推 mi981027: https://i.imgur.com/xwpyTg0.jpg
剛剛有翻到原文書的intergrality theorem這邊
https://i.imgur.com/VS6gxpW.jpg
所以我可以理解為
若圖上所有邊的capacity為整數，則使用ford fulkerson會得到最大流量f為整數，且對於
所有在圖上的點u,v，u到v的流量為整數
但其實流量f的解並不一定必需是整數，只是用ford-fulkerson跑出來會是，這樣對嗎？
推 mi981027: https://i.imgur.com/zMxfC3Z.jpg
哦哦哦，犯蠢了，感謝mi大
※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:04:29
※ 編輯: mistel (223.137.50.75 臺灣), 09/23/2019 13:14:59
推 mi981027: 嗯嗯對的（話說原來書上有這個定理@@該添購了）
→ mistel: 課本上通常一個算法大概Lenma加上定理應該有十多個XD，mi
→ mistel: 大可以去compbook徵，蠻好徵的~
→ mathtsai: (1)對 maximum flow和是不是分數沒關
推 FRAXIS: 雙向鏈結只是拿來存同 priority 的 nodes