圖論 - 匹配

---

---

匹配圖是圖的一個子圖，其中沒有邊彼此相鄰。簡單來說，任意兩條邊之間不應該有任何公共頂點。

匹配

設‘G’ = (V, E) 為一個圖。如果G的每個頂點最多與M中的一條邊關聯，則子圖稱為匹配M(G)，即：

deg(V) ≤ 1 ∀ V ∈ G

這意味著在匹配圖M(G)中，頂點的度數應為1或0，其中邊應來自圖G。

符號 − M(G)

示例

在匹配中：

如果deg(V) = 1，則(V)被稱為匹配的

如果deg(V) = 0，則(V)未匹配。

在匹配中，任意兩條邊不相鄰。這是因為如果任意兩條邊相鄰，則連線這兩條邊的頂點的度數將為2，這違反了匹配規則。

最大匹配

如果不能將圖‘G’的任何其他邊新增到M中，則稱圖‘G’的匹配M為最大匹配。

示例

上圖中的M1、M2、M3是G的最大匹配。

最大匹配

也稱為最大最大匹配。最大匹配定義為具有最大邊數的最大匹配。

‘G’的最大匹配中的邊數稱為其匹配數。

示例

對於上面示例中給出的圖，M1和M2是‘G’的最大匹配，其匹配數為2。因此，使用圖G，我們最多隻能形成只有2條邊的子圖。因此，匹配數為二。

完美匹配

如果圖g (G)的每個頂點都恰好與匹配(M)的一條邊關聯，則稱圖(G)的匹配(M)為完美匹配，即：

deg(V) = 1 ∀ V

子圖中每個頂點的度數都應為1。

示例

在下圖中，M1和M2是G的完美匹配的例子。

注意 − 圖的每個完美匹配也是圖的最大匹配，因為在完美匹配圖中沒有機會再新增一條邊。

圖的最大匹配不一定是完美的。如果圖‘G’有一個完美匹配，則頂點數|V(G)|為偶數。如果是奇數，則最後一個頂點與另一個頂點配對，最終剩下一個單一頂點，它不能與任何其他頂點配對，其度數為零。這顯然違反了完美匹配原則。

示例

注意 − 上述陳述的逆命題不一定為真。如果G的頂點數為偶數，則M1不必是完美的。

示例

它是匹配，但即使它有偶數個頂點，它也不是完美匹配。