增廣路

增廣路定理 Berge's lemma

這是最大匹配的一個重要理論。

定義

• 交錯路（alternating path）始於非匹配點且由匹配邊與非匹配邊交錯而成。
• 增廣路（augmenting path）是始於非匹配點且終於非匹配點（除了起始的點）的交錯路。增廣路中邊的數量是奇數。

增廣路上非匹配邊比匹配邊數量多 1，如果將增廣路上的匹配邊和未匹配邊反轉，則匹配數量會增加 1 且依然是交錯路。

如上圖，匹配數從 2 增加為 3，匈牙利算法中只通過這樣的方式增加匹配數量，稱為 增廣（Augment）。

根據 Berge's lemma 當找不到增廣路的時候，得到最大匹配。

過程

由此定理可知我們求最大匹配的核心思路。

核心思路

枚舉所有未匹配點，找增廣路徑，直到找不到增廣路徑。

證明

事實上，對於每個點只要枚舉一次就好，證明如下：

假設某一輪沿着增廣路 \(a - b\) 增廣後，新增了以未匹配點 \(x\) 為起點的增廣路 \(P_x\)，則 \(P_x\) 必與 \(a - b\) 有公共邊（否則 \(P_x\) 不可能是因此次增廣而新增的）。 在 \(P_x\) 與 \(a - b\) 取得公共邊時，由於 \(a - b\) 是交錯路，意味着相交點在 \(a - b\) 內的兩鄰邊是不同類型的（圖中以紅和藍表示）；因而增廣前 \(x\) 就能走到 \(a - b\) 中的某個未匹配點，説明此前已存在從 \(x\) 出發的增廣路，即已枚舉過的未匹配點不再可能作為增廣路起點。

交錯樹

從未匹配點 \(r\) 進行 DFS 或 BFS 尋找增廣路的過程中產生的樹稱為交錯樹，\(r\) 是交錯樹的根。設 \(T=(V_t,E_t)\) 為再尋找增廣路時產生的交錯樹。定義：

• 偶點（黑點）為樹上深度為偶數的點。
• 奇點（白點）為樹上深度為奇數的點。

下圖展示了一個二分圖和從未匹配點 \(1\) 開始尋找增廣路時，形成的以 \(1\) 為根的交錯樹。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：accelsao, Chrogeek, t4rf9, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用