图形算法和网络流

图形算法和网络流图形算法和网络流1. 介绍将图看成一个网络：它的边上负载着某种流，如水流、电流、数据流或其他类似的流。那么，我们应该如何准确的建立这一模型呢？首先，我们需要知道通过每条边e=xy的流量以及流向。在模型中，我们给顶点对（x,y）赋值一个正整数k，来表示存在k个单位的流x经过e流向y；或者给（x,y）赋值-k来表示e上有k个单位相反方向的流。即从y流向x。对于这样的赋值: 和G中任意两个相邻的点x和y，有。通常情况下，在网络中，流只从少数几个节点流入或流出，而在所有其他节点，流入总量与流出总量相等。在我们的模型中，这意味着在大多数节点x，函数满足Kirchhoff定律。而这一章，我们将满足以上两个性质的任意映射：称为图G上的一个“流”。有时，我们会用其他群取代Z，通常我们考虑的图都是多重图。事实上，“流”的理论不仅对显示中的流模型行之有效，而且它与图论的其他部分有着一些深刻和令人惊讶的联系，尤其是与连同性和着色问题。1.1环流令是一个（无向）多重图，G的每条边e=xy有两个方向（direction）（x,y）和（y,x）。（如果e是一个还，这两个方向是一样的，所以环只有一个方向。）一条边和它的一个方向所组成的三元组（e,x,y）叫做一个定向边。对应于e的定向边是它的定向，记为和，所以，但通常我们不知道哪一个是哪一个，我们把所有定向边的集合记为：我们把中的元素表示为，等等，即使还没有定义边e，而“e”用来表示它对应的无向边。对于任意定向边的集合，令注意到本身是对称的：对任意两个顶点集X, （不一定不相交）和，定义将简写为,并且记这里，表示顶点集的补注意，在和的定义中，不考虑在顶点处的环。设H的加法意义下具有零元0的阿贝尔半群，给定顶点集X, （不一定是不相交的）和函数令 （1）同样地，我们将记作,等等。从现在开始，我们假设H是一个阿贝尔群。若f满足下面两个条件：（F1）对任意具有的，有；（F2）对任意有则称f是图G上的一个（取值自H的）环流如果f满足（F2），则从这两个基本性质中不难看出，在环流中，穿过任意一个割的净流量为零。命题1.1.1 如果f 是一个环流，那么对任意集合，有。证明:由于桥本身就是割，故命题1.1.1蕴含着桥上的环流总为零。推论1.1.2 如果f是一个环流且是G中一个桥，则2. 网络中的流这一节我们将简要地介绍一些网络流理论，它是目前匹配和连通性领域中的标准证明技巧。通过例子，我们来证明这一理论中的经典结果，即由Ford和Fulkerson得到的最大流最小割定理。只用这一定理便可毫不费力地的得到Menger定理，由此可见该方法的巨大威力。考虑一个具有初始点s和终点t的网络模型，这里通过任意两个节点的连线上的流量不大于该连线的固定容量。我们的目的是确定该网络中从s流向t的最大净流量。由于各种原因，我们同时取决于网络的结果以及它的连接之间的各种容量，而这个最大净流量具体是多少，则正是我们想要找出的。令G=（V,E）为多重图，s，为两个固定顶点，且为一个映射；我们称c为G上的一个容量函数，而称四元组N:=（G,s,t,c）为一个网络。注意到，c对一条边的两个方向是单独定义的。如果一个函数f:满足以下三个条件（图1.）就称它为N上的一个流。（F1）对满足的所有，有；对所有有；（F3）对所有,有。若f的所有取值为整数，我们称f是整数的图1 网络流的简单记法：所有的赋值均表示在给定方向上的流量（容量没有显示）设f 是N中的一个流，若满x足和，则称集合对是N中的一个割，而是这个割的容量。由于现在f只需要满足而不必满足（F2），那么不必要求所有的满足（如命题1.1.1中所叙述的那样）。然而，所有割的取值是相同的；命题1.2.1 N中的任意割满足证明 同命题1.1.1的证明一样，我们有命题1.2.1中所有的公共值被称为的总流量，并记为，图1.2.1中所示的流的总流量为3根据（F3），对N中的每个割，有因此N中一个流的总流量绝不会超过一个割的最小容量。下面的最大流最小割定理表明，这一上届总能在某个流上达到：定理1.2.2 在每个网络中，流的最大总流量等于割的最小容量。证明 令N=(G,s,t,c)为一个网络，且G=：（V,E）。我们将定义N中的一个整数流序列使得总流量是严格递增的，即显然，整数流的总流量之和仍然为整数，因此事实上对所有n有因为所有这些值被N中任意割的容量所限制，所有我的序列总会终止于某个流与这个流相对应，我们将会找到一个容量为的割。由于任何流的总流量不会超过且任意割的容量为的割。由于任何流的总流量不会超过，且任意割的容量不会少于所以这个数值正是定理中提到的最大值和最小值。对和所有，令在N中对某个已经定义了整个数据流后，我们用来表示所有顶点v的集合，这里v使得G包含一条s=v途径且满足对所有有其中（当然，且）若令为相应的s-t途径；不失一般性地，假定W中不重复任何顶点，令则又因为根据假设（如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 每个（具有整数容量函数的）网络都包含一个最大总流量为整数的流。3. 群上的流设G=（V,E）是一个多重图，若f和g是G的取决于同一个阿贝尔群H上的两个流，那么和也是环流，于是G上取值于H的环流很自然地构成了一个群。在我们所用的术语中，是指一个处处非零（即，对所有的有）的环流f: 注意到，G上H-流的集合在加法意义下并不封闭：如果在某条边上两个H-流相加为零，则它们的和不再是一个H-流。根据推论1.1.2包含H-流的图不可能有桥。对有限群H来说,G上的H-流的数目，尤其是他们的存在性，令人非常吃惊地只取决于H的阶数，而并不取决于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-流。因为当所有边为环时有所有存在个这样的映射，且是即为所需要的多项式。现在假设存在一条边不是环，令且考虑多重图根据归纳假设，存在多项式使得对于任意有限阿贝尔湖群H和上的H-流的数目为我们将证明G上H-流的数目等于则是要找的多项式。设H已给定，并记G上全体H-流的数目为我们将证明G上H-流的数目等于则是要找的多项式。设H以给定，并记G上全体H-流的集体为F，我们将尝试证明 （1）G1上的H-流恰好是那些仅在流量为零，而且其他所有边上流量非零的G的H-环流限制在上所得到的，我们记G上这样的环流所构成的集合为则类似地，我们的目标是证明上的H-流一一对应与那些仅可能在上流量为零的G上的H-环流，那么G上这样的环流构成的集合满足且是和F的不并交。这就验证了（1），进而证明了定理。在中，令为收缩后的顶点。我们要在和由上的限制，（由于x-y边在中变成了环，所以它们在中只有一个定向我们取作为它的g-值）那么g确实是上的H-流。注意到，根据命题1.1.1,取则（F2）对G在成立。图3 收缩边的结果剩下的就是证明映射是双射.如果已给定上的H-流g，而且我们想找到一个满足的则对所有由于故以确定；根据（F1），对所有从而有这样，映射是双射当且仅当对于给定的g，总存在唯一的方法来定义和余下的值，使得f对满足（F1），对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-流的存在性证明中，关键难点不涉及群理论的本质。另一方面，允许选择一个方便好用的群将会很有用；对此，用命题1.4.5中，我们将会看到一个这方面的好例子。设为整数，而G=（V,E）为多重图，G上满足对所有均有的Z-流f被称为k-流。显然，对所有，任意k-流也是l-流。所以我们会问，使得G有一个k-流的最小整数k是多少呢（假设这样的k存在）？我们称这样的最小的k为G的流数，并记为若对任意k.G中不存在k-流，我们令确定流数的问题很快就涉及图论中一些最深刻的为公开问题，我们将在本章晚些时候对这些问题进行讨论。然而，首先还是让我们来看看k-流与H-流的更广义概念的联系。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-流当且仅当它有，即当且仅当取值为的常值映射满足（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=xy(),取和而定义的映射是G上的。那么，根据定理1.3.3，G有一个3-流完全图的流数是多少呢？对奇数n1,由命题1.4.1我们有此外，这些都可以很容易地由命题1.4.2和6.4.5直接得到。有