作者ok8752665 ()
看板Grad-ProbAsk
標題[理工] 演算法 maximum flow觀念
時間Wed Jan 22 17:17:04 2020
看了滿多題目問到在Network flow中
maximum flow是否唯一的問題
想請問要唯一的話有哪些條件
或者是如何判斷是否唯一
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.38.66.191 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1579684627.A.CFF.html
1F：推 NCTUcs: residual graph中找不到cycle就表示max-flow為unique 01/22 17:40
2F：→ ok8752665: 所以基本上跟邊是否整數 或者邊是否全相同/異無關嗎 01/22 17:59
3F：→ ok8752665: ^的capacity 01/22 18:00
4F：推 NCTUcs: 沒有查到其他的充分條件 感覺是只是考找反例的能力吧 01/22 18:26
5F：→ mistel: 請問有題目可以看看嗎？ 01/22 18:55
8F：→ ok8752665: 了解 感謝 01/22 19:30
9F：推 mistel: 感謝 01/22 19:39
10F：推 hsiehong: 想順便問一下 如果risitual network中沒有argument path 01/22 23:24
11F：→ hsiehong: 了，那要如何確認目前的flow 是maximun flow呢？ 01/22 23:24
12F：推 hsiehong: 如下面這個例子 01/22 23:26
14F：→ ok8752665: residual network中沒有augmenting path 那其flow就是 01/22 23:38
15F：→ ok8752665: maximum flow了阿 01/22 23:38
16F：推 Aa841018: residual是反向，如果是max flow應該會有augmenting pat 01/22 23:49
17F：→ Aa841018: h吧？ 01/22 23:49
18F：→ Aa841018: 反而完全不流出的狀況，在resudual 當中才找不到augment 01/22 23:49
19F：→ Aa841018: ing path吧？ 01/22 23:49
20F：→ Aa841018: 因為完全不流出，自然沒有可以流回的path… 01/22 23:50
21F：→ ok8752665: ? 有點不太懂你的意思 所以你是說flow是maximum flow時 01/22 23:56
22F：→ ok8752665: 還會有augmenting path? 01/22 23:56
23F：推 Aa841018: 我是這麼覺得，我概念有錯嗎？ 01/22 23:57
24F：→ ok8752665: 完全不流出的情況 residual會等於原圖 就代表有路出去 01/22 23:57
26F：推 hsiehong: 但上面左圖中flow是1，但實際上maximal flow是2啊 ,res 01/23 00:00
27F：→ hsiehong: idual network中卻沒有augment path了 01/23 00:00
28F：→ ok8752665: 對阿 所以你這張圖的residual沒有路出去了阿 01/23 00:00
29F：→ ok8752665: 有阿 是看residual 右邊那張 還有sbat可以走阿 01/23 00:01
30F：推 Aa841018: 抱歉我有點卡，原則上max flow將某個水管塞滿，那在resi 01/23 00:03
31F：→ Aa841018: dual 當中不是應該可以流回與max flow同等的水流量嗎？ 01/23 00:03
32F：→ Aa841018: 一個是正向出去（max flow),一個是逆向回來（residual) 01/23 00:03
33F：→ ok8752665: 對阿 residual就是給你之後可以倒退的機制阿 01/23 00:07
34F：→ ok8752665: maxflow就會讓你的residual 沒有augmenting path走啊 01/23 00:08
35F：推 Aa841018: 那怎麼會說max flow 時residual 無路可走，max flow就代 01/23 00:13
36F：→ Aa841018: 表送了最多水流過來了，那residual 當然可以逆向送同樣 01/23 00:13
37F：→ Aa841018: 的水流回去，這樣算有路可走吧？ 01/23 00:13
38F：推 Aa841018: 我好像有點懂了，所謂有augmenting path 指的是實線的 01/23 00:17
39F：→ Aa841018: 邊，非虛線的邊對嗎？ 01/23 00:17
40F：→ ok8752665: 先說你那張圖有畫錯 C->B 還有1可以走 然後實虛都能走 01/23 00:19
41F：→ ok8752665: 所謂有augmenting path是指起點到終點有路可走 不是任 01/23 00:20
42F：→ ok8752665: 兩點 01/23 00:20
43F：→ ok8752665: 用你那張圖當例子 也可以發現沒有路從A到B吧 01/23 00:21
44F：推 Aa841018: 謝謝說明（抱歉我突然卡進來狂問…） 01/23 00:21
45F：→ ok8752665: 不會 希望你真的懂了 01/23 00:22