二部圖最大匹配——新資料結構Augmenting graph與Hopcroft-Karp演算法的複雜度證明

作者：由 JHack 發表于攝影時間：2020-12-25

本文使用 Zhihu On VSCode 創作併發布

前言

在圖論演算法中，我們在解決一個二部圖的最大匹配（以下簡稱二部匹配）問題時，往往是基於最大流演算法的（在很多教材和網上的資料均是如此）。而在組合最佳化中，我們往往會利用更為深刻的數學方法對該問題進行轉化、歸約。

對於不帶權的二部匹配問題（Cardinality bipartite matching），求解其最大匹配時通常會使用到一種方法叫做Augmenting path（增廣路），這種演算法唯一的挑戰就在於如何在多項式時間內尋找增廣路。這裡我介紹一種使用全新的資料結構（姑且稱之為資料結構） - Augmenting graph，對不帶權二部匹配問題進行求解。我們會看到該資料結構是如何快速在二部圖中尋找增廣路的。

問題定義

二部圖（Bipartite graphs）

二部圖的定義是基於圖的點著色（coloring）的，這裡為了簡便，我們直接介紹其「直觀」的定義：一個無向圖

被稱為一個二部圖，如果其頂點能劃分為兩部分：

such that

$U\cup W=V$

且G中每一條邊都能連線

和

。

二部圖有一個非常顯著的特徵：

是一個二部圖

$\Leftrightarrow$

中每一個環都是偶數長度的。

在後面的寫作中，我將使用

$G=(U\cup W,E)$

來表示一個二部圖，其中原頂點集

被劃分為了兩部分

。

匹配（Matching）

圖的一個匹配是一個邊集

$M\subseteq E$

such that M中任意兩條邊都是不相鄰的。換句話說，對於圖中任意一個頂點

，至多隻有一條匹配邊

$e\in M$

與其相鄰。

二部匹配問題

令

$G=(U\cup W,E)$

是一個二部圖，求一個匹配

$M\subseteq E$

，使得

是最大的。

一個二部圖匹配的例子：

matching

max matching

M-augmenting path

對稱差（symmetric difference）

對稱差是一種集合運算。給定兩個集合

，定義其對稱差

$\oplus$

為

$A\oplus B:=(A-B)\cup (B-A)=(A\cup B)-(A\cap B)$

對稱差的性質：

Commutative 交換性：

$A\oplus B=B\oplus A$

Associative 結合性：

$(A\oplus B)\oplus C=A\oplus (B\oplus C)$

The empty set is neutral：

$A\oplus \emptyset=A$

Every set is its own inverse：

$A\oplus A=\emptyset$

對稱差

Alternating and Augmenting Paths

如圖，給定一個匹配M，我們稱一個path

$P\subseteq E$

或者一個cycle是alternating的，如果M中的（部分或所有）邊交替地出現在其中。

我們也稱這樣的P是一個

M-alternating path

（下圖包含3條M-alternating path和一個

M-alternating cycle

）。

注意，並不需要M所有的邊都出現在其中，例如下圖的例子中，原圖被分為了四個連通分支，粉色的邊為匹配邊，那麼這些連通分支都可看做是alternating的，顯然對於任意一條alternating path，其並不包含所有M中的匹配邊。

如果P是一個M-alternating path，且P的長度是奇數，且P的兩個端點都沒有被M覆蓋，則我們稱這樣的P是一個

M-augmenting path

（關於M的增廣路）。

alternating path

對於一條M-augmenting path，我們可以對其進行「增廣」，因為它並沒有被「最大限度地匹配」，例如上圖中的第一條path（標記了augmenting），其中的兩條匹配邊顯然不是最大匹配，最大匹配應該是像第三條path那樣。

Augmentation

令M是一個匹配，

是一條M-augmenting path，則

滿足

仍然是一個匹配，且

。

這種操作我們通常稱之為augmentation（增廣），偶爾也會叫做swapping。

swapping

也就是說，對一個M-augmenting path和M進行對稱差，我們能得到一個更大的匹配

。

Symmetric difference of two matchings

接下來我們來分析一下，對圖中任意兩個匹配進行對稱差操作會發生什麼，這個結論在後面的演算法證明中會用到。

令

是一個無向圖，M和N為圖中任意兩個匹配，則

$M\oplus N$

的結果將會得到如下結論：

我們會得到一些連通分枝（component）。

每一個頂點要麼被N覆蓋要麼被M覆蓋要麼被M和N覆蓋（頂點被邊集覆蓋的意思是在邊集中存在一條或多條邊與該頂點相鄰），因此每一個頂點至多擁有

兩個

與其相鄰的頂點，因此這些分枝要麼是一條簡單路徑（path），要麼就是一個環（cycle），且所有的分枝都是「點分離（vertex disjoint，指的是各部分不包含相同的頂點）」的。

N和M中的每一條邊要麼交替地出現在同一分枝中，要麼出現在不同分枝中。

令

為某個分枝中的邊集，

$N_C := N\cap C$

，

$M_C:=M\cap C$

。對每一個分枝，如果

是偶數，則

；如果

是奇數，則要麼

要麼

。

如果對於某個大於零的整數k有

也即N中的邊比M中的邊多k條，則至少有

個連通分枝使得

，且它們是 M-augmenting paths。

解釋：

為方便描述，我們令

$Y=M\oplus N$

，我們考慮原圖的子圖

即由兩個匹配的對稱差的結果的邊集

和這些邊相鄰的頂點構成的子圖，對於原圖中任意一個頂點，它至多隻被一條匹配邊覆蓋，那麼對於任意兩個匹配（M和N）的並集，其中的頂點要麼被M覆蓋，要麼被N覆蓋，要麼同時被M和N覆蓋。

Y中的邊是M和N的並集再去掉它們的交集（對稱差的定義），因此G‘中的頂點也就滿足上述性質，因此這些頂點的度數最大為2，也即對任意的

$v\in \delta(Y), deg(v)\le 2$

因此無論G’中包含多少連通分枝，這些分枝中的所有點，度數最大為2，那麼它們只可能是path或者cycle。

引理 1。1：在

$N\oplus M$

的同一個component中，M中的邊和N中的邊必然是交替出現的。

因為：1、component中的邊是連續的；2、這些邊要麼屬於M要麼屬於N；3、根據matching的定義，兩條相鄰的邊必然不能同時屬於M或者同時屬於N。因此引理成立。

引理 1。2：如果

，也即N中的邊比M中多k條，那麼在

$N\oplus M$

中必然存在至少k個path，使得N在path中的邊數比M在path中的邊數多1（因為每個path至多多1條邊）。而這些path可看做

path。

證明：如果分枝是cycle，則必然是偶數條邊（因為如果是奇數，根據引理1。1，由於該cycle的邊一定是M和N交替出現的，必然有一個點要麼被M匹配了兩次要麼被N匹配了兩次，不符合匹配的定義），則說明在M中的邊和在N中的邊數量相等（出現在該分枝中的）。

如果是path，如果是偶數條邊，則和cycle一樣，如果是奇數條邊，則要麼是N中的邊數多1，要麼是M中的邊數多1。

因此對於

，那麼肯定至少有k個path滿足

，而這些path是M-alternating的，M中的匹配邊比非匹配邊少1（N中的邊是M的非匹配邊），根據M-augmenting path的定義，這些path都是M-augmenting path。因此定理成立。

增廣路定理（［Petersen （1891）］［Kőnig （1931）］［Berge （1957）］）

M是一個最大匹配當且僅當不存在M-augmenting path。

根據該定理，我們能很快想到一個求最大匹配的演算法：

初始化一個匹配集M

只要圖中還存在M-augmenting path，則利用對稱差增廣它

看起來很簡單，然而有一個問題是：如何（在多項式時間內）尋找增廣路？

Augmenting Graph

我們的主角終於登場了！

令

$G=(U\cup W,E)$

是一個二部圖，

是G的一個匹配，我們將原圖的無向邊改成有向邊：未匹配的邊從U到W，匹配的邊從W到U，這樣便得到一個M-augmenting graph

。

M-augmenting graph

： edges in M are oriented from W to U ， others from U to W。

我們再令：

分別表示U和W中未匹配的頂點

可從

到達的頂點（包括

自身）

M-augmenting graph擁有一些非常好用的性質：

從

的點出發到

的點結束的path一定是一條

path。因為一條M-augmenting path一定是從未匹配的點出發，最終又是以未匹配的點結束，則一定是從

的點出發，到

的點結束。

$R_M\cap W_M=\emptyset\Leftrightarrow$

M is maximum。如果從

中任意點出發，所能到達點都不在

中，則說明不存在M-augmenting path，根據定理，M是最大匹配。

所有左邊的匹配點有且只有一條入邊；所有右邊的匹配點只有一條出邊。根據matching的定義和M-augmenting graph的構造方法，Trivial。

所有的匹配邊的兩個端點，要麼都在

中，要麼都不在。因為在

中的點是

可達的，如果一條匹配邊，起點在

中，則該起點可從

到達，終點可從起點到達，則終點也可從

到達，終點也在

中；如果一條匹配邊，起點不在

中，則由於終點可從該起點到達且只能從該起點到達，且

中的點都不能到達該起點，則

中的點都不能到達該終點，則終點不在

中。

沒有從

離開（到

$V\setminus R_M$

）的邊。Trivial，由於

是

可達的，如果有那麼一條邊連線一個不是

中的點，則這個點也應該是

可達的，也應該納入

中；

M-augmenting graph不僅可以用來求解二部匹配問題（下面會詳細說演算法），還能求解頂點覆蓋（vertex cover）和穩定集（stable set）問題：

G中沒有邊連線

$U\cap R_M$

和

$W\setminus R_M$

$I:=(U\cap R_M)\cup(W\setminus R_M)$

是一個穩定集，且

$C:=(U\setminus R_M)\cup(W\cap R_M)$

是一個頂點覆蓋，且

Evolution of Augmenting graph

設P 是一條M-augmenting path，令

$N=M\oplus P$

：表示由

增廣後得到的圖（翻轉所有在P中的邊即可）

$U_N\subset U_M,W_N\subset W_M$

$R_N\subseteq R_M$

如圖，左邊是

，其中一條增廣路為

，其中紅色為未匹配邊，藍色為匹配邊。增廣後，為保持augmenting graph的性質（所有匹配邊從W到U），則只需翻轉這條增廣路中的所有邊的方向即可，得到右邊的圖

，原紅色邊變為匹配邊，藍色邊變為未匹配邊。

接下來我們來看看一個重要的中間結論，在後面的證明中會用到該結論：

引理2。1：設

是二部圖中的一個匹配，

為一條最短的M-augmenting path，

為

$M\oplus P-$

augmenting path，（Q為P增廣後得到的path再在兩端加上兩條未匹配邊，這樣Q才是一條augmenting path），則有

$|Q|\ge |P| + 2|P\cap Q|$

證明：

令

$N:=M\oplus P\oplus Q$

，由於Q是一條

$M\oplus P-$

augmenting path，就相當於先設

，則Q是一條

augmenting path，

，那麼N就是對Q增廣後得到的匹配，相當於對M連續增廣了兩次，那麼有

。

根據引理1。2，

$N\oplus M$

會得到2條disjoint M-augmenting path ，令它們為

，由於

是最短的M-augmenting path，則

$|P|\le |P_1|,|P|\le|P_2|$

。

根據對稱差的性質，

$\begin{align}&\ N=M\oplus P\oplus Q\\&\Rightarrow M\oplus N=M\oplus M\oplus P\oplus Q\\&\Rightarrow M\oplus N=P\oplus Q\end{align}$

因此

$\underbrace{|P\oplus Q|=|P|+|Q|-2|P\cap Q|}_{對稱差的定義}=\underbrace{|M\oplus N|\ge |P_1|+|P_2|}_{引理1.2}\ge 2|P|$

移項得到

$|Q|\ge |P| + 2|P\cap Q|$

Basic algorithm

根據augmenting graph的性質，我們能很快想到一個最基本的演算法：

Pseudo code：

$\begin{array}{l}&M\leftarrow \emptyset \\&repeat \\&\ \ \ \ Find\ a\ path\ P\ in\ D_M\ from\ U_M\ to\ W_M\\&\ \ \ \ If\ P\ is\ not\ found,\ return\ M\\&\ \ \ \ M\leftarrow M\oplus P \\\end{array}$

一開始令集合 M為空集

然後開始迴圈：1、尋找一條增廣路P（從

到

），如果找不到，則返回M；2、增廣這條路（

$M=M\oplus P$

）。

每次迴圈是在

中尋找增廣路，則迴圈次數不超過頂點數，為

，每次增廣需要操作的次數不超過邊數數，為

，因此時間複雜度為

。

Hopcroft-Karp Algorithm

Pseudo code：

$\begin{array}{l}&M\leftarrow \emptyset \\&repeat \\&\ \ \ \ Find\ a\ maximal\ collection\ of\ vertex-disjoint\ shortest\ augmenting\ paths\ in\ D_M\ from\ U_M\ to\ W_M\\&\ \ \ \ \mathcal{P}\leftarrow \{P_1,P_2,...,P_k\}\ maximal\ set\ of\ vertex-disjoint\ shortest\ augmenting\ paths \\&\ \ \ \ M\leftarrow M\oplus (P_1\cup P_2\cup\cdots\cup P_k) \\&until\ \mathcal{P}=\emptyset \\&return\ M\end{array}$

Hopcroft-Karp

演算法每次迭代時尋找多條長度相等的增廣路來提升演算法效率，這些增廣路是vertex-disjoint的，因此它們之間沒有相交的點或邊。每次迭代找到的增廣路形成的集合是一個極大的集合（inclusion-wise maximal），也即如果我們令這個集合為

$\mathcal{P}$

，那麼不存在另一個增廣路集合

$\mathcal{P}$

使得

$\mathcal{P}\subset \mathcal{P}$

。

演算法開始時，由於還沒有匹配邊，也即

$M=\emptyset$

，此時

，在Augmenting graph中，所有的邊由U指向W。

我們透過BFS從

開始遍歷，生成一棵廣度優先搜尋樹（level graph），若找到一個在

中的點

，即v是未匹配點，則我們找到了一條增廣路，記錄此時的搜尋深度（level）為

（BFS的第一個點的level為0），那麼該增廣路長度為k。

我們找到所有長度為k的增廣路

$\mathcal{P}= \{P_1,P_2,...,P_k\}$

，使得

$\mathcal{P}$

是極大的。

接下來就可以利用對稱差對所有的這些增廣路進行增廣。若某次迭代時我們再也找不到增廣路，則說明此時的匹配M就是最大匹配。

Correctness and complexity

演算法的正確性根據增廣路定理是顯然成立的，我們接下來根據一系列有趣的結論來推導其時間複雜度。

引理3。1：每次迭代結束後，所有最短增廣路的長度會至少增加2。

證明：首先我們令

為本次迭代時得到的匹配，

為上次迭代時的匹配，也即

$N=M\oplus \mathcal{P}$

，

為一條最短的

path。

情況1：

和所有上次迭代時選擇的M-augmenting path都是vertex-disjoint的，也即Q中所有點都不在這些M-augmenting path中。

因此上次迭代中，對M進行增廣時，並未影響到Q，否則Q中的匹配邊本就是

$\mathcal{P}$

中的一員，就不滿足情況1的假設了。

而在上次迭代中由於沒有影響到Q，本次迭代時與上次迭代時Q是沒有變化的，則Q在上次迭代中仍然是一條augmenting path，且是一條M-augmenting path（因為上次迭代時匹配為M）。

但是上次迭代時並沒有把Q選入

$\mathcal{P}$

，為什麼呢？只能是因為Q不是最短的M-augmenting path！因此我們有

最短的M-augmenting path的長度。而增廣路一定是奇數長度的，因此

的長度至少比最短的M-augmenting path的長度多2。

因此情況1，引理成立。

情況2：

與上次迭代中的一條最短的M-augmenting path

共享一個頂點

，也即Q中的一個頂點v也存在於P中且P是最短的M-augmenting path。

可見情況1和情況2是互補的，因此一旦在情況2中引理也成立的話，那麼引理本身就是成立的。

如圖，

有兩種情況：

在

中的某條匹配邊的末端（此時

$v\in U$

），或

是

中某條匹配邊的起始點（圖中記為

，且此時

$v\in W$

）。無論是哪種情況，由於P是alternating的，因此P中有且只有一條

非匹配邊

與

相鄰。

P增廣後，根據之前提到的

Evolution of augmenting graph

，P中的邊均會反向，使得原匹配邊變為非匹配邊，原非匹配邊變為匹配邊。

還記得在最開始介紹augmenting graph時提到的一個性質嗎？

所有U中的匹配點有且只有一條入邊；所有W中的匹配點只有一條出邊。

如圖，若

$v\in U$

，也即之前出現在匹配邊的末端，則增廣後，

就是

的末端，且

變成了匹配邊，此時

有且只有一條入邊，那就只能是

了，而由於v也在Q中，那麼只能

也在Q中；

若

$v\in W$

，也即v之前出現在匹配邊的始端，則增廣後，v就是e的始端，且e變成了匹配邊，此時v有且只有一條出邊，那就只能是

了，而由於v也在Q中，那麼只能

也在Q中。

因此無論v是哪種情況，在P中都存在一條邊e也出現在Q中，則

$\{e\} \subseteq P\cap Q$

，這就說明

$|P\cap Q|\ge 1$

。根據引理2。1，

$|Q|\ge | P|+2|P\cap Q|$

，那麼

$|Q|-|P|\ge 2$

，引理成立。

引理3。2：令N為演算法結束後得到的最大匹配，

$\alpha$

，

為當前匹配。k次迭代結束後，

$|M|\ge (\frac{k}{k+1})\alpha$

。

證明：由於每次迭代我們都只操作（增廣）了最短增廣路，因此根據引理3。1，在k次迭代結束後，任意的M-augmenting path的長度

$\ge 2k+1$

（在第一次迭代時也即還沒有任何匹配邊時，最短增廣路長度=1），又根據引理1。2，

$M\oplus N$

至少包含

個點分離的M-augmenting path。

那麼

$|M\oplus N|\ge (2k+1)(|N|-|M|)$

而

$|M\oplus N|=|M|+ |N|-2|M\cap N|\le |M|+|N|$

因此

$(2k+1)(|N|-|M|)\le |M|+|N| \Rightarrow |M|\ge (\frac{k}{k+1})|N|$

證畢。

當然這個引理也可以寫作

$\alpha$

引理3。3： Hopcroft-Karp Algorithm的時間複雜度為

$O(m\sqrt{n})$

。

其中m為圖的邊數，n為頂點數，也即對於一個無向圖

。這個根號很有意思，它是怎麼來的呢，利用之前得到的結論，我們可以進行證明：

取一個特殊的

$k=\lfloor(\alpha$

，那麼

$k+1\ge \lceil(\alpha$

，在k次迭代後，有

$\alpha$

由於

$\alpha$

是整數，因此也等價於

$\alpha$

由於我們每次迭代會讓

的邊數至少+1，既然最大匹配數是

$\alpha$

，當前匹配是

，那麼剩下的迭代次數就

$\le\alpha$

。

那麼總共的迭代次數=已經迭代的k次加上剩餘的迭代次數

$\le 2k=2\lfloor(\alpha$

，則我們得到了總迭代次數的上界

$O(\sqrt{\alpha$

，由於每一個點至多與一條匹配邊相鄰，因此

與

$\alpha$

之間的關係是線性的，則

$O(\sqrt{\alpha$

，而每次迭代時所需的增廣時間為

，因此演算法的時間複雜度為

$O(m\sqrt{n})$

。

後記

其實在組合最佳化中，很多演算法本身是十分簡單易懂的，它們的難點在於分析其正確性和時間複雜度。 Hopcroft-Karp演算法的複雜度分析是一個十分有趣的過程，如果你也能跟著這篇文章一步步分析下來，那麼你對於該演算法，以及二部圖匹配和增廣路演算法會掌握的更深刻。

標簽： path 匹配增廣 augmenting 迭代

上一篇:默克生命科學sigma乾貨|過渡金屬催化劑有哪些

下一篇：探索異形鑽的魅力（二）——墊形枕形

二部圖最大匹配——新資料結構Augmenting graph與Hopcroft-Karp演算法的複雜度證明

猜你喜歡

《增廣賢文》：近水知魚性，近山識鳥音。

快速迭代的人工智慧

圖神經網路自監督學習之 GCL-Aug-BS

我這樣的程式設計師是不是太懶了？

二十一天說敏捷-【D1】敏捷概述

二部圖最大匹配——新資料結構Augmenting graph與Hopcroft-Karp演算法的複雜度證明

猜你喜歡

《增廣賢文》：近水知魚性，近山識鳥音。

快速迭代的人工智慧

圖神經網路自監督學習 之 GCL-Aug-BS

我這樣的程式設計師是不是太懶了？

二十一天說敏捷-【D1】敏捷概述

圖神經網路自監督學習之 GCL-Aug-BS