匹配 (圖論)

在圖論中，一個圖是一個匹配（或稱獨立邊集）是指這個圖之中，任意兩條邊都沒有公共的頂點。這時每個頂點都至多連出一條邊，而每一條邊都將一對頂點相匹配。

嚴格定義

對於一個給定的圖G=(V,E)，這幅圖的一個匹配M是圖G的一個子圖（由原來的圖的一部分頂點和一部分邊構成的圖），其中每兩條邊都不相鄰（沒有公共頂點）。在匹配圖中，一個頂點連出的邊數至多是一條。如果這個頂點連出一條邊，就稱這個頂點是已匹配的。

圖G的一個極大匹配是指這樣一個匹配，它不可能是圖G的任何一個匹配的真子圖。換句話說，如果M是圖G的一個極大匹配，那麼不可能有另一個匹配包含M的全部邊，而不等於M。如果一個子圖包含了M，並且還有其它的邊，那麼必然不是匹配，也就是說一定有兩條邊有公共頂點。如果M是圖G的一個極大匹配，那麼G的每一條邊都和M中的一條邊相鄰（否則可以加上這條邊）。以下的三幅圖是極大匹配的例子。

圖G的一個最大匹配是另一個概念，指邊數最多的匹配。最大匹配可能有不止一個，但最大匹配的邊數是確定的，並且不可能超過圖中頂點數的一半。這是因為一個匹配中的一條邊對應一對（兩個）頂點，而不同邊所對應的兩對頂點是完全不同的，否則它們就是相鄰的兩條邊了。最大匹配中的頂點數稱為圖的「配對數」，一般記作$\nu (G)$。最大匹配顯然都是極大匹配，但極大匹配不一定是最大匹配。以下三幅圖是最大匹配的例子。可以看出，在左起第一幅圖中，最大匹配的頂點數是4，但在上面的極大匹配的例子中，存在着只有1條邊的極大匹配。左起第二幅圖中也是一樣，最大匹配的頂點數是6，但在上面的極大匹配的例子中，存在着只有2條邊的極大匹配。左起第三幅圖則是一個「最大匹配必然是極大匹配」的例子。

圖G的一個完美匹配（Perfect Match）是一個包括了圖G中原來的所有頂點的匹配，是最大匹配的一種。一般來說，最大匹配不一定使用了原圖的所有頂點，因此配對數小於等於原圖的頂點數目，比如說上面左起第一和第三幅圖。而第二幅圖則是一個完美匹配的例子。完美匹配有時也叫做全局匹配或完全匹配。完美匹配同時也是一個原圖的最小邊數的邊覆蓋（即是用最少的邊包括所有頂點的子圖）。

一個準完美匹配則是當完美匹配不存在時的一個近似。準完美匹配中，原圖只有一個頂點沒有被使用，也就是說只差一個頂點達到完美匹配，這是因為原圖的頂點數是奇數，完美匹配不可能存在。準完美匹配必然是最大匹配。

對一個給定的匹配M，定義：

• 一條交替路徑（Alternating Path）是指這樣一條路徑，其中的每一條邊交替地屬於或不屬於匹配M。比如說，第一、三、五條邊屬於M，而第二、四、六條不屬於M，等等。
• 一條增廣路徑（Augmenting Path）是指從M中沒有用到的頂點開始，並從M中沒有用到的頂點結束的交替路徑。

可以證明，一個匹配是最大匹配，若且唯若它沒有任何增廣路徑（這個結論有時被稱為貝爾熱引理）。

性質

任意圖中，極大匹配的邊數不少於最大匹配的邊數的一半。

如果A和B是兩個極大匹配，那麼|A| ≤ 2|B| 且 |B| ≤ 2|A|。因為，在B \ A里的每條邊最多與A \ B中的兩條邊相連。而且，根據極大性，在A \ B中的邊一定與一條B \ A中的邊相連。所以$|A\setminus B|\leq 2|B\setminus A|.$

因此我們可以得到:$|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.$

特別地，這個結論告訴我們任何一個極大匹配都是最大匹配的2近似，也是最小的極大匹配的2近似。這個不等式是嚴格的。比如一個圖G是一個4個點3條邊的鏈，那麼最小的極大匹配是1，最大匹配是2。

此外，霍爾婚配定理刻劃了二部圖中，何時能將一側全部頂點匹配到另一側。

匹配多項式

匹配多項式是一個圖的k條邊匹配的數量的生成函數。假定G是一個圖，m_k是k條邊匹配的數量。那麼G的匹配多項式是

$\sum _{k\geq 0}m_{k}x^{k}.$

另一個匹配多項式的定義是

$\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},$

其中n是圖中點的個數。每一種定義都有其作用，詳情可以看匹配多項式的文章。

參考來源

• 盧開澄,盧華明. 图论及其应用. 清華大學出版社. 1995. ISBN 978-7-302-01817-9.