开花的算法

的开花的算法，有时被称为埃德蒙兹匹配算法，可以用于任何图构建一个最大匹配．开花算法是在匈牙利算法通过缩小图中的循环来揭示增广路径．此外，匈牙利算法只适用于加权一式两份的图但是blossom算法适用于任何图形。开花算法是一种多项式时间最大图匹配算法。该算法有许多应用，例如，分配问题，如大厅的婚姻定理，以及路径问题，如哈密顿路径问题．

^［1］

的匈牙利算法是一种非常有效的图匹配算法，但它只适用于加权二部图，因为它不能处理奇数长度的循环。问题在于寻找增广路径，因为如果有一个奇循环，算法将计算错误的增广路径，因为它会错过一些边。此外，一个循环可能使算法永远循环，在最小权值优化的情况下，使权值无限次地减少，抑制适当的终止。Blossom算法旨在通过解决更广义的图匹配问题来填补这一空白，并且可以在图不能保证是二部的情况下使用。

该算法改进了匈牙利算法，有一种处理奇数长度循环的方法。它通过找到一种方法来欺骗算法，让算法认为它是在一个简单的二部图上操作，将一个循环折叠成一个顶点，这样它就可以在匹配上运行匈牙利算法。

这个算法之所以这样命名，是因为一个循环看起来很像一朵花，暗指一朵花。可以缩小这些循环，然后递归地重新启动搜索。如果算法在收缩图中发现了一条增广路径，它可以通过花向上展开，在原始图中生成一条增广路径。这种交替路径可用于将匹配增加一条边。如果递归过程曾经运行到一个没有增广路径的状态，那么算法可以返回原始图中没有增广路径。^[２]

开花算法取一个一般的图 $G = (v, e)$并找到一个最大匹配 $米$．该算法从一个空匹配开始，然后通过每次添加一条边来迭代改进它增广路径在匹配 $米$．添加到扩展路径可以增加匹配，因为扩展路径中的每一条其他边都是匹配中的一条边;随着更多的边被添加到扩展路径中，就会发现更多的匹配边。blossom算法在每次迭代后都有三种可能的结果。算法要么找不到增广路径，在这种情况下，它找到了一个最大匹配;为了改善结果，可以找到一条增强路径;或者可以找到一个花，以便操纵它并发现一个新的扩充路径。

增广路径

增广路径是一个奇数长度的路径，其端点有不匹配的节点。增广路径中的边是交替的:一个线段在匹配中，下一个线段不在匹配中，下一个线段在匹配中，以此类推。

该算法通过寻找增广路径来工作，因此每次迭代都可以增加一次匹配的大小。要做到这一点，它首先寻找不匹配的顶点(没有连接到匹配中的边的顶点)。然后，它从这些节点建立一个交替路径。这意味着路径从不匹配的节点开始—要成为扩展路径，它必须以不匹配的节点开始和结束。

算法继续在增广路径上构建，直到它不能再扩展为止。当它停止构建增广路径时，要么是图已经用尽了不在增广路径中的边，在这种情况下，没有最大匹配;要么是算法到达了一个点，无法生成增广路径，在这个点，算法返回一个最大匹配。

花朵

花背后的思想是，图中的奇数长度循环可以压缩到单个顶点，这样搜索就可以在现在压缩的图中继续迭代^［3］．这里，这些奇数的周期是花朵。算法可以在图中继续运行，并将复杂的循环视为只有一个节点——欺骗算法，使其认为图中有偶数个节点(它已经探索过了)，这样它就可以在图上运行匈牙利算法。

一个开花是一个循环 $G$组成的 $2 k + 1$它们的边 $k$属于 $米$，其中一个顶点 $v$在循环(基)中，存在着一条间隔长度的交替路径，称为从 $v$到一个暴露的顶点 $w$^［3］．这种优势是由于茎部可以在花的边缘之间轻松切换。

^［1］

该算法的目标是将一朵花缩小为单个节点，以揭示其扩展路径。它通过运行匈牙利算法直到它撞到一朵花，然后它收缩成一个顶点。然后，它再次开始匈牙利算法。如果发现了另一朵花，它会缩小花朵并启动匈牙利算法，依此类推。^［4］

注意边的切换，使另一个匹配的边花的茎^［5］．

^［6］

伪代码

形式上，该算法是通过维护扫描边缘的森林来执行的。

1. $M = 0，\ h = g，\ n = M$

2. EVEN = {v | v在M}中是自由的，ODD = 0， $E_f = 0$， $F = (v_f, e_f)$．

3. 维护 $V_F =偶数\杯奇数$．

4. 选择一个边缘 $u, v$这样 $你\ \ε\甚至$而且 $v范围内随意抽查,\ \ \很奇怪$

   a.如果不存在，则输出 $米$．

5. 如果 $v范围内随意抽查,\ \ \ V_F$然后:

   一。把 $v$奇怪的, $米(v)$甚至, $(u, v)$而且 $(v (v))$在 $E_f$,在那里 $米(v)$顶点匹配到吗 $v$．

6. 其他的,如果 $v \ \ε\$而且 $u, v$被联系在一起 $F$,那么:

   一。花 $B$被发现。

   b。收缩 $B$来 $b$,并设置 $H$来 $H \ setminus B$， $N$来 $N \ setminus B$．

   c。 $H$,把 $b$甚至在。

   d.执行步骤4。

7. 其他的,如果 $v \ \ε\$而且 $u, v$在F中没有连接，则:

   a.存在增广路径 $\ν$在 $H$关于 $N$．

   b.检索增广路径 $\ρ$在 $G$关于 $米$．

   c。增加 $米$．

   d.执行步骤2。

8. 当不再满足条件时结束算法。

在上面的伪代码中，如果由一条边连接的两个顶点是EVEN顶点，就可以很容易地发现一朵花，这意味着循环是奇数。类似地，增广路径 $\ρ$可以通过还原花朵和沿途缩小的匹配来回收。如果增广路径 $H$， $\ν$，由 $G$缩减 $B$来 $b$,如果 $\ν$不能访问 $b$,然后 $\ν$也是一个 $米$增广路径。否则,要么 $\ν$以b结尾，在这种情况下是开花 $B$包括树的根 $\ν$在某个顶点结束 $B$；或 $\ν$访问 $b$，这样的话 $\ν$达到顶点 $x$在 $B$，并且可以修改花朵，以便匹配的边缘可以将图形与根连接起来，如上图6所示^［7］．

开花算法有三种结果会增加运行时复杂度:它可能会找到最大匹配、一条扩展路径或一个开花。在最坏的情况下，该算法的总运行时间为 $V E O (| | | | ^ 2)$，每次迭代都需要 $E O (| |)$当每条边都被扫描以确定完美匹配时。如果找到一个扩展路径，则可以在 $V O (| |)$时间, $V E O (| | | |)$时间。最后，如果发现了一朵花，则必须递归较小的图，这可以重复出现最多为 $V O (| |)$递归，此时要么找到增广路径，要么算法终止。由于每次递归一朵花，都会有一组新的增广路径，因此算法的最大运行时为 $V E O (| | | | ^ 2)$^［8］．

该算法后来经过改进，其运行时为 $O (V ^ | 3 |)$，其后进一步减至 $E O (| | \ i - V {| |})$．关于快速实现的更多细节，请参考Micali和V. Vazirani的论文，MV匹配算法的一个证明．

• 匹配算法

1. ,一个。埃德蒙兹blossom.svg．检索于2016年6月19日https://en.wikipedia.org/wiki/File:Edmonds_blossom.svg
2. 马车,S。开花的算法．检索自2016年6月26日http://mathworld.wolfram.com/BlossomAlgorithm.html
3. ,。开花的算法．检索于2016年6月19日https://en.wikipedia.org/wiki/Blossom_algorithm
4. Kusner, M。埃德蒙兹的开花算法．检索于2016年6月19日http://matthewkusner.com/MatthewKusner_BlossomAlgorithmReport.pdf
5. ,一个。埃德蒙兹起重path.svg．检索于2016年6月25日https://en.wikipedia.org/wiki/File:Edmonds_lifting_path.svg
6. ,一个。埃德蒙兹起重path.svg．检索于2016年6月25日https://en.wikipedia.org/wiki/File:Edmonds_lifting_end_point.svg
7. Mahajan, M。在图的匹配．从检索http://www.imsc.res.in/~meena/matching/edmonds.pdf
8. 古普塔,。第八讲:埃德蒙的开花算法．从检索http://www.cs.cmu.edu/~anupamg/advanced/lectures/lecture08.pdf