作者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/cn.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