跳转至

圖匹配

匹配 或是 獨立邊集 是一張圖中不具有公共端點的邊的集合。 在二分圖中求匹配等價於網路流問題。

圖匹配算法是信息學競賽中常用的算法，總體分為最大匹配以及最大權匹配，先從二分圖開始介紹，再進一步提出一般圖的作法。

圖的匹配

在圖論中，假設圖 \(G=(V,E)\)，其中 \(V\) 是點集，\(E\) 是邊集。

一組兩兩沒有公共點的邊集 \(M(M\in E)\) 稱為這張圖的 匹配。

定義匹配的大小為其中邊的數量 \(|M|\)，其中邊數最大的 \(M\) 為 最大匹配。

當圖中的邊帶權的時候，邊權和最大的為 最大權匹配。

匹配中的邊稱為 匹配邊，反之稱為 未匹配邊。

一個點如果屬於 \(M\) 且為至多一條邊的端點，稱為 匹配點，反之稱為 未匹配點。

  • 極大匹配（maximal matching）：無法再增加匹配邊的匹配。不一定是最大匹配。
  • 最大匹配（maximum matching or maximum cardinality matching）：匹配邊數量最多的匹配。最大匹配可能有不止一個，但最大匹配的邊數是確定的，而且不可能超過圖中定點數的一半。
  • 最大權匹配（maximum weight matching）：加權圖中，權值和最大的匹配。
  • 最大權最大匹配（maximum weight maximum cardinality matching）：匹配數最多的前提下，邊權和最大的匹配。即所有最大匹配中，邊權和最大的匹配。
  • 完美匹配（perfect matching）：所有點都屬於匹配，同時也符合最大匹配。若圖 G 為完全圖且頂點數為偶數時，必然存在完美匹配。

  • 近完美匹配（near-perfect matching）：發生在圖的點數為奇數，剛好只有一個點不在匹配中，扣掉此點以後的圖稱為 factor-critical graph。

    極大匹配

    maximal matching

    最大匹配

    maximum cardinality matching

    最大權匹配

    maximum weight matching

    最大權最大匹配

    maximum weight maximum cardinality matching

二分圖匹配

bi-graph

一張二分圖上的匹配稱作二分匹配

設 \(G\) 為二分圖，若在 \(G\) 的子圖 \(M\) 中，任意兩條邊都沒有公共節點，那麼稱 \(M\) 為二分圖 \(G\) 的一個匹配，且 \(M\) 的邊數為匹配數。

完美匹配

設 \(G=\langle V_1, V_2, E \rangle\) 為二分圖，\(|V_1| \leq |V_2|\)，\(M\) 為 \(G\) 中一個最大匹配，且 \(|M|=|V_1|\)，則稱 \(M\) 為 \(V_1\) 到 \(V_2\) 的完美匹配。

霍爾定理

設二分圖 \(G=\langle V_1, V_2, E \rangle, |V_1| \leq |V_2|\)，則 \(G\) 中存在 \(V_1\) 到 \(V_2\) 的完美匹配當且僅當對於任意的 \(S \subset V_1\)，均有 \(|S|\leq|N(S)|\)，其中 \(N(S)=\Cup_{v_i \in S}{N(V_i)}\)，是 \(S\) 的鄰域。

最大匹配

尋找二分圖邊數最大的匹配稱為最大匹配問題。

算法

組合優化中的一個基本問題是求 最大匹配（maximum matching）。

二分圖最大匹配

詳見 二分圖最大匹配 頁面。

在無權二分圖中，Hopcroft–Karp 算法可在 \(O(\sqrt{V}E)\) 解決。

二分圖最大權匹配

詳見 二分圖最大權匹配 頁面。

在帶權二分圖中，可用 Hungarian 算法解決。 如果在最短路搜尋中用 Bellman–Ford 算法，時間複雜度為 \(O(V^2E)\)， 如果用 Dijkstra 算法或 Fibonacci heap，可用 \(O(V^{2}\log {V}+VE)\) 解決。

一般圖最大匹配

詳見 一般圖最大匹配 頁面。

無權一般圖中，Edmonds' blossom 算法可在 \(O(V^2E)\) 解決。

一般圖最大權匹配

詳見 一般圖最大權匹配 頁面。

帶權一般圖中，Edmonds' blossom 算法可在 \(O(V^2E)\) 解決。

匹配算法的轉換

用最大權最大匹配求最大權匹配

最大權最大匹配 允許負邊權 \((w(e)<0)\)，但是 最大權匹配 不會有負邊權。

若一張圖 \(G\) 其所有的邊皆為負權，則其 最大權匹配 \(M=\emptyset\)。

調整邊的權重

先將圖 \(G\) 的所有負權邊其權重 \(w(e)\) 設為 \(0\)，再進行接下來的步驟。

完全圖性質

當圖 \(G\) 為完全圖且沒有負邊權時，最大權最大匹配=最大權匹配。

所以把圖 \(G\) 鋪成完全圖，鋪上的邊其權重為 \(0\)，計算 最大權最大匹配 後再把權重為 0 的邊去除即可。如下圖所示。

graph-match

用最大權匹配求最大權最大匹配

最大權匹配 不會有負邊權，且零邊 \((w(e)=0)\) 可選可不選，但是 最大權最大匹配 允許負邊權和零邊。

調整邊的權重

令 \(K=\max\{|w(e)|:e\in E, w(e)\leq0\}+1\)，若沒有負邊權和零邊則 \(K=0\)。把圖 G 中所有的邊其權重 \(w(e)\) 加上 \(K\) 產生一張新圖 \(G^{\prime}=(V,E^{\prime})\)。得到的新圖 \(G\) 不存在負邊權和零邊。

最大權最大匹配 不一定等於 最大權匹配，但如果把所有邊的邊權加上一個足夠大的數 \(P\)，最大權匹配 的結果就是 最大權最大匹配。這樣的 \(P\) 應該取多大？ 令 \(P=\sum w(e):e\in E^{\prime}\)，把圖 G 中所有的邊其權重 \(w(e)\) 加上 \(P\)，產生一張新圖 \(G^{\prime\prime}=(V,E^{\prime\prime})\)。

此時對圖 G 進行 最大權匹配，其結果可以對應原圖 \(G\) 的 最大權最大匹配。如下圖所示。

graph-match

參考資料

  1. Wikiwand - Matching (graph theory)
  2. Wikiwand - Blossom algorithm
  3. 2015 年《淺談圖的匹配算法及其應用》- 陳胤伯
  4. 演算法筆記 - Matching
  5. the-tourist/algo
  6. Bill Yang's Blog - 帶花樹學習筆記
  7. 二分圖的最大匹配、完美匹配和匈牙利算法
  8. Wikiwand - Hopcroft–Karp algorithm
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：accelsao, StudyingFather, t4rf9, wlbksy, yuhuoji
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用