作者liljimmy (吉米)
看板Grad-ProbAsk
標題[理工] 演算法 Ford-Fulkerson問題
時間Fri Nov 27 13:50:06 2020
https://i.imgur.com/gj3EXz0.jpg
請問這題的B選項，題目說任意邊的capacity都是整數，推測選項意思應該是：執行Ford-Fu
lkerson找到一條augmenting path時，不一定要把他補滿可以只加任意flow，所以才會有可
能產生小數的flow在邊上，不知道這樣理解對不對？
https://i.imgur.com/OjFKR2m.jpg
這邊想問一下名詞””arc””的定義是什麼？
看答案推敲是指minimum cut上所有的邊都叫做arc嗎？
先謝謝各位高手。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.77.223.227 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1606456208.A.189.html
1F：推 mi981027: 1. 不對 在capacity是整數的情況下用FF找到的一定是整 11/28 00:27
2F：→ mi981027: 數，這在CLRS有個定理 11/28 00:27
3F：推 mi981027: 只是最佳解本來就不一定要是整數，可以稍微畫個簡單的 11/28 00:32
4F：→ mi981027: 圖試試看，立宇的書裡應該也有例子 11/28 00:32
5F：→ liljimmy: @mi981027 感謝 那題了解了 11/28 11:13
6F：→ liljimmy: 第二題的arc是什麼意思還是不會QQ 11/28 11:13
7F：推 FRAXIS: arc 就是 edge 11/28 13:27
8F：→ liljimmy: @FRAXIS 那這邊他指的minicut s-t中的arcs就是 12/01 11:01
9F：→ liljimmy: 指兩個集合之間所連結的邊嗎？ 12/01 11:01
10F：→ liljimmy: 那這題後面是要我們在上述這些「arcs」上capacity+1這 12/01 11:01
11F：→ liljimmy: 樣嗎？抱歉還是不太懂 12/01 11:01