求助,网络流练习
  • 板块学术版
  • 楼主schtonn
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/3/15 21:14
  • 上次更新2023/11/5 02:00:50
查看原帖
求助,网络流练习
95027
schtonn楼主2021/3/15 21:14

今天我读书的时候发现一道练习题很有趣:

它给出了一个计算网络最大流的算法(假的),大意是只寻找增广路,不连反向边,一直增广无法增广为止。可以证明求出的不一定是最大流。

但是它提出了这样一个命题:

在任意网络上,不论何种情况(不管算法怎样遍历),总有一个常数 b1b\geq1,使得上述算法算出的最大流一定大于等于真正的最大流的 1b\frac{1}{b}

要求证实或证伪。

于是我画了一个熟悉的图:

不难看出这个图里无论把 999999 改到多大,最后计算出的假最大流一定大于真最大流的 12\dfrac{1}{2},但是蒟蒻想不出更多的思路了,书里也没有答案qwq

求问大佬们qwq

2021/3/15 21:14
加载中...