图形算法和网络流.doc

1、图形算法和网络流1图形算法和网络流1.介绍将图看成一个网络：它的边上负载着某种流，如水流、电流、数据流或其他类似的流。那么，我们应该如何准确的建立这一模型呢？首先，我们需要知道通过每条边 e=xy 的流量以及流向。在模型中，我们给顶点对（x,y）赋值一个正整数 k，来表示存在 k 个单位的流 x 经过 e 流向 y；或者给（x,y）赋值-k 来表示 e 上有 k 个单位相反方向的流。即从 y 流向 x。对于这样的赋值 : 和f2VZG 中任意两个相邻的点 x 和 y，有 。(,)(,)fxf通常情况下，在网络中，流只从少数几个节点流入或流出，而在所有其他节点，流入总量与流出总量相等。在我们的模

2、型中，这意味着在大多数节点 x，函数 满足 Kirchhofff定律。 y(),0Nxf而这一章，我们将满足以上两个性质的任意映射 ： 称为图 G 上的一个“流” 。f2VZ有时，我们会用其他群取代 Z，通常我们考虑的图都是多重图。事实上， “流”的理论不仅对显示中的流模型行之有效，而且它与图论的其他部分有着一些深刻和令人惊讶的联系，尤其是与连同性和着色问题。1.1环流令 是一个（无向）多重图，G 的每条边 e=xy 有两个方向（direction）(,)VE（x,y）和（y,x） 。 （如果 e 是一个还，这两个方向是一样的，所以环只有一个方向。 ）一条边和它的一个方向所组成的三元组（e,x

3、,y）叫做一个定向边。对应于 e 的定向边是它的定向，记为 和 ，所以 ，但通常我们不知道哪一个是哪一个，我们e,(,),xye把所有定向边的集合记为： :(,)|;,;eEExyVx我们把 中的元素表示为 ， 等等，即使还没有定义边 e，而“e ”用来表示它对应的无Ee向边。图形算法和网络流2对于任意定向边的集合 ，令FE:|eF注意到 本身是对称的： 对任意两个顶点集 X, （不一定不相交）和 ，EYVFE定义 (,):(,)|yxFXYexyFX； ；将 简写为 ,并且记(x,)FYx():,)=(,)Vx这里， 表示顶点集 的补 注意，在 和 的定义中，不考虑在顶点XVX,FY(处的环

4、。xY设 H 的加法意义下具有零元0的阿贝尔半群，给定顶点集 X, （不一定是不相交V的）和函数 令:fE（1）e(,)(,):EXYff同样地，我们将 记作 ,等等。(x,)FYx从现在开始，我们假设 H 是一个阿贝尔群。若 f 满足下面两个条件：（F1）对任意具有 的 ，有 ；y(,)eE(,)(,)exyfex（F2）对任意 有vV0f则称 f 是图 G 上的一个（取值自 H 的）环流如果 f 满足（F2） ，则 (,)0xXffV（ ,） =从这两个基本性质中不难看出，在环流中，穿过任意一个割的净流量为零。命题1.1.1 如果 f 是一个环流，那么对任意集合 ，有 。(,)0fX证明:

5、 (,)(,)0fXVfX（ ,） =由于桥本身就是割，故命题1.1.1蕴含着桥上的环流总为零。推论1.1.2 如果 f 是一个环流且 是 G 中一个桥，则exy(,)0fexy2.网络中的流图形算法和网络流3这一节我们将简要地介绍一些网络流理论，它是目前匹配和连通性领域中的标准证明技巧。通过例子，我们来证明这一理论中的经典结果，即由 Ford 和 Fulkerson 得到的最大流最小割定理。只用这一定理便可毫不费力地的得到 Menger 定理，由此可见该方法的巨大威力。考虑一个具有初始点 s 和终点 t 的网络模型，这里通过任意两个节点的连线上的流量不大于该连线的固定容量。我们的目的是确定该

6、网络中从 s 流向 t 的最大净流量。由于各种原因，我们同时取决于网络的结果以及它的连接之间的各种容量，而这个最大净流量具体是多少，则正是我们想要找出的。令 G=（V,E）为多重图，s ， 为两个固定顶点，且 为一个映射；我们称tV:cENc 为 G 上的一个容量函数，而称四元组 N:=（G,s,t,c ）为一个网络。注意到，c 对一条边的两个方向是单独定义的。如果一个函数 f: 满足以下三个条件（图1.）就称它为 NER上的一个流。（F1）对满足 的所有 ，有 ；xy(,)exy(,)(,)fexyfex对所有 有 ；(2)Fv,Vst0fv（F3）对所有 ,有 。eE()ce若 f 的所有

7、取值为整数，我们称 f 是整数的图1 网络流的简单记法：所有的赋值均表示在给定方向上的流量（容量没有显示）设 f 是 N 中的一个流，若 满 x 足 和 ，则称集合对 是 N 中的一SVsSt(,)S个割，而 是这个割的容量。c(,)S由于现在 f 只需要满足 而不必满足（F2） ，那么不必要求所有的 满足(2)F XV（如命题1.1.1中所叙述的那样） 。然而，所有割的取值是相同的；(,)0fX命题1.2.1 N 中的任意割 满足(,)S(,)(,)fSfsV图形算法和网络流4证明 同命题1.1.1的证明一样，我们有 v(,)(,)(,)0(,)SffVfsf命题1.2.1中所有 的公共值被

8、称为 的总流量，并记为 ，图1.2.1中所示的流(,)fSf f的总流量为3根据（F3 ） ，对 N 中的每个割 ，有(,)Sc(,)fS因此 N 中一个流的总流量绝不会超过一个割的最小容量。下面的最大流最小割定理表明，这一上届总能在某个流上达到：定理1.2.2 在每个网络中，流的最大总流量等于割的最小容量。证明 令 N=(G,s,t,c)为一个网络，且 G=：（V,E） 。我们将定义 N 中的一个整数流序列使得总流量是严格递增的，即012,.f 012.ff显然，整数流的总流量之和仍然为整数，因此事实上对所有 n 有 因为所1nf有这些值被 N 中任意割的容量所限制，所有我的序列总会终止于某

9、个流 与这个流f相对应，我们将会找到一个容量为 的割。由于任何流的总流量不会超过 且ncf nc任意割的容量为 的割。由于任何流的总流量不会超过 ，且任意割的容量不ncf nc会少于 所以这个数值正是定理中提到的最大值和最小值。nf对 和所有 ，令 在 N 中对某个 已经定义了整个数据流 后，0eE0():fennf我们用 来表示所有顶点 v 的集合，这里 v 使得 G 包含一条 s=v 途径 且满nS 01.ex足对所有 有i()niifec其中 （当然， 且 ）1=(e,x)iii： 0xslv若 令 为相应的 s-t 途径；不失一般性地，假定 W 中不重复任ntS01.lWe图形算法和网

10、络流5何顶点，令则 又因为根据假设 （如 c）为整数，所以 是一个整数，令直观上看， 是 沿 W 从 s 向 t 多发送了 个单位的流而得到的（ 1.2.2）图2 对于常数流 和 c=3，具有增量 的“增光路”W显然， 也是 N 中一个整数流，我们计算一下它的总流量由于 W 仅包含顶点 s 一次， 是唯一满足其 f-值改变过并使得 x=s 且 的三元组（e,x,y） 。这个值（从而 的值）增大了。因此， 即所要证的。若 则 是 N 中的一个割。对 使用（F3）并根据 的定义，故对所有 有因此即所要证的因为定理1.2.2的证明中所构成的流是整数的，我们同时还证明了以下结论：推论1.2.3 每个（

11、具有整数容量函数的）网络都包含一个最大总流量为整数的流。3.群上的流图形算法和网络流6设 G=（V,E）是一个多重图，若 f 和 g 是 G 的取决于同一个阿贝尔群 H 上的两个流，那么 和 也是环流，于是 G 上取值于 H 的环流很自然地构成了一个群。在我们所用的术语中， 是指一个处处非零（即，对所有的 有）的环流 f: 注意到，G 上 H-流的集合在加法意义下并不封闭：如果在某条边 上两个 H-流相加为零，则它们的和不再是一个 H-流。根据推论1.1.2包含 H-流的图不可能有桥。对有限群 H 来说,G 上的 H-流的数目，尤其是他们的存在性，令人非常吃惊地只取决于 H 的阶数，而并不取决

12、于 H 本身：定理1.3.1 对每个多重图 G，存在一个多项式 P 使得对任意有限阿贝尔群 H，G 上 H-流的图不可能有桥。对有限群 H 来说，G 上 H-流的数目，尤其是它们的存在性，令人非常吃惊地只取决于 H 的阶数，而不取决于 H 本身：定理1.3.1 对每个多重图 G，存在一个多项式 P 使得对任意有限阿贝尔群 H,C 上 H-流的数目是证明 令 对 使用归纳法。我们先假定 G 的所有边均为环。那么，给定任意有限阿贝尔群 H，每个映射 是 G 上的一个 H-流。因为当所有边为环时有 所有存在 个这样的映射，且 是即为所需要的多项式。现在假设存在一条边 不是环，令 且考虑多重图根据归纳

13、假设，存在多项式 使得对于任意有限阿贝尔湖群 H 和上的 H-流的数目为 我们将证明 G 上 H-流的数目等于则 是要找的多项式。图形算法和网络流7设 H 已给定，并记 G 上全体 H-流的数目为 我们将证明 G 上 H-流的数目等于则 是要找的多项式。设 H 以给定，并记 G 上全体 H-流的集体为 F，我们将尝试证明（1）G1上的 H-流恰好是那些仅在 流量为零，而且其他所有边上流量非零的 G 的 H-环流限制在 上所得到的，我们记 G 上这样的环流所构成的集合为 则类似地，我们的目标是证明 上的 H-流一一对应与那些仅可能在 上流量为零的 G上的 H-环流，那么 G 上这样的环流构成的集

14、合 满足且 是 和 F 的不并交。这就验证了（ 1） ，进而证明了定理。在 中，令 为 收缩后的顶点。我们要在 和由 上的限制， （由于x-y 边 在 中变成了环，所以它们在 中只有一个定向 我们取作为它的 g-值）那么 g 确实是 上的 H-流。注意到，根据命题1.1.1,取则（F2 ）对 G 在 成立。图3 收缩边 的结果剩下的就是证明映射 是双射.如果已给定 上的 H-流 g，而且我们想找到一个满足 的 则对所有 由于 故 以确定；根据（F1 ） ，对所有 从而有 这样，映射 是双图形算法和网络流8射当且仅当对于给定的 g，总存在唯一的方法来定义 和 余下的值，使得 f 对满足（F1 ）

15、 ，对 x 和 y 满足（F2 ）现在， 的取值可根据在 x 的（F2）以及 x 关联的边 e 上已知的值 来确定，而 的取值可根据在 y 的（F2）以及与 y 关联的边 e 上已知的值 来确定。的确，假设和 那么（F2）对 f 成立当且仅当以及亦即，当且仅当我们取幸运的是，这样定义的 和 对 f 同样满足（F1）这是因为 g 在 应用(F2),有定理6.3.1中的多项式 P 被称为 G 的流多项式。推论1.3.2 如果 H 和 是两个具有相同阶的有限阿贝尔群，那么 G 有 H-流当且仅当 G有推论1.3.2对代数流理论来说有深刻的影响：它表明在 H-流的存在性证明中，关键难点不涉及群理论的本

16、质。另一方面，允许选择一个方便好用的群将会很有用；对此，用命题1.4.5中，我们将会看到一个这方面的好例子。设 为整数，而 G=（V,E ）为多重图，G 上满足对所有 均有的 Z-流 f 被称为 k-流。显然，对所有 ，任意 k-流也是 l-流。所以我们会问，使得 G 有一个 k-流的最小整数 k 是多少呢（假设这样的 k 存在）？我们称这样的最小的 k 为 G 的流数，并记为 若对任意 k.G 中不存在 k-流，我们令图形算法和网络流9确定流数的问题很快就涉及图论中一些最深刻的为公开问题，我们将在本章晚些时候对这些问题进行讨论。然而，首先还是让我们来看看 k-流与 H-流的更广义概念的联系。

17、k-流与 之间存在着十分紧密的联系。让 便是从 Z 到 的自然同态通过结合 每个 k-流定义了一个 正如下面的定理所示，逆命题也成立：从G 上每个 我们可以构造 G 上的一个 。考虑到推论1.3.2这意味着对任意群H，H-流的存在性问题可归结为相应的 k-流问题。4.具有较小 k 值的 k-流平凡地，一个图有1-流（空集）当且仅当它不含边。在这一节，作为简单的例子，我们会手机若干关于图包含2-，3-或4-流的充分条件。更多例子可在练习中找到。命题1.4.1一个图有2-流当且仅当它的所有度数为偶数。证明 根据定理 1.3.3，图 =（V,E）有2-流当且仅当它有 ，即当且仅当取值为的常值映射 满

18、足（F2） ；这一条件当且仅当所有度数为偶数。在本章余下部分，若一个图的所有顶点度数偶数，我们就称它是偶的。命题1.4.2 一个三正则图有3-流当且仅当它是二部图。证明 设 G=（V,E ）是一个三正则图，我们首先假定 G 有一个3-流，因此也有一个f。我们证明 G 中任意一个圈 的长度为偶数。考虑 C 上两条连续边，比如 和 如果 f 把 C 中的前向边赋相同的值，即如果，那么与 关联的第三条边的任意非零赋值都不能使 f在 满足（F2 ） 。因此， f 给 C 上的边交错地赋值 和 特别地，C 的长度为偶数。反过来，令 G 的一个二部图，其顶点划分为X,Y因为 G 是三正则的，故对所有的边e

19、=xy( ),取 和 而定义的映射 是 G 上的。那么，根据定理1.3.3，G 有一个3-流完全图 的流数是多少呢？对奇数 n1,由命题1.4.1我们有 此外，这些都可以很容易地由命题1.4.2和6.4.5直接得到。有趣的是，图形算法和网络流10是唯一一个流数为4的完全图：命题1.4.3 对所有偶数 n4的图 都有一个3-流。作为归纳法的开始，考虑 n=6，则 G 是三个边不交图 的并，其中123,G而 显然， 和 都有2-流，而由命题 1.4.2知， 有3- 流，那么这些312,GK3,12流的并是 G 上的一个3-流。现在令 并假设结论对 n-2成立，显然，G 是 和图 的边不交的并，n6 n-2K(,)VE其中 根据归纳假设 有3-流。由定理1.3.3我们只需要找到 上的一个-2*Kn-2KG；其中 是 在 G 中的边。令 是这些流之和。显然，除了3Z流 exy2和 之外， 处处为零。若 则 f 即为所需的 上的 ；若,exy（ ） ,（ ） f(,)0fexy3Z流，则 （对任意 z）是 上的。()=0f zf