[理工] 演算法 maximum flow觀念

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