2021 Week17 - Matching

--- tags: 成大高階競技程式設計 2021 --- # 2021 Week17 - Matching 註：:bulb: 代表相對少見、較進階或與主題關聯性較低的內容，讀者可自行斟酌觀看。 --- # 匹配（Matching） # 最大匹配（Maximum Cardinality Matching） ```graphviz graph { A [label="A", style=filled]; B [label="B", style=filled]; C [label="C"]; D [label="D", style=filled]; E [label="E", style=filled]; F [label="F", style=filled]; G [label="G", style=filled]; A -- B [style=bold, color="#B000B0"]; A -- C; A -- D; C -- F; B -- E; D -- E [style=bold, color="#B000B0"]; F -- G [style=bold, color="#B000B0"]; } ``` > 二個節點有邊相連時，彼此可以形成一對，同時不再與其他點配對。 **一個圖 $G$ 上兩兩不相鄰的邊組成一個集合 $M$，稱為圖上的一個匹配（matching）。** > * 匹配邊（matched edge）：$M$ 中的邊 > * 非匹配邊（unmatched edge） > * 匹配點（matched vertex）：某個匹配邊的端點 > * 非匹配點（unmatched vertex） > <br> > * 最大匹配（maximum matching）：所有 $G$ 的匹配中，匹配邊最多的匹配 > * 完美匹配（perfect matching）：$G$ 的所有節點均為匹配點 <hr class="thin"> #### 交錯路徑 ```graphviz graph { rankdir=LR; A [label=""]; node [label="", style=filled]; A -- B; B -- C [style=bold, color="#B000B0"]; C -- D; D -- E [style=bold, color="#B000B0"]; } ``` $G$ 上的一條路徑，邊由 $M$ 的匹配邊與非匹配邊交錯組成，且起點為非匹配點，稱為 $M$-交錯路徑（$M$-alternating path）。 <hr class="thin"> #### 可擴增路徑 ```graphviz graph { rankdir=LR; A [label=""]; B [label="", style=filled]; C [label="", style=filled]; D [label=""]; A -- B; B -- C [style=bold, color="#B000B0"]; C -- D; } ``` **一條 $M$-交錯路徑（$M$-alternating path），起點與終點皆為非匹配點，稱為 $M$-可擴增路徑（$M$-augmenting path）。** > 「$M$-」代表它跟匹配 $M$ 有關。將一條 $M$-可擴增路徑 $P$ 擴增，匹配邊變成非匹配邊，非匹配邊變成匹配邊，可以得到一個更大的匹配 $M'=M\;\triangle\; P=(M\cup P)\setminus (M\cap P)$。 > $\triangle$ 是對稱差（symmetric difference）。 > ```graphviz > graph { > rankdir=LR; > label="Augmented :"; > fontsize=15; > labelloc=t; > labeljust=l; > > A [label="", style=filled]; > B [label="", style=filled]; > C [label="", style=filled]; > D [label="", style=filled]; > > A -- B [style=bold, color="#B000B0"]; > B -- C; > C -- D [style=bold, color="#B000B0"]; > } > ``` <hr class="dotted"> ### Berge's lemma :::danger **一個匹配 $M$ 是最大匹配若且唯若不存在 $M$-可擴增路徑。** ::: > #### 證明:bulb: > > 1. 如果存在 $M$-可擴增路徑，就可以得到更大的匹配，所以 $M$ 就不是最大匹配。 > 2. 如果不存在 $M$-可擴增路徑，對於任意一個匹配 $M'$， > 考慮 $M\;\triangle\;M'$ 所構成的圖 $H$，$\Delta(H)\le 2$， > 所以 $H$ 的每個連通部分要不是路徑就是環。 > > 如果是路徑的話，一定是 $M$-交錯路徑， > 但是根據假設，它不是 $M$-可擴增路徑， > 所以路徑上屬於 $M$ 的邊不少於屬於 $M'$ 的邊； > 如果是環的話，環上屬於 $M$ 的邊跟屬於 $M'$ 的邊一樣多。 > > 得到結論，$|M|\ge |M'|$，所以 $M$ 是最大匹配。 > > > $\Delta(G)$ 代表圖 $G$ 的最大度數（maximum degree）。 <hr class="thin"> #### 奇點／偶點 ```graphviz digraph { rankdir=LR; A [label="", color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; A -> B [arrowhead=o]; B -> C [style=bold, arrowhead=o, color="#B000B0"]; C -> D [arrowhead=o]; D -> E [style=bold, arrowhead=o, color="#B000B0"]; } ``` 一條交錯路徑上，距離起點基數條邊的點為**奇點（odd vertex）**；距離起點偶數條邊的點為**偶點（even vertex）**（包含起點）。 > 交錯路徑並沒有真的起點，端看我們怎麼看它， > 而在尋找時，通常以某個非匹配點作為起點開始。 <hr class="dashed"> ## 二分圖最大匹配（Maximum Cardinality Bipartite Matching） > 二分圖，代表節點可以被分為二個集合，同個集合內的節點不能有邊相連。 ```graphviz graph { rankdir=LR; subgraph cluster_X { style=dashed; label="X"; A [label="0", fontcolor="#FF0000", style=filled]; B [label="1", fontcolor="#FF0000", style=filled]; C [label="2", fontcolor="#FF0000"]; } subgraph cluster_Y { style=dashed; label="Y"; a[label="0", fontcolor="#0000FF", style=filled]; b[label="1", fontcolor="#0000FF", style=filled]; c[label="2", fontcolor="#0000FF"]; } A -- a [style=bold, color="#B000B0"]; A -- c; B -- a; B -- b [style=bold, color="#B000B0"]; C -- a; C -- b; } ``` 因為可擴增路徑長度是奇數，二分圖上的一條可擴增路徑，兩個非匹配點一定分屬集合 $X,Y$。因此在找可擴增路徑時，只需要**以 $X$ 中的非匹配點為起點**就可以了。 > 交錯路徑上，**$X$ 的點都是偶點，$Y$ 的點都是奇點**。 ```graphviz digraph { rankdir=LR; A [label="0", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"]; C [label="2", fontcolor="#FF0000", color="#FF0000"]; a[label="0", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"]; c[label="2", fontcolor="#0000FF", color="#0000FF"]; C -> a [arrowhead=o]; a -> A [style=bold, color="#B000B0", arrowhead=o]; A -> c [arrowhead=o]; } ``` 以一個某個 $X$ 中的起點，沿著不同的交錯路徑往下找，交錯路徑 $P_1,P_2$ 可能會出現重疊的情況，但是在 $P_2$ 上，$P_1$ 的偶點還是偶點，奇點還是奇點，也就是說 $P_1$ 從交會點往下走，與 $P_2$ 從交會點往下走，是否能變成可擴增路徑的結果是一樣的，而且最終也只能選擇一條，所以**當路徑遇到已經被拜訪過的節點，不考慮往此節點繼續走**。 ```graphviz digraph { rankdir=LR; A [label="0", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="1", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"]; C [label="2", fontcolor="#FF0000", color="#FF0000"]; a[label="0", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"]; b[label="1", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"]; c[label="2", fontcolor="#0000FF", color="#0000FF"]; C -> a [arrowhead=o]; a -> A [style=bold, arrowhead=o, color="#B000B0"]; A -> c [arrowhead=o]; C -> b [arrowhead=o]; b -> B [style=bold, arrowhead=o, color="#B000B0"]; B -> a [style=dotted, arrowhead=o]; } ``` > **奇點到偶點是匹配邊，偶點到奇點是非匹配邊**， > 因為奇點的匹配邊唯一，只會到唯一的偶點（並且沒被拜訪過）， > **cross edge 只可能是「偶點到奇點」或「偶點到偶點」的邊**； > 又因為二分圖沒有偶點到偶點（$X$ 到 $X$）的邊， > 因此遇到被拜訪過的點，也就是 **cross edge，一定是偶點到奇點的邊**。 <hr class="dotted"> ### Augmenting Path Algorithm 依序以 $X$ 中每個非匹配點為起點，進行 DFS，尋找可擴增路徑，如果有找到的話就進行擴增，最後就可以得到最大匹配。 > 為什麼可以這樣做呢？ > 如果演算法結束後，每個 $X$ 的非匹配點都沒有可擴增路徑， > 根據 Berge's lemma，匹配就是最大匹配了。 > > 首先擴增只會把某些非匹配點變為匹配點，所以演算法結束後還是 $X$ 的非匹配點， > 代表一開始它就是 $X$ 的非匹配點，我們已經確認過不存在以它為起點的可擴增路徑。 > 因此剩下要確認的就是，**原本沒有可擴增路徑的點，在進行擴增後，還是沒有可擴增路徑**。 > > #### 證明:bulb: > 假設對於可擴增路徑 $P_v=v_0\dots v_k$ 進行擴增， > 造成另一個 $X$ 的非匹配點 $u_1$，因此多了一條可擴增路徑 $P_u=u_1\dots u_2$， > 則 $P_u$ 與 $P_v$ 一定有部分重疊路徑 $v_i\dots v_j$。 > > ```graphviz > digraph { > rankdir=LR; > label="Before :"; > fontsize=30; > labelloc=t; > labeljust=l; > > A [label="v0", fontcolor="#FF0000", color="#FF0000"]; > B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > C [label="vi", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"]; > D [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="vj", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"]; > G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > H [label="vk", fontcolor="#0000FF", color="#0000FF"]; > > a [label="u1", fontcolor="#FF0000", style=dashed]; > b [label="", style="filled, dashed", fillcolor=lightgray]; > c [label="", style="filled, dashed", fillcolor=lightgray]; > d [label="u2", fontcolor="#0000FF", style=dashed]; > > A -> B [arrowhead=o]; > B -> C [style=bold, arrowhead=o, color="#B000B0"]; > C -> D [arrowhead=o]; > D -> E [style=bold, arrowhead=o, color="#B000B0"]; > E -> F [arrowhead=o]; > F -> G [style=bold, arrowhead=o, color="#B000B0"]; > G -> H [arrowhead=o]; > > b -> a [style=dashed, dir=none]; > c -> b [style="bold, dashed", dir=none, color="#B000B0"]; > F :ne -> c [style=dashed, dir=none]; > d -> C :sw [style=dashed, dir=none]; > } > ``` > > > ```graphviz > digraph { > rankdir=LR; > label="After :"; > fontsize=30; > labelloc=t; > labeljust=l; > > A [label="v0", fontcolor="#FF0000", style=filled, fillcolor=lightgray]; > B [label="", style=filled, fillcolor=lightgray]; > C [label="vi", fontcolor="#FF0000", style=filled, fillcolor=lightgray, color="#FF0000"]; > D [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="vj", fontcolor="#0000FF", style=filled, fillcolor=lightgray, color="#0000FF"]; > G [label="", style=filled, fillcolor=lightgray]; > H [label="vk", fontcolor="#0000FF", style=filled, fillcolor=lightgray]; > > a [label="u1", fontcolor="#FF0000", style=dashed, color="#FF0000"]; > b [label="", style="filled, dashed", fillcolor=lightgray, color="#0000FF"]; > c [label="", style="filled, dashed", fillcolor=lightgray, color="#FF0000"]; > d [label="u2", fontcolor="#0000FF", style=dashed, color="#0000FF"]; > > A -> B [style=bold, dir=none, color="#B000B0"]; > B -> C [dir=none]; > C -> D [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > D -> E [dir=back, arrowtail=o]; > E -> F [dir=back, style=bold, arrowtail=o, color="#B000B0"]; > F -> G [dir=none]; > G -> H [dir=none, style=bold, color="#B000B0"]; > > b -> a [style=dashed, dir=back, arrowtail=o]; > c -> b [style="bold, dashed", dir=back, arrowtail=o, color="#B000B0"]; > F :ne -> c [style=dashed, dir=back, arrowtail=o]; > d -> C :sw [style=dashed, dir=back, arrowtail=o]; > } > ``` > > $(v_i,v_{i+1})$ 與 $(v_{j-1},v_j)$ 擴增前一定是非匹配邊，因此如圖所示， > 擴增前 $u_1$ 應該要有可擴增路徑（$u_1\dots v_k$），與假設衝突，原命題成立。 > > > 如果 $(v_i,v_{i+1})$ 或 $(v_{j-1},v_j)$ 擴增前是匹配邊，擴增後是非匹配邊， > > $(P_u\setminus P_v)$ 上要有另一條匹配邊連接著 $v_i$ 或 $v_j$， > > 但是 $(v_{i-1},v_i)$ 與 $(v_j,v_{j+1})$ 也是匹配邊，這就不是匹配了。 <hr class="dotted"> 實作上，**DFS 只停留在 $X$ 的點**，**每次走一條非匹配邊**，若此時遇到的是 $Y$ 的非匹配點，就找到可擴增路徑了；如果是 $Y$ 的匹配點，則**直接接著再走一條匹配邊**，到另一個 $X$ 的點。 > $Y$ 的點的匹配邊唯一，這就是為什麼只以 $X$ 的點為基準， > 並且每次走二條邊（**一條非匹配邊 $+$ 一條匹配邊**）。 ```cpp! class BipartiteMatching { vector<bool> vis; vector<int> mx{}, my{}; bool dfs(const vector<vector<int>>& adj, int x) { for (auto& y : adj[x]) { if (vis[y]) continue; vis[y] = true; if (my[y] == -1 || dfs(adj, my[y])) { mx[x] = y, my[y] = x; return true; } } return false; } public: pair<vector<int>, vector<int>> operator()(const vector<vector<int>>& adj, int ny) { vis.resize(ny), mx.assign(adj.size(), -1), my.assign(ny, -1); int c{0}; for (int x{0}; x < adj.size(); ++x) { fill(vis.begin(), vis.end(), false); if (dfs(adj, x)) ++c; } return {move(mx), move(my)}; } }; ``` 每個點進行一次 DFS，複雜度為 $O(|V|(|V|+|E|))=O(|V||E|)$。 <hr class="dotted"> #### greedy matching 先找到一個極大匹配，不要從空的匹配開始。 > 一個極大匹配，不為任何其他匹配的子集。 ```cpp! for (int x{0}; x < adj.size(); ++x) // greedy matching for (auto& y : adj[x]) { if (my[y] != -1) continue; mx[x] = y, my[y] = x, ++c; break; } ``` <hr class="dashed"> ### Hopcroft-Karp Algorithm Augmenting Path Algorithm 透過 DFS 搜尋，常常去找較長的可擴增路徑，導致複雜度並不優異； Hopcroft-Karp Algorithm 改為尋找最短的可擴增路徑，我們沒辦法事先知道最短可擴增路徑的起點是誰，因此以所有 $X$ 的非匹配點當作樹根，進行 BFS。 > 如果分別從 $x_i,x_j$ 開始尋找，當它們交會時， > 在 $x_i$ 繼續找下去的結果與 $x_j$ 一致， > 所以只從 $x_i$ 找下去即可，與之前的結論相同， > **當路徑遇到已經被拜訪過的節點，不往此節點進行搜尋**。這邊只是「尋找」可擴增路徑，還沒有進行擴增，所以路徑重疊沒關係。 ```graphviz digraph { rankdir=LR; A [label="xi", fontcolor="#FF0000", color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", color="#0000FF"]; D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; a [label="xj", fontcolor="#FF0000", color="#FF0000"]; b [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; A :e -> B :nw [arrowhead=o]; B -> C [style=bold, arrowhead=o, color="#B000B0"]; C :ne -> D1 :w [arrowhead=o]; D1 -> E [style=bold, arrowhead=o, color="#B000B0"]; E -> F [arrowhead=o]; C :se -> D2 :w [arrowhead=o]; a -> b [arrowhead=o]; b -> c [style=bold, arrowhead=o, color="#B000B0"]; c :e -> B :sw [style=dashed, arrowhead=o]; } ``` 那為什麼不能跟之前一樣保留一條路徑就好呢？因為 $x_i$ 可能有多條可擴增路徑，最後不一定會擴增重疊的部分。 ```graphviz digraph { rankdir=LR; A [label="xi", fontcolor="#FF0000", color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", color="#0000FF"]; D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; H [label="", color="#0000FF"]; I [label="", color="#0000FF"]; D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; J [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; K [label="", color="#0000FF"]; a [label="xj", fontcolor="#FF0000", color="#FF0000"]; b [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; A -> B [arrowhead=o]; B -> C [style=bold, arrowhead=o, color="#B000B0"]; C :ne -> D1 :w [arrowhead=o]; D1 -> E [style=bold, arrowhead=o, color="#B000B0"]; E -> F [arrowhead=o]; C :e -> D2 :nw [arrowhead=o]; D2 -> G [style=bold, arrowhead=o, color="#B000B0"]; G -> H [arrowhead=o]; G -> I [arrowhead=o]; C :se -> D3 :nw [arrowhead=o]; D3 -> J [style=bold, arrowhead=o, color="#B000B0"]; J -> K [arrowhead=o]; a -> b [arrowhead=o]; b -> c [style=bold, arrowhead=o, color="#B000B0"]; c :e -> D3 :sw [style=dashed, arrowhead=o]; } ``` 1. 重複步驟 $2,3$，直到沒有可擴增路徑為止 2. 把**所有的 $X$ 非匹配點**當作樹根，透過 BFS，尋找**所有最短可擴增路徑** 3. 對於 BFS 森林的每個樹葉，透過 **DFS 回溯，找可擴增路徑並擴增** > 可擴增路徑有可能重疊，因此在擴增後，要把這條路徑**從 BFS 森林中移除**。 > > 不是有 $k$ 條可擴增路徑，就代表可以擴增 $k$ 次。步驟 $2$ 嚴格來說，是找到一個「點不重複的最短可擴增路徑」的極大集合（a maximal set of vertex-disjoint shortest augmenting paths）；換句話說，這些路徑都可以進行擴增，並且擴增後，就不存在其他長度相等的可擴增路徑。 > 下面二種情況都是極大集合： > > ```graphviz > digraph { > rankdir=LR; > > A [label="xi", fontcolor="#FF0000", color="#FF0000"]; > B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="", color="#0000FF"]; > D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > H [label="", color="#0000FF"]; > I [label="", color="#0000FF"]; > D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > J [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > K [label="", color="#0000FF"]; > > a [label="xj", fontcolor="#FF0000", color="#FF0000"]; > b [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > > A -> B [dir=back, arrowtail=o]; > B -> C [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > C :ne -> D1 :w [dir=none]; > D1 -> E [style=bold, dir=none, color="#B000B0"]; > E -> F [dir=none]; > C :e -> D2 :nw [dir=none]; > D2 -> G [style=bold, dir=none, color="#B000B0"]; > G -> H [dir=none]; > G -> I [dir=none]; > C :se -> D3 :nw [dir=back, arrowtail=o]; > D3 -> J [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > J -> K [dir=back, arrowtail=o]; > > a -> b [dir=none]; > b -> c [style=bold, dir=none, color="#B000B0"]; > c :e -> D3 :sw [style=dashed, dir=none]; > } > ``` > > ```graphviz > digraph { > rankdir=LR; > > A [label="xi", fontcolor="#FF0000", color="#FF0000"]; > B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > D1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="", color="#0000FF"]; > D2 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > H [label="", color="#0000FF"]; > I [label="", color="#0000FF"]; > D3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > J [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > K [label="", color="#0000FF"]; > > a [label="xj", fontcolor="#FF0000", color="#FF0000"]; > b [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > > A -> B [dir=back, arrowtail=o]; > B -> C [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > C :ne -> D1 :w [dir=none]; > D1 -> E [style=bold, dir=none, color="#B000B0"]; > E -> F [dir=none]; > C :e -> D2 :nw [dir=back, arrowtail=o]; > D2 -> G [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > G -> H [dir=back, arrowtail=o]; > G -> I [dir=none]; > C :se -> D3 :nw [dir=none]; > D3 -> J [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > J -> K [dir=back, arrowtail=o]; > > a -> b [dir=back, arrowtail=o]; > b -> c [style=bold, dir=back, arrowtail=o, color="#B000B0"]; > c :e -> D3 :sw [style=dashed, dir=back, arrowtail=o]; > } > ``` 乍看之下，BFS 森林不容易紀錄，因為樹之間可能重疊，有相同的子樹；換句話說，就是像上圖一樣有虛邊。不過我們只在意最短可擴增路徑，所以如果 $x_j$ 到交會點的長度，大於 $x_i$ 到交會點的長度，就不用考慮它了；因此這邊記錄每個節點的深度（也就是到路徑起點的距離），搭配原先的圖，就可以推斷出 BFS 森林。 <hr class="dotted"> BFS 時，一樣以 $X$ 的點為基準，每次走一條非匹配邊，如果需要繼續就直接再走匹配邊；而 DFS 時，因為從 $Y$ 的點開始回溯，一樣一次走一條非匹配邊，如果要繼續回溯，就直接走匹配邊，只差在是以 $Y$ 的點為基準。 ```cpp! // Hopcroft–Karp algorithm - O(E√V) class BipartiteMatching { vector<vector<int>> adjy; vector<int> dx, dy, mx, my; bool dfs(const vector<vector<int>>& adjx, int y) { for (auto& x : adjy[y]) { if (dx[x] + 1 != dy[y]) continue; if (mx[x] == -1 || dfs(adjx, mx[x])) { my[y] = x, mx[x] = y; dy[y] = -1; // remove from bfs forest return true; } } dy[y] = -1; // remove from bfs forest return false; } bool bfs(const vector<vector<int>>& adjx) { fill(dx.begin(), dx.end(), -1); fill(dy.begin(), dy.end(), -1); queue<int> qu{}, qu2{}; for (int x{0}; x < adjx.size(); ++x) // use all unmatched x's as roots if (mx[x] == -1) qu.push(x), dx[x] = 0; bool found{false}; while (!qu.empty() && !found) { // stop at the level found while (!qu.empty()) { auto x{qu.front()}; qu.pop(); for (auto& y : adjx[x]) if (dy[y] == -1 && my[y] != x) { dy[y] = dx[x] + 1; if (my[y] == -1) found = true; else qu2.push(my[y]), dx[my[y]] = dy[y] + 1; } } qu.swap(qu2); } return found; } public: pair<vector<int>, vector<int>> operator()(const vector<vector<int>>& adjx, int ny) { adjy.assign(ny, {}); for (int x{0}; x < adjx.size(); ++x) for (auto& y : adjx[x]) adjy[y].push_back(x); dx.resize(adjx.size()), dy.resize(ny), mx.assign(adjx.size(), -1), my.assign(ny, -1); int c{0}; while (bfs(adjx)) { for (int y{0}; y < ny; ++y) if (my[y] == -1 && dy[y] != -1) c += dfs(adjx, y); } return {move(mx), move(my)}; } }; ``` <hr class="thin"> :::danger （引理 1.）對於圖 $G$ 上的二個匹配 $M_a,M_b$，如果 $|M_a|\gt|M_b|$，則 $M_b$ 至少有 $|M_a|-|M_b|$ 條（點不重複的）可擴增路徑。 ::: 考慮子圖 $H=M_a\;\triangle\; M_b$，$H$ 的連通部分不是路徑就是環，而且一定是 $M_a$ 的邊與 $M_b$ 的邊交錯，因此連通部分有三種可能， $M_a$ 的邊比 $M_b$ 的邊多 $1$；$M_a$ 的邊與 $M_b$ 的邊一樣多；$M_a$ 的邊比 $M_b$ 的邊少 $1$。因為 $M_a$ 的匹配邊比 $M_b$ 多了 $|M_a|-|M_b|$ 條，所以至少**有這麼多的連通部分**， $M_a$ 的邊會比 $M_b$ 的邊多 $1$，而這樣的連通部分，就**是 $M_b$ 的可擴增路徑**。 ```graphviz digraph { rankdir=LR; subgraph cluster_3 { label="Mb 的邊多 1："; fontsize=20; labelloc=t; labeljust=l; J [label=""]; K [label=""]; L [style=invis]; M [style=invis]; J -> K [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond]; K -> L [style=invis]; L -> M [style=invis]; } subgraph cluster_2 { label="一樣多："; fontsize=20; labelloc=t; labeljust=l; E [label=""]; F [label=""]; G [label=""]; H [label=""]; I [style=invis]; E :s -> F [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray]; F -> G :sw [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond]; E :n -> H [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond]; H -> G :nw [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray]; G -> I [style=invis]; } subgraph cluster_1 { label="Ma 的邊多 1："; fontsize=20; labelloc=t; labeljust=l; A [label=""]; B [label=""]; C [label=""]; D [label=""]; A -> B [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray]; B -> C [label="Mb", dir=both, arrowhead=ldiamond, arrowtail=rdiamond]; C -> D [label="Ma", dir=both, arrowhead=rdiamond, arrowtail=ldiamond, color=lightgray]; } } ``` <hr class="thin"> **每次的最短可擴增路徑長度都比前一次大。** > 匹配 $M1$，對 $k$ 條長度 $l$ 的最短可擴增路徑 $p_1\dots p_k$ 擴增， > 變為匹配 $M2=M1\;\triangle\; (p_1\cup \dots \cup p_k)$，而對於 $M2$ 的任意一條可擴增路徑 $p$， > > > 如果 $p$ 與 $p_1\dots p_k$ 沒有任何重疊部分， > > 因為我們已經擴增了「最短可擴增路徑的極大集合」， > > $p$ 的長度自然就大於 $l$，以下討論重疊的情況。 > > $M2$ 再對 $p$ 擴增後，變為匹配 $M3=M2\;\triangle\; p$， > 根據引理 1.，$M3$ 比 $M1$ 多了 $k+1$ 個匹配數， > 代表 $M1$ 至少要有 $k+1$ 條可擴增路徑，並且是在 $M1\;\triangle\; M3$ 中， > 因為 $M1$ 的最短可擴增路徑長度為 $l$，$M1\;\triangle\; M3$ **至少有 $(k+1)\cdot l$ 條邊**； > 而 $M1\;\triangle\; M3=(p_1\cup \dots \cup p_k)\;\triangle\; p$，$p$ 與 $p_1\cup \dots \cup p_k$ 有重疊的話， > **最多只能有 $k\cdot l+|p|-1$ 條邊**，所以得到結論，**$|p|$ 大於 $l$**。 > > $(k+1)\cdot l\le |M1\;\triangle\; M3|=|(p_1\cup \dots \cup p_k)\;\triangle\; p|\le k\cdot l+|p|-1\\\to|p|\gt l$ <hr class="thin"> **演算法在至多 $2\sqrt V$ 次後，達到最大匹配。** > **經過 $\sqrt V$ 次**，此時的匹配為 $M'$，可擴增路徑**長度至少 $\sqrt V$**； > 與最大匹配 $M$，$M\;\triangle\; M'$ 的連通部分為 $M'$ 的交錯路徑或交錯環， > 而可擴增路徑長度至少為 $\sqrt V$，代表**至多有 $\sqrt V$ 條（點不重複的）可擴增路徑**； > 這代表 **$M'$ 的匹配數最多比 $M$ 的匹配數少了 $\sqrt V$ 個**， > 所以**最多再經過 $\sqrt V$ 次後，就會達到最大匹配**。 <hr class="thin"> 每次一個 BFS 與一個 DFS，總共 $2\sqrt V$ 次，**複雜度為 $O(|E|\sqrt{|V|})$**。 <hr class="dashed"> ## 一般圖最大匹配（Maximum Cardinality Matching in a general graph） ### Edmonds' Blossom Algorithm:bulb: ```graphviz graph { rankdir=LR; S0 [label="root", color="#FF0000"]; S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -- S1; S1 -- S2 [style=bold, color="#B000B0"]; S2 -- S3; S3 -- A [style=bold, color="#B000B0"]; A :se -- B; B :e -- C [style=bold, color="#B000B0"]; A :ne -- D; D :e -- E [style=bold, color="#B000B0"]; C -- E [style=dashed]; A :e -- C [style=invis]; A :e -- E [style=invis]; A :e -- D [style=invis]; } ``` > 前面說到，因為奇點到偶點只能走唯一的匹配邊， > > 且到為匹配點的奇點時，會馬上走匹配邊到偶點， > > 確保不會有奇點到奇點的 cross edge 出現。 > > 所以 cross edge 可能是「偶點到奇點」或「偶點到偶點」的邊， > 而偶點到奇點的邊，在二分圖時已經討論過了。一般圖會出現偶點到偶點的 cross edge，形成一個奇圈（odd-length cycle），稱作花（blossom）。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [arrowhead=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [arrowhead=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [arrowhead=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=none]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 花上的奇點只要從另一側過來，就可以搖身一變成為偶點，繼續尋找可擴增路徑。 ```graphviz digraph { rankdir=LR; S0 :n -> H :s [style=invis]; H -> I :s [style=invis]; H [style=invis]; I [style=invis]; H -> D [dir=back, arrowtail=o]; F -> I [arrowhead=o]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [arrowhead=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [arrowhead=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [arrowhead=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=none]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; J [style=invis]; J -> B :s [dir=back, arrowtail=o]; } ``` <hr class="thin"> 因為花上都是偶點，所以可以進行縮花（blossom contraction），變為一個假點。 > 縮花是為了讓圖逐漸變小，減少運算量，也可以選擇不縮花。 ```graphviz digraph { rankdir=LR; S0 [label="root", color="#FF0000"]; S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; S4 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; subgraph cluster_blossom { label="Blossom"; fontsize=15; labelloc=t; labeljust=l; A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"]; } S0 -> S1; S1 -> S2 [style=bold, color="#B000B0"]; S2 -> S3; S3 -> A [style=bold, color="#B000B0"]; A -> S4; } ``` <hr class="thin"> 1. 依序以每個非匹配點當作樹根，進行步驟 $2,3$ 2. 透過 BFS 尋找可擴增路徑 * 出現花就縮花，花上的奇點變成偶點，繼續尋找 * 找到可擴增路徑就結束搜尋 3. 沿著可擴增路徑拆花並擴增 > 正確性論證與 Augmenting path algorithm 相同。 <hr class="dotted"> 實作上，花雖然是一個圈，但還是有方向性地分為二側，因此我們對二側原本的偶點，分別記錄 cross edge，以利之後可以繞花，到達另一側； > 也可以對二側的所有點進行記錄。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C :n -> G [style=dashed, arrowhead=curve]; E -> G [style=dashed, arrowhead=curve]; E -> C [style=dashed, arrowhead=curve]; G :s -> C [style=dashed, arrowhead=curve]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` 雖然花上的奇點都變為偶點，實際上還是需要知道它是哪種情況，才能決定要不要繞花，或是照著原本的路徑回去就好。 <hr class="dotted"> ```graphviz digraph { rankdir=LR; H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; J [label="", color="#0000FF"]; A -> H [dir=back, arrowtail=o]; H -> I [dir=none, style=bold, color="#B000B0"]; I -> J [dir=back, arrowtail=o]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=15; labelloc=t; labeljust=l; A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; } ``` <hr class="thin"> 先拆花。 ```graphviz digraph { rankdir=LR; H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; J [label="", color="#0000FF"]; D -> H [dir=back, arrowtail=o]; H -> I [dir=none, style=bold, color="#B000B0"]; I -> J [dir=back, arrowtail=o]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=none]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 到花之前正常進行擴增。 ```graphviz digraph { rankdir=LR; H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; J [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; D -> H [dir=none, style=bold, color="#B000B0"]; H -> I [dir=none]; I -> J [dir=none, style=bold, color="#B000B0"]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="m[y]", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="y", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=none]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 進入花的第一條匹配邊一定要變為非匹配邊。 ```graphviz digraph { rankdir=LR; H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; J [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; D -> H [dir=none, style=bold, color="#B000B0"]; H -> I [dir=none]; I -> J [dir=none, style=bold, color="#B000B0"]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="m[y]", style=filled, fillcolor=lightgray, color="#FF0000"]; E [label="y", color="#0080FF"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=none]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 遇到花上原本的奇點，進行繞花；cross edge 會變為匹配邊。 > 前面是奇點暫時變為了偶點； > 而現在這一側，奇點真正成為了偶點，偶點反而成為了奇點， > 而對面一側，奇點則回歸奇點的身份。 ```graphviz digraph { rankdir=LR; H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; J [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; D -> H [dir=none, style=bold, color="#B000B0"]; H -> I [dir=none]; I -> J [dir=none, style=bold, color="#B000B0"]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="p[c2]", color="#0000FF"]; C [label="c2", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="p[y]", style=filled, fillcolor=lightgray, color="#FF0000"]; E [label="y", color="#0080FF"]; F [label="p[c1]", color="#FF0000"]; G [label="c1", style=filled, fillcolor=lightgray, color="#0080FF"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none]; A :ne -> D [style=invis]; D :e -> E [dir=none]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none]; C -> G [style="dashed, bold", dir=none, color="#B000B0"]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 將 cross edge 二側的交錯路徑分開，得到 $y\to p[c1]$ 與 $p[c2]\to root$ 二條可擴增路徑。 ```graphviz digraph { rankdir=LR; H [style=invis]; I [style=invis]; J [style=invis]; D -> H [style=invis]; H -> I [style=invis]; I -> J [style=invis]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [label="root", color="#FF0000"]; S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="p[c2]", color="#0000FF"]; C [style=invis]; D [label="p[y]", style=dotted]; E [label="y", color="#0080FF"]; F [label="p[c1]", color="#FF0000"]; G [style=invis]; } S0 -> S1 [dir=back, arrowtail=o]; S1 -> S2 [dir=none, style=bold, color="#B000B0"]; S2 -> S3 [dir=back, arrowtail=o]; S3 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [style=invis]; A :ne -> D [style=invis]; D :e -> E [dir=none, style=dotted]; E -> F [dir=back, arrowtail=o]; F -> G [style=invis]; C -> G [style=invis]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 將 $y\to p[c1]$ 的起點看為 $y$，變成 $p[c1]\to y$，就得到二條與原先 BFS 搜尋路徑方向一致的可擴增路徑。 ```graphviz digraph { rankdir=LR; H [style=invis]; I [style=invis]; J [style=invis]; D -> H [style=invis]; H -> I [style=invis]; I -> J [style=invis]; J -> G [style=invis]; I -> F [style=invis]; H -> E [style=invis]; S0 [label="root", color="#FF0000"]; S1 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; S2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; S3 [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="p[c2]", color="#0000FF"]; C [style=invis]; D [label="p[y]", style=dotted]; E [label="y", color="#FF0000"]; F [label="p[c1]", color="#0000FF"]; G [style=invis]; } S0 -> S1 [dir=back, arrowtail=o]; S1 -> S2 [dir=none, style=bold, color="#B000B0"]; S2 -> S3 [dir=back, arrowtail=o]; S3 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [style=invis]; A :ne -> D [style=invis]; D :e -> E [dir=none, style=dotted]; E -> F [dir=back, arrowtail=o]; F -> G [style=invis]; C -> G [style=invis]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> > 花中有花呢？ > > ```graphviz > digraph { > rankdir=LR; > > H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > J [label="", color="#0000FF"]; > > D -> H [dir=back, arrowtail=o]; > H -> I [dir=none, style=bold, color="#B000B0"]; > I -> J [dir=back, arrowtail=o]; > > J -> G [style=invis]; > I -> F [style=invis]; > H -> E [style=invis]; > > S0 [style=invis]; > > subgraph cluster_blossom { > label="Blossom"; > fontsize=20; > labelloc=t; > labeljust=l; > > A [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"]; > B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > C [shape=doublecircle, label="c2", style=filled, fillcolor=lightgray, color="#FFA500"]; > D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; > } > > S0 -> A [dir=none, style=bold, color="#B000B0"]; > > A :se -> B [dir=back, arrowtail=o]; > B :e -> C [dir=none, style=bold, color="#B000B0"]; > A :ne -> D [dir=back, arrowtail=o]; > D :e -> E [dir=none, style=bold, color="#B000B0"]; > E -> F [dir=back, arrowtail=o]; > F -> G [dir=none, style=bold, color="#B000B0"]; > > C -> G [style=dashed, dir=none]; > > A :e -> C [style=invis]; > A :e -> E [style=invis]; > A :e -> F [style=invis]; > A :e -> G [style=invis]; > } > ``` > > 一樣進行拆花。 > > ```graphviz > digraph { > rankdir=LR; > > H [label="", style=filled, fillcolor=lightgray, color="#0000FF"]; > I [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > J [label="", color="#0000FF"]; > > D -> H [dir=back, arrowtail=o]; > H -> I [dir=none, style=bold, color="#B000B0"]; > I -> J [dir=back, arrowtail=o]; > > J -> G [style=invis]; > I -> F [style=invis]; > H -> E [style=invis]; > > S0 [style=invis]; > > subgraph cluster_blossom { > label="Blossom"; > fontsize=20; > labelloc=t; > labeljust=l; > > subgraph cluster_blossom2 { > label="Blossom"; > fontsize=10; > labelloc=t; > labeljust=l; > > A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; > A1 [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > A2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > A3 [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > A4 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > > A :se -> A1 [dir=back, arrowtail=o]; > A1 -> A2 [dir=none, style=bold, color="#B000B0"]; > A :ne -> A3 [dir=back, arrowtail=o]; > A3 -> A4 [dir=none, style=bold, color="#B000B0"]; > A2 -> A4 [style=dashed, dir=none]; > } > > B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > subgraph cluster_blossom3 { > label="Blossom"; > fontsize=10; > labelloc=t; > labeljust=l; > > C [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; > C1 [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > C2 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > C3 [label="c2", style=filled, fillcolor=lightgray, color="#FFA500"]; > C4 [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > > C :se -> C1 [dir=back, arrowtail=o]; > C1 :e -> C2 [dir=none, style=bold, color="#B000B0"]; > C :ne -> C3 [dir=back, arrowtail=o]; > C3 :e -> C4 [dir=none, style=bold, color="#B000B0"]; > C2 -> C4 [style=dashed, dir=none]; > } > D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; > F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; > G [label="c1", style=filled, fillcolor=lightgray, color="#FF0000"]; > } > > S0 -> A [dir=none, style=bold, color="#B000B0"]; > > A4 :se -> B [dir=back, arrowtail=o]; > B :e -> C [dir=none, style=bold, color="#B000B0"]; > A3 :ne -> D [dir=back, arrowtail=o]; > D -> E [dir=none, style=bold, color="#B000B0"]; > E -> F [dir=back, arrowtail=o]; > F -> G [dir=none, style=bold, color="#B000B0"]; > > C3 -> G [style=dashed, dir=none]; > > A :e -> C [style=invis]; > A :e -> E [style=invis]; > A :e -> F [style=invis]; > A :e -> G [style=invis]; > } > ``` > > **$c1, c2$ 要是真實的點，才能拆花，進到花中。** <hr class="dotted"> 擴增時，從終點往起點回溯，奇點到偶點是非匹配邊，一定是照著原本搜尋的反方向； **偶點到奇點**則不然，**需走配對邊**（`m[]`），不一定是父節點（`p[]`），否則**繞花的地方會出錯**。 > 回溯之時，會用到原本的配對邊， > 因此在回溯完成後，也就是遞迴返回時， > 再修改配對邊，較容易實作。 **縮花**並不是真的得生成一個新的點，只是**透過並查集，在某些地方將花視為一個整體**； **拆花**也不是要把它分開，而**是不將花看作一個整體而已**。 ```cpp! // Edmonds' Blossom Algorithm - O(VEa(V)) class Matching { int label{0}; vector<int> p{}, d{}, a{}, c1{}, c2{}, m{}; // (alternating tree), (unvisited: -1, even: 0, odd: 1), (auxiliary for lca), (cross edge) /* DSU */ vector<int> dsu_p{}, dsu_sz{}, dsu_b{}; void dsu_reset() { fill(dsu_p.begin(), dsu_p.end(), -1); fill(dsu_sz.begin(), dsu_sz.end(), 1); iota(dsu_b.begin(), dsu_b.end(), 0); } int find(int x) { // collapsing find return dsu_p[x] == -1 ? x : dsu_p[x] = find(dsu_p[x]); } int base(int x) { return dsu_b[find(x)]; } void contract(int x, int y) { // weighted union auto rx{find(x)}, ry{find(y)}; if (rx == ry) return ; auto b{dsu_b[rx]}; // treat x's base as new base if (dsu_sz[rx] < dsu_sz[ry]) swap(rx, ry); dsu_p[ry] = rx, dsu_sz[rx] += dsu_sz[ry], dsu_b[rx] = b; } /*******/ queue<int> qu{}; // only even vertices void handle_one_side(int x, int y, int b) { for (int v{base(x)}; v != b; v = base(p[v])) { c1[v] = x, c2[v] = y, contract(b, v); if (d[v] == 1) qu.push(v); // odd vertex -> even vertex } } int lca(int u, int v) { ++label; // use next number in order not to clear a while (true) { if (a[u] == label) return u; a[u] = label; if (p[u] != -1) u = base(p[u]); swap(u, v); } } void augment(int r, int y) { if (r == y) return ; if (d[y] == 0) { // even vertex -> odd vertex // check d[y] == 0 instead of d[p[y]] == 1, so (m[y], y) is in the blossom augment(m[y], m[c1[y]]); augment(r, m[c2[y]]); m[c1[y]] = c2[y], m[c2[y]] = c1[y]; } else { int x{p[y]}; augment(r, m[x]); m[x] = y, m[y] = x; } } bool bfs(const vector<vector<int>>& adj, int r) { dsu_reset(); fill(d.begin(), d.end(), -1); qu = {}, qu.push(r), d[r] = 0; while (!qu.empty()) { int x{qu.front()}; qu.pop(); for (auto& y : adj[x]) { if (base(x) == base(y)) continue; if (d[y] == -1) { p[y] = x, d[y] = 1; if (m[y] == -1) { // augmenting path augment(-1, y); return true; } else { p[m[y]] = y, d[m[y]] = 0; qu.push(m[y]); } } else if (d[base(y)] == 0) { // blossom int b{lca(base(x), base(y))}; handle_one_side(x, y, b); handle_one_side(y, x, b); } } } return false; } public: vector<int> operator()(const vector<vector<int>>& adj) { label = 0, p.assign(adj.size(), -1), d.resize(adj.size()), a.resize(adj.size()), c1.resize(adj.size()), c2.resize(adj.size()), m.assign(adj.size(), -1); dsu_p.resize(adj.size()), dsu_sz.resize(adj.size()), dsu_b.resize(adj.size()); int c{0}; for (int v{0}; v < adj.size(); ++v) if (m[v] == -1 && bfs(adj, v)) ++c; return move(m); } }; ``` 因為透過並查集進行縮花，每次找到節點所在的集合，或是合併節點，複雜度為 $O(\alpha(|V|))$。 > 如果是在縮花後的圖上操作，因為 `base()`，複雜度就要乘上 $O(\alpha(|V|))$。 <hr class="thin"> 縮花時，找 LCA，分別讓 cross edge 的二個點每次各走一步，次數最多不超過花上的節點數，剩餘縮花的運算量也等於花上的節點數；每個節點最多被縮花一次，因此所有**縮花的總複雜度為 $O(|V|\alpha(|V|))$**。 <hr class="thin"> 擴增時，可擴增路徑長度為 $O(|V|)$，複雜度為 $O(|V|)$。 <hr class="thin"> 每次 BFS，不包含縮花與擴增，複雜度為 $O(|V|+|E|\alpha(|V|))$。 <hr class="thin"> 總共進行 $O(|V|)$ 次，**演算法複雜度為 $O(|V||E|\alpha(|V|))$**。 <hr class="dashed"> ### 另一種實現方式:bulb::bulb: 匹配邊本身就是雙向連通，偶點的前一個點就是對應的奇點，因此可以把鏈結（link）拿去紀錄花上的反向邊，透過匹配邊與鏈結，讓整個花不管順時針逆時針都可以正常經過。 > base 的部分沒辦法這樣做，因為有左右二條邊。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> C [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; E -> F [arrowhead=o]; F -> G [dir=none, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=back, arrowtail=o]; C -> G [style=dashed, arrowhead=o]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> 擴增時要拆花，就會變得很簡單，只要隨著鏈結走就可以了。 ```graphviz digraph { rankdir=LR; H [label="", color="#0000FF"]; H -> D [arrowhead=vee]; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; C [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } S0 -> A [dir=back, arrowtail=vee, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=vee]; B :e -> C [dir=back, arrowtail=vee, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [arrowhead=vee, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; E -> F [arrowhead=vee]; F -> G [arrowhead=vee, style=bold, color="#B000B0"]; C -> G [style=dashed, dir=back, arrowtail=vee]; C -> G [style=dashed, arrowhead=o]; A :e -> C [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` <hr class="thin"> base 沒辦法直接記錄鏈結，但會有從 base 往非匹配邊走的情況嗎？ > 其實有喔！花中有花的時候。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; subgraph cluster_blossom2 { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; a [shape=doublecircle, label="base", style=filled, fillcolor=lightgray, color="#FFA500"]; } } S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> a [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; F -> G [dir=none, style=bold, color="#B000B0"]; a -> G [style=dashed, dir=none]; A :e -> a [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; } ``` 情況一： > 因為直接從 base 連出去，所以不會進到花中。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; subgraph cluster_blossom2 { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; a [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; b [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; d [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; e [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } } a :se -> b [dir=back, arrowtail=o]; b :e -> c [dir=none, style=bold, color="#B000B0"]; a :e -> d [dir=back, arrowtail=o]; d :e -> e [dir=none, style=bold, color="#B000B0"]; c -> e [arrowhead=o, style=dashed]; c -> e [dir=back, arrowtail=o, style=dashed]; a :e -> c [style=invis]; a :e -> e [style=invis]; a :e -> d [style=invis]; S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> a [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; E -> F [arrowhead=o]; F -> G [dir=none, style=bold, color="#B000B0"]; a -> G [style=dashed, arrowhead=o]; a -> G [style=dashed, dir=back, arrowtail=o]; A :e -> a [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; H [label="", color="#0000FF"]; H -> B [arrowhead=o]; } ``` 情況二：當花再次被縮花時，就可以知道鏈結該往哪邊走。 > 取決於偶點到下個奇點的邊，或是偶點到偶點的 cross edge，到底是屬於花中的哪個點。 ```graphviz digraph { rankdir=LR; S0 [style=invis]; subgraph cluster_blossom { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; A [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; B [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; D [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; E [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; F [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; G [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; subgraph cluster_blossom2 { label="Blossom"; fontsize=20; labelloc=t; labeljust=l; a [label="base", style=filled, fillcolor=lightgray, color="#FF0000"]; b [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; c [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; d [label="", style=filled, fillcolor=lightgray, color="#FFA500"]; e [label="", style=filled, fillcolor=lightgray, color="#FF0000"]; } } a :e -> b [dir=back, arrowtail=o]; a :se -> b [arrowhead=o, style=bold, color="#FFD000"]; b :e -> c [dir=none, style=bold, color="#B000B0"]; a :ne -> d [dir=back, arrowtail=o]; d :e -> e [dir=none, style=bold, color="#B000B0"]; c -> e [arrowhead=o, style=dashed]; c -> e [dir=back, arrowtail=o, style=dashed]; a :e -> c [style=invis]; a :e -> e [style=invis]; a :e -> d [style=invis]; S0 -> A [dir=none, style=bold, color="#B000B0"]; A :se -> B [dir=back, arrowtail=o]; B :e -> a [dir=none, style=bold, color="#B000B0"]; A :ne -> D [dir=back, arrowtail=o]; D :e -> E [dir=none, style=bold, color="#B000B0"]; E -> F [dir=back, arrowtail=o]; E -> F [arrowhead=o]; F -> G [dir=none, style=bold, color="#B000B0"]; d -> G [style=dashed, arrowhead=o]; d -> G [style=dashed, dir=back, arrowtail=o]; A :e -> a [style=invis]; A :e -> E [style=invis]; A :e -> F [style=invis]; A :e -> G [style=invis]; H [label="", color="#0000FF"]; H -> B [arrowhead=o]; } ``` <hr class="thin"> 這樣的問題在於，每次縮花調整鏈結時，需要拆花，每次縮花複雜度就要 $O(|V|)$，最多縮花 $O(|V|)$ 次，縮花總複雜度變為 $O(|V|^2)$，因此演算法複雜度為 $O(|V|^3)$。 > 不過實作可能簡單一點。 <hr class="dashed"> 一般圖最大匹配，透過更複雜的 **Micali-Vazirani Algorithm**，可以達到 **$E\sqrt V$** 的複雜度。 --- # 最大權匹配（Maximum Weight Matching）如果現在每條邊都有一個權重 $w$，匹配 $M$ 的權重則為 **$w(M)=\sum_{e\in M}w_e$**，最大權匹配問題就是求一個權重最大的匹配。 <hr class="dashed"> ## 二分圖最大權匹配（Maximum Weight Bipartite Matching） ### Hungarian Algorithm（Kuhn–Munkres Algorithm）:bulb: 先考慮一個比較侷限的問題，在一個完全二分圖（complete bipartite graph）$K_{n,n}$ 上，求最大權完美匹配（Maximum weight perfect matching）。 > 完全二分圖：$X$ 中任意一點與 $Y$ 的所有點均有邊。 > $K_{n,n}$：$|X|=|Y|=n$ 的完全二分圖。 ```graphviz graph { rankdir=LR; subgraph cluster_X { style=dashed; label="X"; A [label="", fontcolor="#FF0000", style=filled]; B [label="", fontcolor="#FF0000", style=filled]; C [label="", fontcolor="#FF0000", style=filled]; } subgraph cluster_Y { style=dashed; label="Y"; a[label="", fontcolor="#0000FF", style=filled]; b[label="", fontcolor="#0000FF", style=filled]; c[label="", fontcolor="#0000FF", style=filled]; } A -- a [style=bold, color="#B000B0", label="8", fontcolor="#B000B0"]; A -- b; A -- c; B -- a; B -- b [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"]; B -- c; C -- a; C -- b; C -- c [style=bold, color="#B000B0", label="7", fontcolor="#B000B0"]; } ``` 先給每個節點一個重量標籤，如果重量標籤滿足 $lx_i+ly_j\ge w_{ij}\;\forall\; 1\le i,j\le n$，稱它為二分圖的一個潛能（potential） $P$，潛能的大小為 $w(P)=\sum_{i=1}^{n}lx_i+\sum_{j=1}^{n}ly_j$。 <hr class="thin"> :::danger （引理 2.）完全二分圖 $K_{n,n}$ 中，任意一個完美匹配 $M$ 與任意一個潛能 $P$，滿足 $w(M)\le w(P)$。等式成立若且唯若 $w_{ij}=lx_i+ly_j\;\forall\; (i,j)\in M$，而此時的 $M$ 為最大完美匹配，$P$ 為最小潛能。 ::: 所有 $M$ 中的邊 $(i,j)$，都有 $w_{ij}\le lx_i+ly_j$，而 $M$ 是完美匹配，所以每個點都恰好是一條匹配邊的端點，因此 $w(M)=\sum_{(i,j)\in M}w_{ij}\le\sum_{(i,j)\in M}lx_i+ly_j=P$；若等式成立，則所有用到的條件式都必須相等，才會得到 $w(M)=w(P)$。 <hr class="thin"> :::danger （定理 3.）一個完全二分圖 $K_{n,n}$ 中，最大完美匹配 $M$ 與最小潛能 $P$，滿足 $w(M)=w(P)$。 ::: 根據引理 2.，如果存在某個 $M$ 與 $P$，使得 $w(M)=w(P)$，則它們分別是最大完美匹配與最小潛能；因此需要證明，對任意完全二分圖 $K_{n,n}$，都存在 $M$ 與 $P$，使得 $w(M)=w(P)$。 > 這邊不討論過多的數學定理，透過演算法來證明其存在性。 <hr class="thin"> ```graphviz graph { rankdir=LR; A [label="5", fontcolor="#FF0000"]; B [label="2", fontcolor="#0000FF"]; A -- B [label="7"]; } ``` 一條邊如果滿足$w_{ij}=lx_i+ly_j$，稱為「等邊」（equaility edge）。因為要找全部是等邊的匹配，所以一開始就只找等邊匹配邊，而可擴增路徑上一定都要是等邊，藉此慢慢增加等邊匹配邊的數量。 <hr class="dotted"> #### 演算法 1. 依序以每個 $X$ 非匹配點為起點 2. 透過等邊尋找可擴增路徑 * 如果找到可擴增路徑，進行擴增 * 如果找不到可擴增路徑，並且無法前進時，進入步驟 $3$ 3. 調整重量標籤，以增加新的等邊，並回到步驟 $2$ 繼續尋找因為任何時候的匹配邊一定是等邊，當路徑無法前進時，一定是停在某個偶點（$X$ 的點）， ```graphviz graph { rankdir=LR; A [label="5", fontcolor="#FF0000"]; B [label="2", fontcolor="#0000FF"]; C [label="3", fontcolor="#FF0000"]; D [label="6", fontcolor="#0000FF"]; A -- B [label="7"]; B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"]; C -- D [style=dashed, label="8"]; } ``` <hr class="thin"> 將交錯樹上 $X$ 的點都減掉 $d$，$Y$ 點都加上 $d$；對於一條邊 $(i,j)\mid i\in X,j\in Y$，如果 $i,j$ 都在樹上，則 $lx_i+ly_j$ 不變，所以樹上還是都是等邊；如果 $i,j$ 都在樹外，$lx_i+ly_j$ 不變；如果 **$i$ 在樹外，$j$ 在樹上**，$lx_i+ly_j$ 變大，還是維持大於等於的性質，並且**這樣的邊不是匹配邊**，所以不影響目前的匹配邊都是等邊的事實；如果 **$i$ 在樹上，$j$ 在樹外**，$lx_i+ly_j$ 變為 $lx_i+ly_j-d$，有可能**變為等邊**， ```graphviz graph { rankdir=LR; A [label="5-d", fontcolor="#FF0000"]; B [label="2+d", fontcolor="#0000FF"]; C [label="3-d", fontcolor="#FF0000"]; D [label="6", fontcolor="#0000FF"]; E [label="8", fontcolor="#0000FF"]; F [label="4", fontcolor="#0000FF"]; A -- B [label="7"]; B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"]; C -- D [style=dashed, label="8"]; C -- E [style=dashed, label="9"]; A -- F [style=dashed, label="3"]; } ``` <hr class="thin"> 為了讓重量標籤還是一個潛能（維持大於等於的性質），令 $d$ 為所有 $i$ 在樹上，$j$ 在樹外的邊中，$lx_i+ly_j-w_{ij}$ 的最小值，而每次調整重量標籤可以增加一條（以上）的等邊。 > **$d=\min_{i\in tree,j\notin tree}(lx_i+ly_j-w_{ij})$** ```graphviz graph { rankdir=LR; A [label="4", fontcolor="#FF0000"]; B [label="3", fontcolor="#0000FF"]; C [label="2", fontcolor="#FF0000"]; D [label="6", fontcolor="#0000FF"]; E [label="8", fontcolor="#0000FF"]; F [label="4", fontcolor="#0000FF"]; A -- B [label="7"]; B -- C [style=bold, color="#B000B0", label="5", fontcolor="#B000B0"]; C -- D [style=dashed, label="8"]; C -- E [style=dashed, label="9"]; A -- F [style=dashed, label="3"]; } ``` <hr class="thin"> 每次重新調整重量標籤，至少會有一條新的等邊，因此在有限步內，一樣會搜尋完所有路徑。 > 雖然加了只能透過等邊搜尋的條件，不代表可擴增路徑會消失， > 只是要等到重量標籤被調整後，才會慢慢形成等邊的可擴增路徑。因為是完全二分圖，最終一定會得到一個**由等邊構成的完美匹配**。 <hr class="dotted"> 每次重新調整完重量標籤後，都直接重新搜尋，得到一個複雜度較差的實作。 ```cpp! class WeightedBipartiteMatching { int n; vector<long long> lx, ly; vector<bool> vx, vy; vector<int> mx, my; bool dfs(const vector<vector<long long>>& w, int x) { vx[x] = true; for (int y{0}; y < n; ++y) if (!vy[y] && lx[x] + ly[y] == w[x][y]) { vy[y] = true; if (my[y] == -1 || dfs(w, my[y])) { mx[x] = y, my[y] = x; return true; } } return false; } void relabel(const vector<vector<long long>>& w) { long long d{numeric_limits<long long>::max()}; for (int x{0}; x < n; ++x) if (vx[x]) { for (int y{0}; y < n; ++y) if (!vy[y]) d = min(d, lx[x] + ly[y] - w[x][y]); } for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d; for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d; } public: pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) { n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), mx.assign(n, -1), my.assign(n, -1); for (int i{0}; i < n; ++i) for (int j{0}; j < n; ++j) lx[i] = max(lx[i], w[i][j]); for (int x{0}; x < n; ++x) { while (true) { fill(vx.begin(), vx.end(), false); fill(vy.begin(), vy.end(), false); if (dfs(w, x)) break; // augmenting path with equaility edge relabel(w); } } return {move(mx), move(my)}; } }; ``` 總共有 $V$ 個點，每個點最多重新標記 $O(|V|)$ 次後找到可擴增路徑， DFS 複雜度為 $O(|E|)=O(|V|^2)$，重新標記複雜度為 $O(|V|^2)$， **演算法複雜度為 $O(|V|^4)$**。 <hr class="dotted"> 一開始每個 $i$ 與 $j$ 都在樹外，因為要計算的是，「$i$ 在樹上，$j$ 在樹外的邊中，$lx_i+ly_j-w_{ij}$」的最小值，每次拜訪到 $i$，所有在樹外的 $j$ 都符合條件；而每次拜訪到 $j$ 時，所有 $j$ 的邊都不再在條件範圍中；因此我們可以**分別對每個 $j$，紀錄其最小值，還有到底是與哪個 $i$ 的邊達到最小值的**。 > 每次拜訪 $i$ 時，就要更新所有 $j$ 紀錄的值； > 每當 $j$ 被拜訪時，就不再考慮這個 $j$ 的邊。 ```cpp! // Hungarian Algorithm - O(V^3) class WeightedBipartiteMatching { int n; vector<long long> lx{}, ly{}; vector<bool> vx{}, vy{}; queue<int> qu{}; // only X's vertices vector<int> py{}; vector<long long> dy{}; // smallest (lx[x] + ly[y] - w[x][y]) vector<int> pdy{}; // & which x vector<int> mx{}, my{}; void relax(const vector<vector<long long>>& w, int x) { for (int y{0}; y < n; ++y) if (lx[x] + ly[y] - w[x][y] < dy[y]) dy[y] = lx[x] + ly[y] - w[x][y], pdy[y] = x; } void augment(int y) { while (y != -1) { int x{py[y]}, yy{mx[x]}; mx[x] = y, my[y] = x; y = yy; } } bool bfs(const vector<vector<long long>>& w) { while (!qu.empty()) { int x{qu.front()}; qu.pop(); for (int y{0}; y < n; ++y) { if (!vy[y] && lx[x] + ly[y] == w[x][y]) { vy[y] = true, py[y] = x; if (my[y] == -1) return augment(y), true; int xx{my[y]}; qu.push(x), vx[xx] = true, relax(w, xx); } } } return false; } void relabel() { long long d{numeric_limits<long long>::max()}; for (int y{0}; y < n; ++y) if (!vy[y]) d = min(d, dy[y]); for (int x{0}; x < n; ++x) if (vx[x]) lx[x] -= d; for (int y{0}; y < n; ++y) if (vy[y]) ly[y] += d; for (int y{0}; y < n; ++y) if (!vy[y]) dy[y] -= d; } bool expand(const vector<vector<long long>>& w) { // expand one layer with new equality edges for (int y{0}; y < n; ++y) { if (!vy[y] && dy[y] == 0) { vy[y] = true, py[y] = pdy[y]; if (my[y] == -1) return augment(y), true; int xx{my[y]}; qu.push(xx), vx[xx] = true, relax(w, xx); } } return false; } public: pair<vector<int>, vector<int>> operator()(const vector<vector<long long>>& w) { n = w.size(), lx.assign(n, 0), ly.assign(n, 0), vx.resize(n), vy.resize(n), py.resize(n), dy.resize(n), pdy.resize(n), mx.assign(n, -1), my.assign(n, -1); for (int i{0}; i < n; ++i) for (int j{0}; j < n; ++j) lx[i] = max(lx[i], w[i][j]); for (int x{0}; x < n; ++x) { fill(vx.begin(), vx.end(), false); fill(vy.begin(), vy.end(), false); fill(dy.begin(), dy.end(), numeric_limits<long long>::max()); qu = {}, qu.push(x), vx[x] = true, relax(w, x); while (!bfs(w)) { relabel(); if (expand(w)) break; } } return {move(mx), move(my)}; } }; ``` <hr class="dotted"> #### 二分圖最大權匹配（Maximum Weight Bipartite Matching）將 $X$ 與 $Y$ 的點數量增加到一樣，不用新增邊，接著將所有**不存在以及負權重的邊，設定為 $0$**，就可以將問題轉化為完全二分圖 $K_{n,n}$ 的最大權完美匹配了。 > 權重設定為 $0$ 的意義是代表可以不匹配。 <hr class="dotted"> #### 二分圖最大權最大匹配（Maximum Weight Maximum Cardinality Bipartite Matching）二分圖最大權最大匹配，是在最大匹配數量下，權重最大的匹配。將所有**不存在的邊設為 $0$**，並將每條**原有的邊加上一個夠大的數字**，就一樣可以將問題轉化，因為當每條邊都被加上一個很大的數字後，除了達到最大數量的匹配以外，其他匹配的權重都會小得多。 > 令邊的權重絕對值最大值為 $W$，$2nW+1$ 就是一個足夠大的值， > > 任意匹配 $M'$，$-nW\le w(M')\le nW$，因此二個匹配權重差距至多 $2nW$。 > > 因為只要某個匹配少了一條匹配邊，其他匹配邊原有權重再怎麼取， > 還是會比達到最大匹配數量的匹配小。 <hr class="dotted"> #### 二分圖最小權最大匹配（Minimum Weight Maximum Cardinality Bipartite Matching）要求最小權的話，為了套用最大權的匈牙利演算法，可以將權重進行變號，這樣最小權就會變為最大權了。至於最大匹配的部分，另一種方式是將不存在的邊設為一個極大的負數，這樣就會盡量取到最大匹配，也就是減少取不存在的邊作為匹配邊。 > 亦或是可以思考為，為了求最小權最大匹配，我們應該是先將不存在的邊設為一個極大的正數， > 但是為了套用最大權的匈牙利演算法，這些極大的正數也要跟著進行變號。 <hr class="dotted"> 匈牙利演算法，透過對完全二分圖求解，確保二分圖一定有著完美匹配； **相關問題，可利用上述一些技巧，進行問題轉化，得到答案後再行調整**。 <hr class="dashed"> ## 一般圖最大權匹配（Maximum Weight Matching）:bulb::bulb: Edmonds' Blossom Algorithm 搭配 Hungarain Algorithm 的概念，就可以解一般圖最大權匹配，不過因為花的出現，重量標籤處理上會更為複雜。 --- # References * 張鎮華、蔡牧村（2020）。演算法觀點的圖論（修訂版）。 * 演算法筆記 - [Matching](http://web.ntnu.edu.tw/~algo/Matching.html) * Wikipedia - [Hopcroft–Karp algorithm](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm) * Wikipedia - [Blossom algorithm](https://en.wikipedia.org/wiki/Blossom_algorithm) * BRILLIANT - [Blossom Algorithm](https://brilliant.org/wiki/blossom-algorithm/) * Wikipedia - [Hungarian algorithm](https://en.wikipedia.org/wiki/Hungarian_algorithm) --- # 練習題 | Problem | Tags | |:-:|:- | | []() | | <style> hr.thin { height: 0.5px; } hr.dotted { border-top: dotted; height: .0em; color: #777777; background-color: #ffffff; } hr.dashed { border-top: dashed; height: .0em; color: #777777; background-color: #ffffff; } /* Gradient transparent - color - transparent */ hr.gradient { border: 0; height: 1px; background-image: linear-gradient(to right, rgba(0, 0, 0, 0), rgba(0, 0, 0, 0.75), rgba(0, 0, 0, 0)); } /* Flaired edges, by Tomas Theunissen */ hr.flaired { overflow: visible; height: 30px; border-style: solid; border-color: black; border-width: 1px 0 0 0; border-radius: 20px; background-color: #ffffff; } hr.flaired:before { /* Not really supposed to work, but does */ display: block; content: ""; height: 30px; margin-top: -31px; border-style: solid; border-color: black; border-width: 0 0 1px 0; border-radius: 20px; } </style>

Read more

C++S's CODEBOOK

2021 Week12 - Graph (BCC, SCC, LCA)

2021 Week17 - Cover & Independent set

2021 Week8 - Range Query