计算图中的最大对集的匈牙利方法

1、计算图中的最大对集的匈牙利方法背景知识介绍在一个网络中往往要求计算其中的最大对集。是由匈牙利人Egervary于1931年发现，后被另外一个匈牙利人Edmonds所推广（到一般图中的“开花算法”）基本方法利用反圈法第一节 二部图中最大对集的有效算法设为一个二部图，是中一个对集。型节点-位于的节点；型节点-位于中的节点；-边-位于中的边；注意：一个增广路的长度为奇数，所以这样的路的两个端点必须是同型节点。反圈法基本原则-（1）初始时，令；（2）在中选边时，必须按照以下原则：(a)如果时，则选取以为端点的非边（即，在型节点处只选非边）；(b)如果 ，则选取以为端点的边（即，在型节点处只选边）（3）

2、若在某一步，出现下述情况之一时算法要终止：情况1。中有非饱和的型节点（此时得到一条关于的增广路）；情况2.。情况1不出现，且中无边可选（此时中不存在关于的增广路）。定理1.当匈牙利算法结束时，得到一个最大对集解答：下面我们来证明这个方法（算法）的正确性。如果情况1发生，根据我们算法特点，每一步上都是森林，其中每一个树都是以中的一点为根的。根据的定义，每一个树以一个非饱和的型节点为根。按照选边原则（2）可以看出：每一个树上，根与任意节点之间的唯一的路是交错路、。所以，当某个非饱和的型节点属于时，这个树上联接根节点与它的路是一个长度为奇数的增广路。现在假定情况2出现。我们用表示此时的（一定要记住：

3、中的每一个节点都位于一个树中）。令记其几何意义如图所示：（注意：这是其中一种结构，也是最重要的结构，即，假定对集中所有边都被包含在以为根的树中）。结论1.所有非饱和的型节点都在中（这是根据的定义得到的。表明：每一个这样的非饱和型节点都是一个树的根，这个树有可能退化为一个节点！）；结论2。所有的非饱和的型节点都在中（否则，选边原则（1）可得到增广路）；结论3.（前提是：连通）事实上，如果有使得，则因为，知道如果则是可选边（事实上此时有增广路联接与中点），与情况2的定义相违背；如果，则，必然有使得，与是对集相违背。结论4. （这个显然成立）注意：上述图形仍有地方要知道：中含有未被饱和的非根节点（因

4、此，）注意：上述的有些东西可能描述的不太精确。我们下面详细说明。记住当前算法执行到情况2，无法选边而且情况1不发生。可选边时有两种选法：沿着对集中的边向下走，沿着非中边向上走。（1）：将对集分成两类：和，其中是以中的节点为根的树中所能包含的边形成的子对集，而则是无法被这些树所含有的子对集（可以为空集）；（2）对集所能饱和的的节点集合为，没有被饱和的节点集合为（3）；（4）（这是由于无法选边决定的，否则，有些子树可以长大）；（5）（理由同上）。这样，结论1.所有非饱和的型节点都在中（这是根据的定义得到的。表明：每一个这样的非饱和型节点都是一个树的根，这个树有可能退化为一个节点！）；结论2。所有的

5、非饱和的型节点都在中（否则，选边原则（1）可得到增广路）；结论3. ；结论4.结论5.。（这是由图的连通性决定的）结论6. ；这样一来，若中存在增广路，那么它的一个端点在中，另外一个端点在中。显然此时可以选边使得对集增大。矛盾。因此，当情况2发生时当前的对集是最大的。注意：从上述分析中可知，我们的讨论可以假定。分析中得到的结构（结论1-6）非常有用，我们可以直接利用它们来计算。定理2.任何一个使得的二部图中一定有一个最大对集饱和所有最大次节点。点评：如果这个结果成立，那么这个图一定是第一类的（即，边色数。）解答：设是这样一个最大对集，它所饱和的最大次节点最多。我们将要证明：为所求。若不然，则存

6、在一个最大次节点，没有被所饱和。不妨设可以取使得是唯一一个未被饱和的最大次节点。对于这个执行匈牙利算法。可知情况2一定出现（即，无边可选的结构一定出现）。注意到上述结论1-结论6暗示：。此时一定有一个节点不是最大次的。不然，则有，这与相悖（这里利用了性质：中非根节点的领域全部被包含在）。设不是最大次节点，记为执行匈牙利算法终止时得到的交错树里面唯一的-路。意见它的长度为偶数。令，则也是最大对集，它饱和最大节点数目比多（事实上，饱和了，但是没有饱和。这正是我们需要的；同时，前面中其他节点还是被所饱和）。这与定义相违背。点评：关于这个结果有许多证明。我们将要提供另外一个富有技巧性的证明（但是说真的

7、，我不喜欢这种过于简短的证明，因为它们往往掩盖了很多的事物真相!）。例3. 如果二部图G中节点次数的最大值是，那么可以将它的边进行着色，每一条边染这中颜色中的一种，使得同一个节点引出的边颜色不同。解：如果G是正则图，则由Hall定理知道结论成立。否则，G不是正则图。我们可以将G扩展成为一个正则二部图（即，是的子图）如下：增加一些节点使得G的两部分的节点数目相同，然后在两部分之间尽可能地连边，直到。再连一条边则最大次数就超过为止。这样得到的图一定是正则图。理由如下：因为若有的次数小于，则总边数，从而必有的次数小于。于是可以连边而不破坏的最大性。根据上面所讲，可以对的边进行着色，使得每一种颜色的边

8、恰好是一个完美对集。在此结构下，的边也相应地被染上了种颜色，使得每一种颜色的边形成一个对集。点评；这个例子表明：如果一个二部图的最大次为，则其中一定有对集饱和所有最大次节点。这个对集可以是最大的。推论4.每一个正则二部图一定有1-因子。下面要用匈牙利算法终止时得到的结构来证明著名的Konig定理和Hall定理。定理5(Konig,1931) 对于任何二部图，最小节点覆盖阶数=最大对集阶数。证明：设是一个最大对集，是最小覆盖集合的阶数。容易看出：根据我们在对当前的执行匈牙利算法时，一开始就无边可选。于是，就有前面图形所示结构，那里有以下事实：这里，。可以看出：是一个覆盖，从而必有。证明完毕。注意

9、到，对于任何的子集，形成一个覆盖。推论6.对于任何二部图，最小节点覆盖阶数=最大对集阶数=如果中有对集饱和中所有节点，那么自然有（Hall条件）成立。反过来，假定上述条件成立，一定有最大对集饱和中所有节点。推论7（Hall定理1935）对于任何二部图，存在对集饱和中所有节点的充分必要条件是：注意：组合学中有几个著名的“max=min”-型定理：Menger定理，Hall定理，Konig定理以及Dilworth定理。它们在本质上都是等价的，以后我们还要介绍它们之间的相互推导。第二节 一般图中的最大对集值Edmonds开花算法。基本想法-将二部图中的匈牙利算法推广到一般图。首先我们来回顾一下我们在

10、二部图中始怎么做的。给定一个二部图和一个对集，算法开始时，令是所有非饱和的型节点集合。一般地，设已经有。我们在中开始选边，选边的原则是：在型节点处选非边，在型节点处选边；把被选到的边放入到中去，得到。放入节点时会有两个情况发生：若有某个非饱和的型节点在中，则得到增广路；否则继续选边过程。若在某一步，没有边可以选择，则说明没有增广路，当前的便是最大对集。在前一节的匈牙利算法执行过程中，所有被选边生成的子图是由个交错树组成的森林。每一个交错树恰好有一个非饱和节点（是型节点）。形象地讲，匈牙利算法的执行过程就是以中每一个节点为根的交错树的生长过程。扩大交错树的方式有两种：一是选入一条边（图（a）；一

11、是选入一条非边，而这条边在中始饱和的（图（b）。在这两种情况下，我们称此时的交错树为可扩的。若被选入的非边在中始非饱和节点（图（c），这个交错树中有一个增广路，这个树称为增广树。若增广树即不是可扩的，也不是增光的，我们就称其为匈牙利树（图(d)）。每一个匈牙利树种必有奇数个节点，其中仅有根节点为非饱和节点下面我们来把上述算法改造一下，以便可以适用于一般图。开始时，令为所有未饱和节点并且记它们为型节点。选边原则不变。当选一条非边时，把它在中的端点记为型节点；当选一条边时，把它在中端点记为型节点。整个过程仍然是扩大交错树，或者得到增广树，或者得到匈牙利树。不过要注意的是：这是的增广树除了上述所讲的

12、一种形式以外（图(c)），还有一种可能：它可能由两个交错树“合并”而成的，即，当两个交错树的两个型节点之间有非边相连，或者两个型节点之间有边相连时，也会产生增广树（下图(a),(b)）.此时必须随时检验这种情况是否会出现。为了避免这种检验，我们可以任取一个非饱和节点作为。当以它为根的交错树成为了匈牙利树后，再任取另外一个非饱和节点放入（令它为型节点）。继续做下去，就是说，在执行过程中，总是某一个交错树，只是在这个树不可扩大时，即成为匈牙利树以后，才去扩大另外一个交错树。这个原则对于下面要介绍的一般图的情况也是一样适用。我们知道，非二部图中会有奇圈。Edmonds在1965年对匈牙利算法做了一个

13、十分重要的写该，从而克服了从二部图到一般图时出现的困难。首先介绍所谓“花”的概念。给定图是它的一个对集。若是其中一个奇圈，使得上恰好有条边。因此有唯一一个节点，它在中的两条关联边均不是边。设是一条交错路，其中是关于的非饱和节点，是长度为偶数的路，。我们称由路与奇圈所成的子图是一个花型结构（注意：可以是1，这时，不是饱和节点）。由生成的子图，成为花苞，为花托，是花柄，是花根。结论1。设是一个花型结构。显然，从的根到花苞上任何一点有一条长度为偶数的交错路。Edmonds 的做法是：在执行匈牙利算法扩大交错路的过程中，一旦发现花型结构，则在图中收缩花苞，得到一个伪节点。令这个伪节点为-型节点，然后继

14、续扩大交错树。结论2.若收缩图中有关于的可扩交错路，那么原图中也有关于的可扩交错路。结论3.如果在收缩图中没有可扩交错路，那么就是最大对集。注意：（1）在交错树中，花型结构的出现有两种可能：一是同一个交错树中，两个型节点之间有非边相连；一是同一个交错树中，两个型节点之间有边相连。所谓花型结构出现，就是针对于某一个匈牙利树，有奇长的基本圈出现。（2）在执行过程中，可能由某个伪节点又出现在另外一个花型结构的花苞中。因而，一般地讲，说到伪节点，也包括这种包含伪节点的伪节点。结论4.每一个伪节点对应于图的一个奇数阶生成子图。下面陈述一般图中求最大对集的匈牙利算法：任取一个非饱和节点，记。令为型节点（若

15、中没有非饱和节点，那么为最大对集）。一般地，设已有。用反圈法在中进行选边，若在某一步，发现花苞，则收缩花苞。令伪节点为型节点，继续选边：若在某一边，得到增广树，则得到增广路并且调节；若在某一步得到匈牙利树，则再去一个非饱和节点，放入中，继续选边；若不再有非饱和节点，则是最大对集。下面将要证明：当算法终止时，是最大对集。为此，考察一下算法终止时我们得到什么结构。当中无边可选，并且所有的非饱和节点都在中时，算法终止。此时得到的交错树都是匈牙利树。是这些匈牙利树的节点集合，其中每一个节点或是型节点，或是型节点（可能是伪节点），每一个树种恰好有一个节点是非饱和节点。我们称中节点生成的子图中的连通分支为

16、无型分支。在每一个无型分支中，由于不含有非饱和节点，股必有偶数个节点。结论5.图的边必是下列情况之一：（1） 在某一个伪节点所对应的奇数阶生成子图中；（2） 是某一个树上的边或是连接树内部两个节点；（3） 连接两个匈牙利树；（4） 在某个无型分之内部；注意：在情况（2）-（3）之下，每一边的端点中有一个-节点。下面介绍所谓的“奇节点集合覆盖”，它是Konig关于二部图中点覆盖概念的自然推广。对于图中的节点集合，如果，则说是一个奇点集合。若，则说覆盖了与它关联的所有边；并且定义；如果，我们说覆盖了生成子图中的所有边，并且定义假定是一个图中的奇点集合族，如果的每一边至少被某一个所覆盖，则说构成了的

17、一个奇集覆盖。定义。结论6.对于任何一个对集和和任何一个奇集覆盖，。现在设是一个对集，我们可以执行匈牙利算法，算法终止，得到一个对集，一批匈牙利树和一些无型分图，现在来制造一个奇集覆盖如下：每一个型节点自然形成一个奇集合；每一个伪节点所对应的奇数阶生成子图为一个奇点集合；对于无型分图，取其中一个端点为一个奇集；根据结论5，我们有下面的结论7.上述奇集合全体是图的一个奇集覆盖。在结论7基础上自然有，这样，就是一个最大对集。定理（Edmonds1965）对于任何一个图，注意：因为一个而部图中不含有奇圈，在二部图中执行匈牙利算法时不会有花型结构出现，并且每一个无型分图是不含非饱和节点的二部图，可以用

18、个节点去覆盖所有无型分图的节点。因此，对于二部图以及一个最大对集，总可以找到一个由单元素集合形成的奇集覆盖使得，这就是Konig定理。例。 给定如图所示，粗边表示边。，是非饱和点。令，为型节点，在中选边，令，为型节点，在中选边，令为型节点，如此等等，得到以为根的匈牙利树（下图）现在再取节点为根节点，也是型节点，继续选边，最终得到以为根节点的匈牙利树（下图）余下的是无型分图（下图）算法终止时，。选取奇集合覆盖为满足条件下面要用Edmonds 的这个算法证明下面的定理（Berge,1958）.设是图中最大对集，则非饱和节点数为从而解答：（1）首先证明：对于任何一个集合，有。设是所有的奇分支，若中每一个节点都被饱和，那么至少有一条边，它要连接中一个节点与中一点，并且不同的对应的也不相同。这样，不含有非饱和节点的奇分支数目。由于含有非饱和节点的奇分支数目这样，。（2）证明：存在设是最