Question

导读

因为 Matching 的演算法有点複杂，所以我们同时介绍 Matching 和它的特例 Bipartite Matching。每当要讲解一个演算法时，就先提出 Bipartite Matching 的演算法，再进一步提出 Matching 的演算法，以循序渐进的方式进行讲解。

Matching

给定一张无向图，当图上两点以边相连时，这两点就可以配成一对──但是呢，一个点最多只能与一个邻点配成一对，宁可孤家寡人，万万不可三妻四妾。双双对对之间的边，整体成为一个“匹配”。

更简单的说法是：令图上各点仅连接著零条边或一条边，这些边构成的集合称作一个“匹配”。

Matched Vertex 与 Unmatched Vertex

一个点要嘛就是和另一个点比翼双飞，要嘛就是孑然一身──前者为“匹配点”，后者为“未匹配点”。

Matched Edge 与 Unmatched Edge

出双入对的两点之间的边为“匹配边”，除此以外则为“未匹配边”。一个匹配是由许多匹配边所组成的。

Cardinality

一个匹配拥有的匹配边数目，也就是配对的数目，称作 Cardinality，尚无适当中译。

顺便介绍一些特别的匹配：

maximal matching：一张图中，没有办法直接增加配对数的匹配。
maximum matching：一张图中，配对数最多的匹配。也是 maximal matching。
perfect matching：一张图中，所有点都送作堆的匹配。也是 maximum matching。

Weight

当图上的边都有权重，一个匹配的权重是所有匹配边的权重总和。

顺便介绍一些特别的匹配：

maximum weight matching：
一张图中，权重最大的匹配。
maximum weight maximum cardinality matching：
一张图中，配对数最多的前提下，权重最大的匹配。
maximum weight perfect matching：
一张图中，所有点都送作堆的前提下，权重最大的匹配。

Bipartite Matching

Bipartite Graph

“二分图”是图的一种特例。一张二分图的结构是：两群点（通常标记作 X 集合与 Y 集合）、横跨这两群点的边（X 与 Y 之间）。至于两群点各自之内是没有边的（X 与 X、Y 与 Y 间）。

顺带一提，二分图构造较单纯，其资料结构可以进行精简：

Bipartite Matching

“二分匹配”。一张二分图上的匹配称作二分匹配，理所当然所有的匹配边都是这横跨这两群点的边，就像是连连看一样。

以 Flow 解 Bipartite Matching

一侧接上源点，一侧接上汇点，即可利用网路流来解决最大二分匹配问题、最大（小）权二分匹配问题。

Augmenting Path Theorem（Berge's Theorem）

本章提要

Berge's Theorem 是寻找最大匹配的一个重要理论。在这个章节中，将会讲解匹配的相关知识，并证明 Berge's Theorem，最后提出一种计算最大匹配的手段。

Alternating Path 与 Alternating Cycle

“交错路径”与“交错环”，在一张存在匹配的图上，匹配边和未匹配边彼此相间的一条路径与一只环。

交错环有个有趣的特性：颠倒交错环上的匹配边和未匹配边，可以改变匹配，但不影响 Cardinality。

Augmenting Path

“扩充路径”，是第一个点和最后一个点都是未匹配点的一条交错路径，因此第一条边和最后一条边都是未匹配边。

扩充路径有个更有趣的特性：颠倒扩充路径上的匹配边和未匹配边，可以改变匹配，并且让 Cardinality 增加一。

Symmetric Difference

两个集合 A 和 B 的“对称差集”定义为 A⊕B = (A∪B) - (A∩B)。例如 A = {1,3,4,5}、B = {2,4,5,7}、A⊕B = {1,2,3,7}，没有重複出现的元素将会留下，重複出现的元素将会消失。

对称差集非常适合用来描述“颠倒扩充路径上的匹配边与未匹配边”这件事情。现在有一个匹配 M，和一条扩充路径 P（拆开成边），那麽 M⊕P 会等于新匹配。

坊间书籍常以对称差集来表述匹配相关理论。在此特别将对称差集的概念介绍给各位，希望各位往后遇到⊕这个符号时，不会下意识地认为它艰深晦涩。

Symmetric Difference of Matching

同一张图上的两种匹配 M 和 M*也可以计算对称差集 M⊕M*，总共会产生六大类 connected component，都是交错路径或者交错环，各位若是不信可以亲自实验看看：

两个匹配的对称差集，提供了这两个匹配互相变换的管道：对其中一个匹配来说，只要颠倒整个对称差集中的匹配边与未匹配边，就可以变成另一个匹配。写成数学式子就是：令 M⊕M* = P，则 M⊕P = M*、M*⊕P = M。

Augmenting Path Theorem

从图上任取一个未匹配点，如果找不到以此点作为端点的扩充路径，那麽这张图会有一些最大匹配不会包含此点。更进一步来说，就算从这张图上删除此点（以及相连的边），以剩馀的点和边，还是可以找到原本那张图的其中一些最大匹配。

证明不困难，利用一下先前所学到的东西，便可以推理出来：

令当下的匹配 M 找不到以未匹配点 p 作为端点的扩充路径，
并令 M*是该图的其中一个最大匹配。
1. 如果 p 不在 M*上：
   删除此点完全不会对 M 和 M*有任何影响，定理成立。
2. 如果 p 在 M*上：
　2-1. p 对于 M 来说是未匹配点。理所当然 p 不在 M 上。
　2-2. 考虑 M⊕M*的六种情形。p 不在 M 上，且 p 在 M*上，所以只有 d 或 e 符合条件。
　2-3. M 找不到以 p 作为端点的扩充路径，所以 d 不符合条件，只有 e 符合条件。
　2-4. 对于 M*来说，只要照著 e 颠倒匹配边和未匹配边，
　　　 就可以制造出另一个不会包含 p 的最大匹配，
　　　 成为 1.的情形，定理还是成立。

这个理论相当的重要，它表明了一个找最大匹配的手段：

1. 一开始图上所有点都是未匹配点。
2. 将图上每一个未匹配点都尝试作为扩充路径的端点：
　甲、如果找得到扩充路径：
　　　沿著扩充路径修改现有匹配，以增加 Cardinality。
　　　（此未匹配点变成了匹配点。）
　乙、如果找不到扩充路径：
　　　直接删除此点。继续下去仍然可以找到原图的其中一个最大匹配。
　　　（此未匹配点被删除。）

所有的未匹配点要嘛变成匹配点，要嘛被删除，
因此未匹配点最后会尽数消失，同时产生一个最大匹配。

其要点在于：反覆利用 Augmenting Path Theorem。儘管图上的点不断在减少，匹配也一直在改变，依然能找到原图的其中一个最大匹配。

Augmenting Path Theorem，另一种形式

一个匹配若无扩充路径，就是最大匹配。

要是图上所有未匹配点都不能当作扩充路径的端点，就代表著图上根本就没有扩充路径；Cardinality 无法增加，就代表著当下的匹配就是最大匹配囉！

不断找扩充路径，直到找不到为止。此时的匹配就是最大匹配。

Maximum Cardinality Bipartite Matching: Augmenting Path Algorithm

用途

找出一张二分图的其中一个最大二分匹配。

Alternating Tree

前面的章节以 Augmenting Path Theorem 提出了一个找最大匹配的方式，但是症结在于我们选定一个未匹配点之后，还不知道如何有效率的寻找扩充路径。我们可以选定一个未匹配点作为树根，然后建立搜寻树，尝试列出所有的交错路径，从树根出去的路径都是交错路径──藉此找扩充路径。

有个重要的发现是：在搜寻树当中，当两条交错路径撞在同一个点，将来还是只能选择其中一条路径来进行扩充，所以现在只要留下一条路径就够了。

根据这个重要的发现，图上的每个点、每条边只需经过一次，就能判断出扩充路径。我们得以用 Graph Traversal 来找一条扩充路径，并得到一棵树。

如此得到的树称作“交错树”，从树根出去的路径仍都是交错路径。很幸运的，二分图中的每条交错路径都是在 X 与 Y 之间来回，交错树很容易建立，亦可以很快的看出扩充路径在哪裡：若我们选定的未匹配点、扩充路径的端点是在 X 上，它会是交错树的树根；扩充路径的另一个端点、未匹配点就一定会在 Y 上，它会是交错树的树叶。

演算法

1. 一开始图上所有点都是未匹配点。
2. 将 X 的每个未匹配点依序尝试作为扩充路径的端点，
   并以 Graph Traversal 建立交错树，以寻找扩充路径。
  （X 的未匹点都处理过的话，Y 的未匹配点就不会再有扩充路径，故只需找 X 侧。）
　甲、如果找得到扩充路径：
　　　沿著扩充路径修改现有匹配，以增加 Cardinality。
　　　（此未匹配点变成了匹配点。）
　乙、如果找不到扩充路径：
　　　直接删除此点。继续下去仍然可以找到原图的其中一个最大匹配。
　　　（此未匹配点被删除。）

这个演算法运作起来，实际上就跟接上了源点与汇点再进行 Ford-Fulkerson Algorithm（Augmenting Path Algorithm）一样。

时间複杂度

时间複杂度为 O(V) 次 Graph Traversal 的时间。图的资料结构为 adjacency matrix 的话，便是 O(V^3)；图的资料结构为 adjacency lists 的话，便是 O(VE)。

找出一个最大二分匹配（精简过的 adjacency matrix）

以 DFS 来找扩充路径，程式码变得相当精简。

Maximum Cardinality Matching: Blossom Algorithm

用途

找出一张无向图的其中一个最大匹配。

Alternating Tree：Cross Edge

尝试利用二分图的 Augmenting Path Algorithm，不断选定未匹配点作为交错树的树根，然后寻找扩充路径。

这裡定义距离树根偶数条边的点称作“偶点”，距离树根奇数条边的点称作“奇点”──可以发现一般的 Graph 建立交错树时，会有个与 Bipartite Graph 不一样的地方，就是会有偶点到偶点的边。

二分图的交错树：
1. 偶点到奇点：一定是未匹配边。
2. 奇点到偶点：一定是已匹配边。
3. 偶点到偶点：二分图不会有这种边。
4. 奇点到奇点：二分图不会有这种边。

一般图的交错树：
1. 偶点到奇点：一定是未匹配边。
2. 奇点到偶点：一定是已匹配边。
3. 偶点到偶点：一定是未匹配边，且会形成“花”。
4. 奇点到奇点：交错树不会有这种边，因为不会形成交错路径。

Alternating Tree：Cycle

偶点到偶点的边，在交错树上会形成一个环。只要穿越这条偶点到偶点的边，以绕远路的方式，环上所有奇点都能够成为偶点，而且将来可以延伸出更多条交错路径。

原本奇点只能以匹配边连到偶点，无法额外延伸出其他交错路径；现在一般图的交错树中，多了偶点到偶点的边，奇点因此活跃了。环上的所有奇点，可以摇身一变成为偶点，然后重新延伸出交错路径！

Blossom

在交错树上，分岔的两段交错路径，接上一条偶点到偶点的边，所形成的奇数条边的环，就称作“花”。花上两条未匹配边的衔接点，则称作“花托”，宛如花开在交错树上。

Blossom Contraction

既然花上的点都可以成为偶点，那麽乾脆把花直接缩成一个偶点，会让交错树变得更简洁明白。

交错树上可能会有许多偶点到偶点的边，形成许多朵重重叠叠的花，我们可以用任意顺序缩花。实作时，为了容易找到花，可以在建立交错树的途中，一旦发现偶点到偶点的边就立即缩花。一句话，一旦发现花就立即缩花。

缩花的次数呢？一朵花最少有三个点，缩花后成为一个点，前前后后少了两个点。由此推得：V 个点的图建立一棵交错树，最多缩花 V/2 次；如果再多缩几朵花，树上就没有点了。

路径沿著花绕来绕去，绕得你晕头转向。

演算法

1. 一开始图上所有点都是未匹配点。
2. 将图上每个未匹配点依序尝试作为扩充路径的端点，
   并以 Graph Traversal 建立交错树，以寻找扩充路径。
   甲、走到未拜访过的点：
　　　a. 如果是已匹配点，则延伸交错树，一条未匹配边再加一条已匹配边。
　　　b. 如果是未匹配点，则找到扩充路径。
   乙、走到已拜访过的点：
　　　a. 如果是偶点，形成花。做花的处理。
　　　b. 如果是奇点，根据只需留一条路径的性质，什麽都不必做。

花的处理：
1. 找出花托，即是 x 与 y 的 Lowest Common Ancestor，
2. 设定一下到达花上各奇点之交错路径。
   一定会经过 cross edge。注意花托别重複经过。
3. 把花上面的点全部当作偶点。
   或者，乾脆把花直接缩成一个偶点。
   缩花可用 Disjoint Sets 资料结构。

找出一个最大匹配（adjacency matrix）

下面程式码採用 BFS 建立交错树，不缩花。

总共进行 V 次 Graph Traversal，每次 Graph Traversal 需要花 O(V^2) 时间建立树根至图上各点的交错路径，用 deque 资料结构记录之。

图的资料结构为 adjacency matrix 的话，便是 O(V^4)；图的资料结构为 adjacency lists 的话，便是 O(V^2 * (V+E))，可简单写成 O(V^2 * E)。

Maximum Cardinality Bipartite Matching: Hopcroft-Karp Algorithm

用途

找出一张二分图的其中一个最大二分匹配。

演算法

每次都一口气找出所有目前最短的扩充路径进行扩充，直到找不到为止。正确性证明与时间複杂度证明，请参考 CLRS 的习题。【待补文字】

1. 一开始图上所有点都是未匹配点。
2. 重複下列动作，直到无法增加匹配（最多执行 sqrtV 次）：
　甲、以 X 的所有未匹配点同时作为树根，
　　　採用 BFS 建立交错森林，一次仅延展一整层，
　　　直到发现所有目前最短的扩充路径。
　　　（时间複杂度为一次 Graph Traversal 的时间。）
　乙、对于各个 Y 的未匹配点，
　　　若为交错森林的树叶（最短扩充路径的端点），就往树根方向找扩充路径。
　　　注意一旦拜访过的点就不再拜访。
　　　（时间複杂度为一次 Graph Traversal 的时间。）
　　　注：也可以由树根往树叶找。

时间複杂度

时间複杂度为 O(sqrtV) 次 BFS 的时间。图的资料结构为 adjacency matrix 的话，便是 O(sqrtV * V^2) = O(V^2.5)；图的资料结构为 adjacency lists 的话，便是 O(sqrtV * (V+E))，可简单写成 O(sqrtV * E)。

找出一个最大二分匹配（精简过的 adjacency matrix）

Maximum Cardinality Matching: Micali-Vazirani Algorithm

用途

找出一张无向图的其中一个最大匹配。

演算法

每次都同时找出所有目前最短的扩充路径，并进行扩充，直到找不到为止。

http://www.cc.gatech.edu/~vazirani/new-proof.pdf

时间複杂度

O(sqrt(V)*E)。

Maximum Weight Perfect Bipartite Matching: Hungarian Algorithm（Kuhn-Munkres Algorithm）

用途

匈牙利演算法是几位匈牙利学者所发明的，用来求出一张二分图的最大（小）权完美二分匹配。稍做修改，也能用来求出最大（小）权最大二分匹配、最大（小）权二分匹配。

调整权重

一个点连接的所有边，等量增加权重、等量减少权重，都不会影响最大权完美匹配的位置。

此性质二分图和一般图都成立。

建立 vertex labeling

帮各个点都创造一个变数，直接在点上调整权重，代替在边上调整权重，藉此减少调整权重的时间。

转换问题：
最小化所有点的权重总和 = 最大化所有匹配边的权重总和

建立一组 vertex labeling：令图上每一条边，其两端点的权重总和，大于等于边的权重。

由于最大完美匹配必定用到每一个点：所有点的权重总和，必定大于等于所有匹配边的权重总和（最大权完美匹配的权重）。

现在只要尽力降低所有点的权重总和，就能逼近最大权完美匹配的权重。

令 l(x) 是 vertex labeling，x 是图上任意一个点。
令 vertex labeling 让图上所有边(x,y) 都满足 l(x)+l(y)>=adj(x,y)。

想办法降低 l(x)，让 ∑ l(x) =     ∑ adj(x,y) 为最大权完美二分匹配的权重。
                   x 为图上一点  (x,y) 为匹配边

设定上限，然后不断降低上限，降低到极限就碰到最大值了。原本一个求最大值的问题，变成了一个求最小值的问题。这是很实用的数学转换。

【注：以 Linear Programming 的观点来看，这个转换正是 primal problem 与 dual problem 之间的转换。】

这个转换有个重要目的：操作 vertex labeling 而不操作 edge labeling，藉此减少调整权重的时间。

现在只要求出一组总和最小的 vertex labeling，就得到最大权完美二分匹配。

Equality Edge（Admissible Edge）

一条边，两端点的点权重相加，恰好等于边权重，称为“等边”。当 vertex labeling 的总和降低到极限的时候，可以发现最大权完美二分匹配的所有匹配边都是“等边”。

定义“等边”(x,y) 是满足 l(x)+l(y)=adj(x,y) 的边。

Equality Edge + Augmenting Path Algorithm

以“等边”的概念，结合之前的 Augmenting Path Algorithm，得到一个演算法：以“等边”构成的扩充路径，不断进行扩充。由于用来扩充的边全是“等边”，最后一定得到的最大权匹配当然全是“等边”。

一、X 的每一个未匹配点，依序寻找扩充路径，扩充路径必须都是“等边”。
　　换句话说，运用 Graph Traversal 建立交错树，交错树必须都是“等边”。
　　（X 的未匹点都处理过的话，Y 的未匹配点就不会再有扩充路径，故只需找 X 侧。）
　回、如果找到“等边”扩充路径：进行扩充。
　回、如果找不到“等边”扩充路径：？？？？？

当找不到“等边”，只好想办法调整 vertex labeling 了。

调整 vertex labeling

该如何调整呢？要注意 vertex labeling 仍要维持大于等于的性质，而且既有的“等边”不能被改变。

先把“等边”构成的交错树延伸到极限，再把交错树末稍不是“等边”的边，取其两端点的权重总和、减掉边的权重，找此值最小者，交错树上偶点减此值、奇点加此值。

一加一减后，交错树内、外既有的“等边”依然保持不动，交错树末稍则增添了新的“等边”。整张图的“等边”只增不减。

令 d = min( l(x) + l(y) - adj(x,y) )，
       x 为“等边”交错树上一点，y 为“等边”交错树外一点。

让 l(x) -= d，让 l(x) += d。
   x 为树上偶点   x 为树上奇点

如此便制造了一条（以上）的等边，而且既有等边保持不动，
而且维持了每一条边的大于等于性质。

演算法

一、一开始图上所有点都是未匹配点。
二、建立 vertex labeling，使之满足前述的大于等于性质。
三、X 的每一个未匹配点，
　　依序寻找“等边”构成的扩充路径。
　　以 Graph Traversal 建立“等边”构成的交错树。
　　（X 的未匹点都处理过的话，Y 的未匹配点就不会再有扩充路径，故只需找 X 侧。）
　甲、如果形成“等边”构成的扩充路径：
　　　沿著扩充路径修改现有匹配，增加 Cardinality。
　乙、如果找不到“等边”，则制造新的“等边”：
　　　所有交错树末梢的边（都不是等边），算最小差值，偶点减，奇点加，
　　　便在交错树末稍增加一条以上的等边，而且既有等边保持不动。

1. 为了节省时间，使用 vertex labeling 转换问题。
2. 只用等边延展交错树。修正 label 以利延展：偶点减，奇点加。
3-1. label 总和会逐渐减少乃至收敛：修正 label 时，偶点总是比奇点多一个，然后看 2.。
3-2. 等边数量会逐渐增加乃至收敛：每次修正 label 就会产生一条以上的等边。
4. 收敛后，得最大权完美匹配。匹配边都是等边。权重为 label 总和。

时间複杂度：一、O(V) 个未匹配点建立交错树。二、一个未匹配点建立交错树时，最多调整 O(V) 次 label、进行 O(V) 次 Graph Trversal。三、每次调整 label，都要花 O(V^2) 时间找到最小差值。总时间複杂度为 O(V^4)。

Maximum Weight Perfect Matching: Blossom Algorithm

用途

用来求出一张图的最大（小）权最大匹配。

演算法

http://www.arl.wustl.edu/~jst/cse/542/lec/lec15.pdf

http://www.arl.wustl.edu/~jst/cse/542/lec/lec16.pdf

基于匈牙利演算法，仍然以等边来建立交错树，但是要额外考虑花的问题。

当形成花的时候，就把花上所有点标记为偶点，并进行缩花。调整权重时，偶点减 d、奇点加 d，此举造成花上的每条匹配边，皆与实际上的权重值少了 2d。

所以，每当调整权重，就必须记录这失去的 2d，因此，另外再建立一组 blossom labeling，每当刚形成花时，其值为零，之后若调整权重，就加上 2d。

调整权重改成：

让 l(x) -= d，让 l(x) += d。
   x 为树上偶点   x 为树上奇点

让 b(B) += 2d，让 b(B) -= 2d。
   B 为最上层偶花  B 为最上层奇花

如此可制造一条（或者一条以上）的等边，且既有等边保持不动。

等边的定义改成：

定义“等边”(x,y) 是满足 l(x) + l(y) + ∑ b(B) = adj(x,y) 的边。
                                     B 是花，且边(x,y) 在 B 上。

令 d = min( l(x) + l(y) + ∑ b(B) - adj(x,y) )，
       x 为“等边”交错树上一点，y 为“等边”交错树外一点。

扩充时，不拆花，仍将花暂时留著。当花变成

令 l(x) 是 vertex labeling，x 是图上任意一个点。
令 b(B) 是 blossom labeling，B 是建立交错树时形成的任意一朵花。
令 vertex labeling 与 blossom labeling 让图上所有边(x,y) 都满足：
l(x) + l(y) + ∑ b(B) = adj(x,y)
              B 是花，且边(x,y) 在 B 上。

演算法改成：

1. 一开始图上所有点都是未匹配点。
2. 建立 vertex labeling，使之满足前述的大于等于性质。
3. 将 X 的每个未匹配点依序尝试作为“等边”构成的扩充路径的端点，
   并以 Graph Traversal 建立“等边”交错树，以寻找“等边”构成的扩充路径。
  （X 的未匹点都处理过的话，Y 的未匹配点就不会再有扩充路径，故只需找 X。）
　甲、如果形成“等边”构成的扩充路径：
　　　沿著扩充路径修改现有匹配，以增加 Cardinality。
　乙、如果找不到“等边”，制造新的“等边”：
　　　所有交错树末梢的边（不会是等边），算适当值，偶点减，奇点加，
　　　便在交错树末稍增加一条以上的等边，且既有等边保持不动。

z(B) 加上 2d 的原因是，
缩花时花内每个点都被标成正点，  （正点减 d、负点加 d）
然后花内每条匹配边的两个端点当然都是正点都各减 d，所以一条匹配边就少 2d。
故花内每条匹配边都必须补 2d 回来。
注意到补 2d 的性质，经过扩充路径反转匹配边/未匹配边之后，还是依然如此。

只有最外层的花 z(B) 需要加上 2d，因为 z(u,v) 被设计成累加所有 z(B):u,v 属于 B。
如此一来，调权重会简单些，程式码比较好写。

因为要拆花，所以不能用 Disjoint Forest，只能用普通的树。
所以就算用 DP 也不能达到 O(VEalpha(E,V))，还是只有 O(VElogV)。

各位也可以尝试建立交错森林。但是要小心在不同树之间、偶点与偶点之间的边，调整权重时切记要满足 vertex labeling 的大于小于性质。

延伸阅读：求最小权最大匹配

和匈牙利演算法相似，改为升高 vertex labeling 与 blossom labeling 的和。

或者把所有边的权重变号，然后求最大权最大匹配。