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

计算图中的最大对集的匈牙利方法
背景知识介绍一在一个网络中往往要求计算其中的最大对集。是由匈牙利人Egervary于
1931年发现，后被另外一个匈牙利人Edmonds所推广(到一般图中的“开花算法”)
基本方法一利用反圈法
第一节点在 A41中。显然
此时可以选边使得对集增大。矛盾。因此，当情况2发生时当前的对集是最大的。
注意：从上述分析中可知，我们的讨论可以假定A32 = A42 =4。分析中得到的结构(结论
1-6)非常有用，我们可以直接利用它们来计算。
| E(G) »0的二部图G =(S,T, E)中一定有一个最大对集饱和所有最 大次节点。
点评：如果这个结果成立，那么这个图一定是第一类的(即，边色数 ？'(G) = A(G)。)
解答：设M 是这样一个最大对集，它所饱和的最大次节点最多。我们将要证明：M为所
求。若不然，则存在一个最大次节点 v,没有被M 所饱和。不妨设VWS,可以取M 使得v 是唯一一个未被饱和的最大次节点。对于这个M执行匈牙利算法。可知情况2 一定出现
（即，无边可选的结构一定出现）。
注意到上述结论1-结论6暗示：| A因A2 | +1。此时A 一定有一个节点不是最大次的。不 然，则有
|Ag（G） = £ d（u） <Z d（u）M|AJA（G）,
u AJ\u A22
这与|A巨| Ad +1相悖（这里利用了性质： A中非根节点的领域全部被包含在5 设
Vi w A不是最大次节点，记 N为执行匈牙利算法终止时得到的交错树里面唯一的（v-v）-
路。意见它的长度为偶数。令 M ' = M © E（N）,则M '也是最大对集，它饱和最大节点数 目比M 多（事实上，M '饱和了 v,但是没有饱和M。这正是我们需要的； 同时，前面M 中其他节点还是被 M '所饱和）。这与M定义相违背。
点评：关于这个结果有许多证明。我们将要提供另外一个富有技巧性的证明（但是说真的， 我不喜欢这种过于简短的证明，因为它们往往掩盖了很多的事物真相！）。
,那么可以将它的边进行着色，每一条边染这r 中颜色中的一种，使得同一个节点引出的边颜色不同。
解：如果G是r -正则图，则由Hall定理知道结论成立。否则，G不是正则图。我们可以将
G扩展成为一个r-正则二部图G （即，G是G的子图）如下：增加一些节点使得 G的两 部分X,Y的节点数目相同，然后在两部分之间尽可能地连边，直到。再连一条边则最大次 数就超过r为止。这样得到的图一定是 r -正则图。理由如下：因为若有 x三X的次数小于 r ,则总边数<r | X尸r |Y |,从而必y乏丫的次数小于r。于是可以连边xy而不破坏r 的最大性。根据上面所讲，可以对 G的边进行r着色，使得每一种颜色的边恰好是一个完 美对集。在此结构下，G的边也相应地被染上了 r种颜色，使得每一种颜色的边形成一个
对集。
点评:这个例子表明：如果一个二部图的最大次为△,则其中一定有对集饱和所有最大次
节点。这个对集可以是最大的。
-正则二部图一定有1-因子。
卜面要用匈牙利算法终止时得到的结构来证明著名的
Konig定理和 Hall定理。
定理5(Konig,1931)对于任何二部图 G = (S,T , E),最小节点覆盖阶数 =最大对集阶数。
证明：设M是一个最大对集，D0是最小覆盖集合的阶数。容易看出：
I M 归 Do
根据我们在对当前的 M执行匈牙利算法时，一开始就无边可选。于是，就有前面图形所示 结构，那里有以下事实：
|M IHA32I |N(S-A32)|
这里，N(S-A32) =A2。可以看出：A32UA2是一个覆盖，从而必有|M |= Do。证明完毕。
注意到，对于任何 S的子集A, N(A)=(S-A)形成一个覆盖。
G =(S,T, E),
最小节点覆盖阶数=最大对集阶数
= mn(|N(A)|+|S-A|)二|S|-mg{|A|-|N(A)|}
如果G =(S,T,E)中有对集M饱和S中所有节点，那么自然有(Hall条件)
-A S- |N(A)| | A|
成立。反过来，假定上述条件成立，一定有最大对集饱和S中所有节点。
推论7 (Hall定理1935)对于任何二部图 G =(S,T, E),存在对集饱和 S中所有节点的充
分必要条件是：
-A-S=| N(A)| | A|
注意：组合学中有几个著名的" max=min ”-型定理：Menger定理，Hall定理，Konig定理 以及Dilworth定理。它们在本质上都是等价的，以后我们还要介绍它们之间的相互推导。
第