匹配 (圖論)
在圖論中，一個圖是一個匹配（或稱獨立邊集）是指這個圖之中，任意兩條邊都沒有公共的頂點。這時每個頂點都至多連出一條邊，而每一條邊都將一對頂點相匹配。
嚴格定義 編輯
對於一個給定的圖G=(V,E)，這幅圖的一個匹配M是圖G的一個子圖（由原來的圖的一部分頂點和一部分邊構成的圖），其中每兩條邊都不相鄰（沒有公共頂點）。在匹配圖中，一個頂點連出的邊數至多是一條。如果這個頂點連出一條邊，就稱這個頂點是已匹配的。
圖G的一個極大匹配是指這樣一個匹配，它不可能是圖G的任何一個匹配的真子圖。換句話說，如果M是圖G的一個極大匹配，那麼不可能有另一個匹配包含M的全部邊，而不等於M。如果一個子圖包含了M，並且還有其它的邊，那麼必然不是匹配，也就是說一定有兩條邊有公共頂點。如果M是圖G的一個極大匹配，那麼G的每一條邊都和M中的一條邊相鄰（否則可以加上這條邊）。以下的三幅圖是極大匹配的例子。
圖G的一個最大匹配是另一個概念，指邊數最多的匹配。最大匹配可能有不止一個，但最大匹配的邊數是確定的，並且不可能超過圖中頂點數的一半。這是因為一個匹配中的一條邊對應一對（兩個）頂點，而不同邊所對應的兩對頂點是完全不同的，否則它們就是相鄰的兩條邊了。最大匹配中的頂點數稱為圖的「配對數」，一般記作 。最大匹配顯然都是極大匹配，但極大匹配不一定是最大匹配。以下三幅圖是最大匹配的例子。可以看出，在左起第一幅圖中，最大匹配的頂點數是4，但在上面的極大匹配的例子中，存在着只有1條邊的極大匹配。左起第二幅圖中也是一樣，最大匹配的頂點數是6，但在上面的極大匹配的例子中，存在着只有2條邊的極大匹配。左起第三幅圖則是一個「最大匹配必然是極大匹配」的例子。
圖G的一個完美匹配（Perfect Match）是一個包括了圖G中原來的所有頂點的匹配，是最大匹配的一種。一般來說，最大匹配不一定使用了原圖的所有頂點，因此配對數小於等於原圖的頂點數目，比如說上面左起第一和第三幅圖。而第二幅圖則是一個完美匹配的例子。完美匹配有時也叫做全局匹配或完全匹配。完美匹配同時也是一個原圖的最小邊數的邊覆蓋（即是用最少的邊包括所有頂點的子圖）。
一個准完美匹配則是當完美匹配不存在時的一個近似。准完美匹配中，原圖只有一個頂點沒有被使用，也就是說只差一個頂點達到完美匹配，這是因為原圖的頂點數是奇數，完美匹配不可能存在。准完美匹配必然是最大匹配。
對一個給定的匹配M，定義：
- 一條交替路徑（Alternating Path）是指這樣一條路徑，其中的每一條邊交替地屬於或不屬於匹配M。比如說，第一、三、五條邊屬於M，而第二、四、六條不屬於M，等等。
- 一條增廣路徑（Augmenting Path）是指從M中沒有用到的頂點開始，並從M中沒有用到的頂點結束的交替路徑。
可以證明，一個匹配是最大匹配，當且僅當它沒有任何增廣路徑（這個結論有時被稱為貝吉引理）。
性質 編輯
任意圖中，極大匹配的邊數不少於最大匹配的邊數的一半[1]。
如果A和B是兩個極大匹配，那麼|A| ≤ 2|B| 且 |B| ≤ 2|A|。因為，在B \ A里的每條邊最多與A \ B中的兩條邊相連。而且，根據極大性，在A \ B中的邊一定與一條B \ A中的邊相連。所以
因此我們可以得到:
特別地，這個結論告訴我們任何一個極大匹配都是最大匹配的2近似，也是最小的極大匹配的2近似。這個不等式是嚴格的。比如一個圖G是一個4個點3條邊的鏈，那麼最小的極大匹配是1，最大匹配是2。
匹配多項式 編輯
匹配多項式是一個圖的k條邊匹配的數量的生成函數。假定G是一個圖，mk是k條邊匹配的數量。那麼G的匹配多項式是
另一個匹配多項式的定義是
其中n是圖中點的個數。每一種定義都有其作用，詳情可以看匹配多項式的文章。
參考來源 編輯
- ^ Doratha E. Drake, Stefan Hougardy. A Simple Approximation Algorithm for the Weighted Matching Problem. Information Processing Letters.
- 盧開澄,盧華明. 图论及其应用. 清華大學出版社. 1995. ISBN 978-7-302-01817-9.