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

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

2、，则选取以 为端点的非 边（即，在 型节点处只选非 边）()kivSivSM；(b)如果 ，则选取以 为端点的 边（即，在 型节点处只选 边）()kiXTiMT（3）若在某一步，出现下述情况之一时算法要终止：情况 1。 中有非饱和的 型节点（此时得到一条关于 的增广路） ；()k情况 2.。情况 1 不出现，且 中无边可选（此时 中不存在关于 的增广路） 。()kXGM定理 1.当匈牙利算法结束时，得到一个最大对集解答：下面我们来证明这个方法（算法）的正确性。如果情况 1 发生，根据我们算法特点，每一步上 都是森林，其中每一个树都是(),kXE以 中的一点为根的。根据 的定义，每一个树以一个非

3、饱和的 型节点为根。按(0)X(0)XS照选边原则（2）可以看出：每一个树上，根与任意节点之间的唯一的路是交错路、 。所以，当某个非饱和的 型节点属于 时，这个树上联接根节点与它的路是一个长度为奇数T()k的增广路。现在假定情况 2 出现。我们用 表示此时的 （一定要记住： 中的每一个节点都位*X()k*X于一个树中） 。令 记*,V*1234;.ASXT其几何意义如图所示：（注意：这是其中一种结构，也是最重要的结构，即，假定对集中所有边都被包含在以 为根的树中） 。(0)结论 1.所有非饱和的 型节点都在 中（这是根据 的定义得到的。表明：每一个这S1A(0)X样的非饱和 型节点都是一个树的

4、根，这个树有可能退化为一个节点！） ；结论 2。所有的非饱和的 型节点都在 中（否则，选边原则（1）可得到增广路） ；T4结论 3. （前提是： 连通）14,EAG事实上，如果有 使得 ，则因为 ，知道14,vuA()vE*,vXu如果 则 是可选边（事实上此时有增广路联接 与 中点） ，*();uvX,M (0)X与情况 2 的定义相违背；如果 ，则 ，必然有 使得 ，与v(0)2wAvM是对集相违背。M结论 4. （这个显然成立）23,EA注意：上述图形仍有地方要知道： 中含有未被饱和的非根节点（因此， ）1A12|A注意：上述的有些东西可能描述的不太精确。我们下面详细说明。记住当前算法执

5、行到情况 2，无法选边而且情况 1 不发生。可选边时有两种选法：沿着对集 中的边向下走，沿着非 中边向上走。MM（1） ：将对集 分成两类： 和 ，其中 是以 中的节点为根的12121M31A树中所能包含的 边形成的子对集，而 则是无法被这些树所含有的子对集（可以为空M2M集） ；（2）对集 所能饱和的 的节点集合为 ，没有被饱和的节点集合为S132A(0)31AX（3） ；*1234142,;ASXTA（4） （这是由于无法选边决定的，否则，有些子树可以长大） ；4231E（5） （理由同上） 。1,这样，结论 1.所有非饱和的 型节点都在 中（这是根据 的定义得到的。表明：每一个S31A(

6、0)X这样的非饱和 型节点都是一个树的根，这个树有可能退化为一个节点！） ；结论 2。所有的非饱和的 型节点都在 中（否则，选边原则（1）可得到增广路） ；T4结论 3. ；413,EA结论 4. 324132();()NA结论 5. 。 （这是由图的连通性决定的）,结论 6. ；2413EAM这样一来，若 中存在增广路，那么它的一个端点在 中，另外一个端点在 中。显G31A41A然此时可以选边使得对集增大。矛盾。因此，当情况 2 发生时当前的对集是最大的。注意：从上述分析中可知，我们的讨论可以假定 。分析中得到的结构（结论3241-6）非常有用，我们可以直接利用它们来计算。定理 2.任何一个

7、使得 的二部图 中一定有一个最大对集饱和所有最|()|0EG(,)STE大次节点。点评：如果这个结果成立，那么这个图一定是第一类的（即，边色数 。 ）()G解答：设 是这样一个最大对集，它所饱和的最大次节点最多。我们将要证明： 为*M *M所求。若不然，则存在一个最大次节点 ，没有被 所饱和。不妨设 可以取 使v*M,vS得 是唯一一个未被饱和的最大次节点。对于这个 执行匈牙利算法。可知情况 2 一定v出现（即，无边可选的结构一定出现） 。注意到上述结论 1-结论 6 暗示： 。此时 一定有一个节点不是最大次的。不12|A1A然，则有，121 2|()()()|()uAuAGdG这与 相悖（这

8、里利用了性质： 中非根节点的领域全部被包含在 ） 。设12|A1 2A不是最大次节点，记 为执行匈牙利算法终止时得到的交错树里面唯一的 -iv ()iv路。意见它的长度为偶数。令 ，则 也是最大对集，它饱和最大节点*()MEM数目比 多（事实上， 饱和了 ，但是没有饱和 。这正是我们需要的；同时，前面*viv中其他节点还是被 所饱和） 。这与 定义相违背。M *点评：关于这个结果有许多证明。我们将要提供另外一个富有技巧性的证明（但是说真的，我不喜欢这种过于简短的证明，因为它们往往掩盖了很多的事物真相!） 。例 3. 如果二部图 G 中节点次数的最大值是 ，那么可以将它的边进行着色，每一条边染这

9、r中颜色中的一种，使得同一个节点引出的边颜色不同。r解：如果 G 是 正则图，则由 Hall 定理知道结论成立。否则，G 不是正则图。我们可以r将 G 扩展成为一个 正则二部图 （即， 是 的子图）如下：增加一些节点使得 G 的两部分 的节点数目相同，然后在两部分之间尽可能地连边，直到。再连一条边则最YX,大次数就超过 为止。这样得到的图一定是 正则图。理由如下：因为若有 的次rr Xx数小于 ，则总边数 ，从而必有 的次数小于 。于是可以连边 而|YrYyry不破坏 的最大性。根据上面所讲，可以对 的边进行 着色，使得每一种颜色的边恰好r G是一个完美对集。在此结构下， 的边也相应地被染上了

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

11、 是一个覆盖，从而必有 。证明完32()NS0|MD毕。注意到，对于任何 的子集 ， 形成一个覆盖。A()NSA推论 6.对于任何二部图 ，(,)GTE最小节点覆盖阶数=最大对集阶数= min|()|max|()|AS ASNN如果 中有对集 饱和 中所有节点，那么自然有（Hall 条件）(,)STEM|()|成立。反过来，假定上述条件成立，一定有最大对集饱和 中所有节点。S推论 7（Hall 定理 1935）对于任何二部图 ，存在对集饱和 中所有节点的充(,)GTES分必要条件是： |()|ASNA注意：组合学中有几个著名的“max=min”-型定理：Menger 定理，Hall 定理，Ko

12、nig 定理以及 Dilworth 定理。它们在本质上都是等价的，以后我们还要介绍它们之间的相互推导。第二节 一般图中的最大对集值 Edmonds 开花算法。基本想法- 将二部图中的匈牙利算法推广到一般图。首先我们来回顾一下我们在二部图中始怎么做的。给定一个二部图 和一个对集 ，算法开始时，令 是所有非饱和的(,)GSTEM(0)X型节点集合。一般地，设已经有 。我们在 中开始选边，选边的原则是：S()kX()k在 型节点处选非 边，在 型节点处选 边；把被选到的边放入到 中去，得()k到 。放入节点时会有两个情况发生：若有某个非饱和的 型节点在 中，则(1)kX T(1)kX得到增广路；否则

13、继续选边过程。若在某一步，没有边可以选择，则说明没有增广路，当前的 便是最大对集。M在前一节的匈牙利算法执行过程中，所有被选边 生成的子图 是由()kE()(),kkGE个交错树组成的森林。每一个交错树恰好有一个非饱和节点（是 型节点） 。形象(0)|X S地讲，匈牙利算法的执行过程就是以 中每一个节点为根的交错树的生长过程。扩大交(0)X错树的方式有两种：一是选入一条 边（图（a） ） ；一是选入一条非 边，而这条边在MM中始饱和的（图（b） ） 。在这两种情况下，我们称此时的交错树为可扩的。若被选()kV入的非 边在 中始非饱和节点（图（c） ） ，这个交错树中有一个增广路，这个树M()k

14、X称为增广树。若增广树即不是可扩的，也不是增光的，我们就称其为匈牙利树（图(d)） 。每一个匈牙利树种必有奇数个节点，其中仅有根节点为非饱和节点下面我们来把上述算法改造一下，以便可以适用于一般图。开始时，令 为所有未饱和节点并且记它们为 型节点。选边原则不变。(0)XS当选一条非 边时，把它在 中的端点记为 型节点；当选一条 边时，把它M()kVXTM在 中端点记为 型节点。整个过程仍然是扩大交错树，或者得到增广树，或者()kVS得到匈牙利树。不过要注意的是：这是的增广树除了上述所讲的一种形式以外（图(c)） ，还有一种可能：它可能由两个交错树“合并”而成的，即，当两个交错树的两个 型节S点之

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

16、所谓“花”的概念。给定图 是它的一个对集。若 是其中一个奇圈，使得 上恰好有(,)GVEMBB条 边。因此 有唯一一个节点 ，它在 中的两条关联边均不是 边。1|2BBbvBM设 是一条 交错路，其中 是关于 的非饱和节点， 是长度为偶数的路，0()bv0M。我们称由路 与奇圈 所成的子图是一个花型结构（注意：()BVB可以是 1，这时， 不是饱和节点） 。| bv由 生成的子图，成为花苞， 为花托， 是花柄， 是花根。()Bb0v结论 1。设 是一个花型结构。显然，从 的根到花苞上任何一点有一条长度为偶数的交BB错路。Edmonds 的做法是：在执行匈牙利算法扩大交错路的过程中，一旦发现花型

17、结构，则在图中收缩花苞，得到一个伪节点。令这个伪节点为 -型节点，然后继续扩大交错树。S结论 2.若收缩图中有关于 的可扩交错路，那么原图 中也有关于 的可扩交错路。MGM结论 3.如果在收缩图中没有可扩交错路，那么 就是最大对集。注意：（1）在交错树中，花型结构的出现有两种可能：一是同一个交错树中，两个 型节S点之间有非 边相连；一是同一个交错树中，两个 型节点之间有 边相连。所谓花型T结构出现，就是针对于某一个匈牙利树，有奇长的基本圈出现。（2）在执行过程中，可能由某个伪节点又出现在另外一个花型结构的花苞中。因而，一般地讲，说到伪节点，也包括这种包含伪节点的伪节点。结论 4.每一个伪节点对

18、应于图 的一个奇数阶生成子图。G下面陈述一般图中求最大对集的匈牙利算法：任取一个非饱和节点 ，记 。令 为 型节点（若 中没有非饱和节点，那1iv1(0)iXv1iSG么 为最大对集） 。一般地，设已有 。用反圈法在 中进行选边，M()k()kX若在某一步，发现花苞，则收缩花苞。令伪节点为 型节点，继续选边：若在某一边，得到增广树，则得到增广路并且调节 ；M若在某一步得到匈牙利树，则再去一个非饱和节点，放入 中，继续选边；若不再有非()k饱和节点，则 是最大对集。下面将要证明：当算法终止时， 是最大对集。为此，考察一下算法终止时我们得到什么结构。当 中无边可选，并且所有的非饱和节点都在 中时，

19、算法终止。此时得()kX()kX到的交错树都是匈牙利树。 是这些匈牙利树的节点集合，其中每一个节点或是 型节()k T点，或是 型节点（可能是伪节点） ，每一个树种恰好有一个节点是非饱和节点。S我们称 中节点生成的子图 中的连通分支为无型分支。在每一个无型()kV()kGVX分支中，由于不含有非饱和节点，股必有偶数个节点。结论 5.图 的边必是下列情况之一：G（1） 在某一个伪节点所对应的奇数阶生成子图中；（2） 是某一个树上的边或是连接树内部两个节点；（3） 连接两个匈牙利树；（4） 在某个无型分之内部；注意：在情况（2）-（3）之下，每一边的端点中有一个 -节点。T下面介绍所谓的“奇节点集

20、合覆盖” ，它是 Konig 关于二部图中点覆盖概念的自然推广。对于图 中的节点集合 ，如果 ，则说 是一个奇点集合。(,)GVEUV|1(mod2)U若 ，则说 覆盖了与它关联的所有边；并且定义 ；如果|1Uc，我们说 覆盖了生成子图 中的所有边，并且定义|2()mG().cm假定 是一个图中的奇点集合族，如果 的每一边 至少被某一个 所12,.sCA eiC覆盖，则说 构成了 的一个奇集覆盖。定义G。1()()siicCA结论 6.对于任何一个对集 和和任何一个奇集覆盖 ， 。MA|()Mc现在设 是一个对集，我们可以执行匈牙利算法，算法终止，得到一个对集 ，一批匈*牙利树和一些无型分图，

21、现在来制造一个奇集覆盖如下：每一个 型节点自然形成一个奇集合；T每一个伪节点所对应的奇数阶生成子图为一个奇点集合；对于无型分图，取其中一个端点为一个奇集；根据结论 5，我们有下面的结论 7.上述奇集合全体是图的一个奇集覆盖 。*A在结论 7 基础上自然有 ，这样， 就是一个最大对集。*|()Mc*定理（Edmonds1965）对于任何一个图 ，Gmax|M=in()cA是 奇 集 覆 盖是 对 集注意：因为一个而部图中不含有奇圈，在二部图中执行匈牙利算法时不会有花型结构出现，并且每一个无型分图是不含非饱和节点的二部图，可以用 个节点去覆盖所有()1|2kVX无型分图的节点。因此，对于二部图以及一个最大对集 ，总可以找到一个由单元素集*合形成的奇集覆盖 使得 ，这就是 Konig 定理。A*()|cM例。 给定如图所示，粗边表示 边。 ， 是非饱和点。令 ， 为 型节*M1v8(0)1XvS点，在 中选边 ，令 ， 为 型节点，在 中(0)X126,v()26,X26,vT(1)选边 ，令 为 型节点，如此等等，得到以 为根的2367,v()37,vS1v匈牙利树（下图）现在再取节点 为根节点，也是 型节点，继续选边，最终得到以 为根节点的匈牙利18vS18v树（下图）余下的是无型分图（下图）