[理工] 演算法 Ford-Fulkerson問題

[liljimmy (吉米)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1606456208.A.189.html
推 mi981027: 1. 不對 在capacity是整數的情況下用FF找到的一定是整
→ mi981027: 數，這在CLRS有個定理
推 mi981027: 只是最佳解本來就不一定要是整數，可以稍微畫個簡單的
→ mi981027: 圖試試看，立宇的書裡應該也有例子
→ liljimmy: @mi981027 感謝 那題了解了
→ liljimmy: 第二題的arc是什麼意思還是不會QQ
推 FRAXIS: arc 就是 edge
→ liljimmy: @FRAXIS 那這邊他指的minicut s-t中的arcs就是
→ liljimmy: 指兩個集合之間所連結的邊嗎？
→ liljimmy: 那這題後面是要我們在上述這些「arcs」上capacity+1這
→ liljimmy: 樣嗎？抱歉還是不太懂