推 NCTUcs: residual graph中找不到cycle就表示max-flow為unique 01/22 17:40
→ ok8752665: 所以基本上跟邊是否整數 或者邊是否全相同/異無關嗎 01/22 17:59
→ ok8752665: ^的capacity 01/22 18:00
推 NCTUcs: 沒有查到其他的充分條件 感覺是只是考找反例的能力吧 01/22 18:26
→ mistel: 請問有題目可以看看嗎？ 01/22 18:55
→ ok8752665: 了解 感謝 01/22 19:30
推 mistel: 感謝 01/22 19:39
推 hsiehong: 想順便問一下 如果risitual network中沒有argument path 01/22 23:24
→ hsiehong: 了，那要如何確認目前的flow 是maximun flow呢？ 01/22 23:24
推 hsiehong: 如下面這個例子 01/22 23:26
→ ok8752665: residual network中沒有augmenting path 那其flow就是 01/22 23:38
→ ok8752665: maximum flow了阿 01/22 23:38
推 Aa841018: residual是反向，如果是max flow應該會有augmenting pat 01/22 23:49
→ Aa841018: h吧？ 01/22 23:49
→ Aa841018: 反而完全不流出的狀況，在resudual 當中才找不到augment 01/22 23:49
→ Aa841018: ing path吧？ 01/22 23:49
→ Aa841018: 因為完全不流出，自然沒有可以流回的path… 01/22 23:50
→ ok8752665: ? 有點不太懂你的意思 所以你是說flow是maximum flow時 01/22 23:56
→ ok8752665: 還會有augmenting path? 01/22 23:56
推 Aa841018: 我是這麼覺得，我概念有錯嗎？ 01/22 23:57
→ ok8752665: 完全不流出的情況 residual會等於原圖 就代表有路出去 01/22 23:57
推 hsiehong: 但上面左圖中flow是1，但實際上maximal flow是2啊 ,res 01/23 00:00
→ hsiehong: idual network中卻沒有augment path了 01/23 00:00
→ ok8752665: 對阿 所以你這張圖的residual沒有路出去了阿 01/23 00:00
→ ok8752665: 有阿 是看residual 右邊那張 還有sbat可以走阿 01/23 00:01
推 Aa841018: 抱歉我有點卡，原則上max flow將某個水管塞滿，那在resi 01/23 00:03
→ Aa841018: dual 當中不是應該可以流回與max flow同等的水流量嗎？ 01/23 00:03
→ Aa841018: 一個是正向出去（max flow),一個是逆向回來（residual) 01/23 00:03
→ ok8752665: 對阿 residual就是給你之後可以倒退的機制阿 01/23 00:07
→ ok8752665: maxflow就會讓你的residual 沒有augmenting path走啊 01/23 00:08
推 Aa841018: 那怎麼會說max flow 時residual 無路可走，max flow就代 01/23 00:13
→ Aa841018: 表送了最多水流過來了，那residual 當然可以逆向送同樣 01/23 00:13
→ Aa841018: 的水流回去，這樣算有路可走吧？ 01/23 00:13
推 Aa841018: 我好像有點懂了，所謂有augmenting path 指的是實線的 01/23 00:17
→ Aa841018: 邊，非虛線的邊對嗎？ 01/23 00:17
→ ok8752665: 先說你那張圖有畫錯 C->B 還有1可以走 然後實虛都能走 01/23 00:19
→ ok8752665: 所謂有augmenting path是指起點到終點有路可走 不是任 01/23 00:20
→ ok8752665: 兩點 01/23 00:20
→ ok8752665: 用你那張圖當例子 也可以發現沒有路從A到B吧 01/23 00:21
推 Aa841018: 謝謝說明（抱歉我突然卡進來狂問…） 01/23 00:21
→ ok8752665: 不會 希望你真的懂了 01/23 00:22