设 G = (V,E) 是一个二分图,其结点划分为 V = L∪U,设 G′ = (V′,E′) 为其对应的流网 络。在 Ford-Fulkerson 执行过程中,对在 G′ 中找出的任意增广路径的长度给出一个合适的上界。
时间: 2023-07-15 10:11:41 浏览: 52
在 Ford-Fulkerson 算法中,我们需要通过不断地寻找增广路径来不断地增加流量,直到无法找到增广路径为止。因此,一个合适的增广路径长度的上界是非常有用的。
首先,我们可以注意到,对于一个二分图 G,它的最大流最多只能达到 |L|×|U|。这是因为,对于任意一条从 L 到 U 的路径,最多只能流过一单位的流量。因此,在每次增广时,我们最多只能增加 1 的流量。因此,如果我们设初始流量为 0,那么当流量达到 |L|×|U| 时,算法一定会终止。
接下来考虑如何给出一个更紧确的上界。我们可以使用最短增广路径算法,即每次寻找增广路径时,我们选择当前权重最小的路径。在这种情况下,我们可以证明,最短增广路径的长度上界为 2|V| - 1。
证明如下:
假设我们有一个最短增广路径 P,其长度为 k。因为这是一个增广路径,所以我们可以将其看做一个交替路径,即 P = (s, v1, u1, v2, u2, ..., vk-1, uk-1, vk)。其中 s 是源点,v1,v2,...,vk-1 是 L 中的结点,u1,u2,...,uk-1 是 U 中的结点,而 vk 是汇点。
我们可以将这个交替路径分成两个部分:
- 从源点 s 开始,走到 v1 的路径 P1。
- 从 vk-1 开始,走到汇点 t 的路径 P2。
由于这是一个最短增广路径,所以对于任意一条增广路径 P',其长度一定不小于 k。因此,我们可以将 P' 分成两个部分 P'1 和 P'2,使得 P'1 和 P1 相连,P'2 和 P2 相连。这是因为如果 P'1 和 P1 不相连,那么从 s 到 P'1 再到 P1 的路径长度就小于 k,不符合最短增广路径的定义。
同样地,如果 P'2 和 P2 不相连,那么从 P'2 到 t 再到 vk 的路径长度也小于 k,也不符合最短增广路径的定义。因此,我们可以将 P' 分成这样的两个部分。
由于 P1 和 P2 中的结点都不在同一侧,因此它们之间至少有一个交点。假设交点是结点 x,它在 P1 中的位置是 i,而在 P2 中的位置是 j。因为 P 是一个交替路径,所以 i+j=k-1。
现在我们来考虑结点 x 的度数。因为 x 在 P1 和 P2 中都出现了,所以它的度数至少为 2。如果它的度数大于等于 3,那么我们可以找到另外一条增广路径 P',其中 P'1 和 P1 相同,但是 P'2 不同于 P2。我们可以通过将 P2 中的结点 x 换成它相邻的另外一个结点 y,来构造这样的 P'2。因为 x 的度数大于等于 3,所以一定存在这样的结点 y。因此,P' 的长度不小于 k,这与 P 是最短增广路径的定义矛盾。
因此,我们得出结论:结点 x 的度数不能大于等于 3。因为 x 在 L 中,而 L 中的结点之间没有边相连,所以 x 的度数只能为 2。
现在我们来考虑最坏情况。假设我们有一个包含了所有结点的二分图,即 |L|=|U|=|V|/2。在这种情况下,对于每个结点 x∈L,它的度数都是 2。因此,我们可以将交替路径 P 分成 |L| 条路径,每条路径都包含一个 L 中的结点和一个 U 中的结点。因为一共有 |V| 个结点,所以最多有 |V|/2 条这样的路径。因此,最短增广路径的长度上界为 2|V|/2=|V|。
综上所述,我们得出最短增广路径的长度上界为 2|V| - 1。在 Ford-Fulkerson 算法中使用这个上界,可以加快算法的收敛速度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)