匹配 (圖論)
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在圖論中,一個圖是一個匹配(或稱獨立邊集)是指這個圖之中,任意兩條邊都沒有公共的頂點。這時每個頂點都至多連出一條邊,而每一條邊都將一對頂點相匹配。
嚴格定義
[編輯]對於一個給定的圖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.
|