向上临界边和向下临界边

￡神魔★判官ぃ 2021-12-16 08:19 265阅读 0赞

1 给定一个流网络 G = (V, E)，如果我们提高其中一个

边 ei ∈ E 的容量就会提高这个网 络的最大流量，我们称这样的边 ei 为向上临界边。

是否每个流网络有一个向上临界边？简述一个算法鉴别每个网络 G 中的向上临界边，并简 要证明其正确性，分析它的最坏运行时间复杂度

2.给定一个流网络 G = (V, E)，我们如果降低其中一个边 ej ∈ E 的容量就会降低这个网 络的最大流量，我们称这样的边 ej 为向下临界边。

鉴别向上临界边和向下临界边的方法是否相同呢？如果不，简述一个算法鉴别每个网络 G 中的向下临界边，并简要证明其正确性，分析它的最坏运行时间复杂度

**1.**

不是每个流网络都有一个向上临界边。考虑一个简单的流网络只有a,b,c三个点，并且c(a,b) = c(b,c) = 1 ；那么此时提高一条边的容量不会提高这个流网络的容量。

鉴别向上临界边算法。

1）对于给定流网络G(V,E)，计算出一个最大流f，则由f诱导的G的剩余网络为Gf＝(V, Ef )。

2）设U是源点s可以达到的点的集合，V是可以达到汇点t的集合。

3）那么U和V中所有的点构成的边都是流网络G的向上临界边。

证明：对于满足上述条件的边，当我们提高其中一个边 ei ∈ E 的容量，都会产生一条增广路径，则此时会提高这个网络的最大流量。

算法最坏的时间复杂度：取决于求最大流网络使用算法的时间复杂度。

**2.**

不相同。

鉴别向下临界边算法。

1）计算出一个最大流f，则由f诱导的G的剩余网络为Gf＝(V, Ef )。

2）对其中两个点u，v，边(u,v)存在于流网络，而不在剩余网络。

3）此时边(u,v)是向下临界边。

证明：反证法。假设一条满足上述条件的边(u,v)不是向下临界边，则降低该边的容量不会降低这个网络的最大容量。又因为(u,v)是饱和的，其f((u, v)) =c((u, v)，若此时降低(u,v)的容量，即c((u, v)减少，则f((u, v))必定减少，则当前的最大容量必定减少，与假设矛盾。因此此时边(u,v)是向下临界边。

算法最坏的时间复杂度：还是取决于求最大流网络使用算法的时间复杂度，而对于找存在于流网络G，而不在剩余网络Gf的边(u,v)，遍历G中所有的边需要的时间复杂度最坏是O(E)，其一定是比求最大流网络使用算法的时间复杂度要小。因此总体来看，算法的时间复杂度最坏还是取决于求最大流网络使用算法的时间复杂度。

发表评论取消回复

表情：

评论列表（有 0 条评论，265人围观）

还没有评论，来说两句吧...

相关阅读

相关超超临界燃煤发电原理(超超临界发电技术究竟是什么)

所谓的”超超临界燃煤发电技术“也就是清洁燃煤发电技术。我国是煤炭大国，煤炭消费在我国能源消费中所占比较超过50%，在”双碳“的要求下，一方面需要降低对煤炭消费的依赖，而大力发展

浅浅的花香味﹌/ 2023年10月11日 21:24/ 0 赞/ 17 阅读

相关多线程—临界区

多线程—临界区：解决多个线程同时防访一个变量的解决方法。 include<stdio.h> include<stdlib.h> include<W

我会带着你远行/ 2022年09月24日 14:27/ 0 赞/ 174 阅读

相关操作系统之临界区浅析

什么是临界区？每个进程中访问临界资源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，进入后不允许其他进程进入。

电玩女神/ 2022年08月10日 09:52/ 0 赞/ 193 阅读

相关竞争条件和临界区

原文链接：[http://tutorials.jenkov.com/java-concurrency/race-conditions-and-critical-sections

深藏阁楼爱情的钟/ 2022年08月05日 00:57/ 0 赞/ 214 阅读

相关 LaTeX边学边用

表格：三线表：[http://blog.sina.com.cn/s/blog\_5e16f1770100fwi5.html][http_blog.sina.com.cn

﹏ヽ暗。殇╰゛Y/ 2022年06月11日 02:51/ 0 赞/ 265 阅读

相关 FreeRTOS 中断配置和临界段

中断屏蔽寄存器 PRIMASK、FAULTMASK和BASEPRI > 1.PRIMASK：这是个只有1个位的寄存器。当它置1时，就关掉所有可屏蔽的异常，只剩下 NMI

悠悠/ 2022年06月08日 07:12/ 0 赞/ 187 阅读

相关操作系统06-临界区

交错输出的没有绝对情况的如果同时访问共享的数据可能会破坏数据。对这样的事情加上防范！并发的程序访问共享的数据一定要注意。对一些问题敏感的洞察生产消

柔光的暖阳◎/ 2022年06月03日 00:56/ 0 赞/ 221 阅读

相关图的遍历中的树边，前向边，后向边，横叉边

树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行D

àì夳堔傛蜴生んèń/ 2022年05月16日 04:53/ 0 赞/ 264 阅读

相关向上兼容和向下兼容

向上兼容(Upward Compatible) 向上兼容 (Upward Compatible)，又称作向前兼容（Foreward Co

╰+哭是因爲堅強的太久メ/ 2022年03月26日 03:24/ 0 赞/ 743 阅读

相关向上临界边和向下临界边

1 给定一个流网络 G = (V, E)，如果我们提高其中一个边 ei ∈ E 的容量就会提高这个网络的最大流量，我们称这样的边 ei 为向上临界边。是否每个流网络有

￡神魔★判官ぃ/ 2021年12月16日 08:19/ 0 赞/ 266 阅读