推 Transfat: (1)每個capacity都是有理數，相加怎麼會變成無理數呢？02/03 19:50
→ Transfat: (1)的最後一句你是肯定句還是疑問句ㄚ？02/03 19:50
推 Transfat: 查了一下，大概的講法是：如果有irrational capacity,02/03 19:54
→ Transfat: ford-fulkerson 會loop forever,always finding smaller02/03 19:54
→ Transfat: and smaller augmenting path.This infinite sequence02/03 19:55
→ Transfat: may not even converge to the maximum flow.02/03 19:56
→ Transfat: 應該就是沒法有maximum flow的意思02/03 19:56
推 Transfat: goo.gl/4bcLyB 請參考02/03 20:03
抱歉一些名詞打錯(1)weight改capacity
(1)的最後一句是要問(2)的問題與(1)無關
關於上述的例子都是max capacity為有理數
所以才會發生無限loop(因為取到流量為無理數)
我是想問當X為無理數且最大時是否會停
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:30:59
※ 編輯: k1992313 (114.137.239.88), 02/03/2017 20:36:15
推 FRAXIS: Ford-Fulkerson 沒有一定挑最小路徑吧02/03 22:27
→ FRAXIS: Edmonds-Karp 才挑最短路徑02/03 22:27
→ k1992313: 我講的最小是指流量02/03 22:34
※ 編輯: k1992313 (118.165.2.153), 02/03/2017 22:35:07
→ aa06697: 印象中Ford–Fulkerson是隨便選可以到終點的路徑？沒有特02/04 09:53
→ aa06697: 別選哪條02/04 09:53
推 Transfat: 同上想法，且假使你說你的挑法每次都要挑最小capacity02/04 11:15
→ Transfat: 要不能保證最後加起來不會是無理數吧，這要看capacity而 02/04 11:15
→ Transfat: 定 02/04 11:15
覺得說明上好像有很多誤會了，抱歉
路徑的流量被限制在路徑中最小的capacity
所以只要這些capacity為有理數即可？
另外
舉個簡單的例子
s->a->t
如果(s,a)的capacity為10^4.2為無理數
（a,t)的capacity為10
這樣ford fulkerson也停不下來嗎
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:24:58
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:33:14
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:39:12
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 11:42:36
推 yellow60127: 假設capacity是無理數，FF可能跑不出來，一直卡在loo02/04 12:57
→ yellow60127: p裡 02/04 12:57
→ k1992313: 樓上，那是因爲有取到capacity為無理數吧，假如像我舉 02/04 13:01
→ k1992313: 的例子也不會停嗎 02/04 13:01
推 yellow60127: 如果邊是無理，augmenting path又亂取，不保証termin 02/04 13:08
→ yellow60127: al 02/04 13:08
→ k1992313: 可是我舉的例子應該取到路徑流量為10就停止了吧？還是02/04 13:14
→ k1992313: 有哪裡沒分析到的？02/04 13:14
→ yellow60127: 你的例子10就停了02/04 13:17
→ yellow60127: 你舉的例子也沒有亂取的問題存在啊02/04 13:18
→ k1992313: 或是敘述改成'如果有邊為無理數，則FFㄧ定無解'這句話就02/04 13:19
→ k1992313: 錯了？02/04 13:19
我是因爲筆記上寫了capacity不可為無理數
覺得這句話太強烈，所以開始了這堆疑惑
※ 編輯: k1992313 (223.137.217.9), 02/04/2017 13:21:33
→ HEroKuma: capacity為無理數且該條擴充流會無限取並收斂時會跑不出 02/06 01:48
→ HEroKuma: 來 02/06 01:48
→ HEroKuma: 有無理數時,即使是最大邊 也有可能在幾次取流後變成會無 02/06 01:49
→ HEroKuma: 限收斂的路徑 02/06 01:49
→ HEroKuma: 我是這樣理解的 02/06 01:50