動機
在二部圖中,Hall 條件把選定的頂點集與其在另一側的鄰點集作比較。一般圖沒有固定的兩側,奇圈令這種語言不再適用。一個奇分支不可能完全在其內部完成匹配。若要使其中不留下未匹配的頂點,它必須經由一條邊與被刪除的邊界集相連。
這一觀察給出完美匹配的一個必要條件。其充分性則遠不那麼直接:也許多個不同的奇分支障礙會互相影響。我們利用一個邊極大的、沒有完美匹配的圖來證明不存在其他障礙。兩條假想的額外邊與一個交錯圈論證迫使其餘的分支具有非常剛性的形式。
本節在前面的二部圖定理之外發展一般圖的匹配理論。該證明是存在性論證;完整的多項式時間花朵(blossom)搜尋算法與非二部圖的加權匹配不在本節範圍之內。
定義
定義 6.2.1
(完美匹配與奇分支障礙)
設 為有限簡單無向圖。匹配是沒有公共端點的邊的集合。若每個頂點都屬於所選的某一條邊,則稱該匹配為完美匹配。空圖具有空的完美匹配。以 表示最大匹配的大小,以 表示刪除頂點集 後奇階連通分支的個數。
虧量表達式為 ,並定義
該最大值取自有限多個集合。由於空集給出非負值,所以它是非負的。所有候選值與 具有相同的奇偶性。
全鄰頂點是與其他每個頂點都相鄰的頂點。若一個圖沒有完美匹配,但加入任何一條缺失的邊都會產生完美匹配,則稱它是沒有完美匹配的飽和圖。任何沒有完美匹配的圖,只要在不產生完美匹配的前提下不斷加入邊,就能得到這樣的圖;有限性保證這一存在性構造會終止。
定理/命題
定理 6.2.2
(完美匹配的奇分支判別準則)
有限圖具有完美匹配,當且僅當
該條件包括空集與全體原有頂點。特別地,它會強制要求階數為偶數,而不是默默地假設階數為偶數。
定理 6.2.3
(匹配虧量的精確公式)
對每個 階有限圖,
因此,奇分支個數超出被刪頂點個數的最大值,恰好等於未匹配頂點個數的最小值,而不僅僅是一個下界。奇數階圖存在恰好漏掉一個頂點的匹配,當且僅當對每個 都有 。
定理 6.2.4
(飽和障礙的結構)
在沒有完美匹配的飽和圖中,設 為全鄰頂點的集合。則 的每個連通分支都是完全圖。如果這樣的圖同時滿足奇分支條件,那麼它的全鄰頂點可以與奇分支配對,並且其餘全鄰頂點可以彼此配對,從而產生矛盾。
證明思路或證明
證明
(必要性、下界與奇偶性)
先證必要性。取任意一個完美匹配與任意被刪除集合 。在 的每個奇分支中,並非所有頂點都能彼此匹配。至少有一條匹配邊必須離開該分支。由於不同分支之間沒有邊,這條邊的另一個端點屬於 。不同的奇分支使用 中不同的頂點,因為匹配不會重複使用端點。因此奇分支的個數至多為 。
更一般地,在任何匹配中,至多有 個奇分支能向 發出一條所選的邊。其餘每個奇分支至少留下一個未匹配的頂點。所以每個匹配至少留下 個未匹配頂點。取最大值即得下界 。
奇偶性的結論成立,是因為各分支的階數之和為 ,它模 2 等於奇分支的個數。因此對每個 , 與 具有相同的奇偶性。
交錯圈結構引理
證明
(飽和圖:全鄰頂點與團)
設一個飽和圖中有頂點 ,邊 存在,但邊 不存在。我們斷言 必為全鄰頂點。若不然,選取一個與 不相鄰的頂點 。由於 與 相鄰,這四個頂點互不相同。
加入 會產生完美匹配 ,並且它必須使用所加入的邊。加入 會產生完美匹配 ,它同樣必須使用所加入的邊。把它們的並看作多重圖,對共有的邊保留兩個帶標記的副本。每個頂點各有來自兩個匹配的一條邊,所以這個並分解為偶圈,圈上的邊在兩個匹配之間交替出現。重複的公共邊是一個兩條邊的圈。
如果這兩條加入的邊位於不同的交錯圈中,則在含有 的圈上由 切換到 。這樣去掉了 ,而沒有引入 。 中不變的邊與切換後的邊都在原圖中,由此得到一個被禁止的完美匹配。
因此兩條加入的邊位於同一個交錯圈中。去掉這兩條邊。由於它們分屬相反的匹配,圈分裂為兩條路徑,每條路徑都有奇數個頂點。每條路徑的一個端點來自 ,另一個端點來自 。特別地, 是其中一條路徑的端點,而 中恰有一個是另一條路徑的端點。
視情況用原有的邊 或 連接這兩個端點。從這兩條路徑中各刪去被連接的端點後,每條路徑剩下偶數個頂點,可沿其原有的邊按相鄰順序兩兩配對。連同這條連接邊與其他圈上的匹配邊,這再次構成一個完全位於原圖中的完美匹配。這一矛盾證明了斷言。
現在令 為全體全鄰頂點。若 的某個分支不是完全圖,則該分支中兩個不相鄰頂點之間的最短路徑一開始就有兩條邊 ,其端點 不相鄰。它的中間頂點 不在 中,這與斷言矛盾。因此每個這樣的分支都是完全圖。
證明透視
兩條被禁止的額外邊迫使出現一條可用的原有邊
飽和性把每條缺失的邊變成一個假想的完美匹配。它們的交錯並集孤立出原圖中唯一不可用的那些邊。若它們位於不同的圈上,一次切換即可同時避開兩者。若它們位於同一個圈上,去掉它們後得到這兩條路徑,而已知的兩條邊的構型提供一條交叉邊,連接這兩條路徑的暴露端點。結構性結論來自對這兩種情形的全面涵蓋。
奇分支條件的充分性
證明
(把奇團匹配到全鄰頂點集)
假設該條件成立,但不存在完美匹配。不斷加入邊,直到圖成為沒有完美匹配的飽和圖。加入邊保持該條件:對任何固定的刪除集 ,新邊要麼位於某個分支內部,要麼合併兩個分支。合併兩個奇分支使奇分支個數減少二;合併其他任意一對分支不會使其增加。
對這個擴充後的圖應用結構引理。它的非全鄰分支都是團。設其中有 個是奇數階的。在全鄰集合 處的條件說明 。利用全鄰性,把每個奇團中的一個頂點與 中互不相同的頂點匹配。其餘所有頂點在各團內部配對;偶數階團在內部配對,不需要使用 。
該圖的階數為偶數,因為空集處的條件排除了任何奇分支。總階數的奇偶性也就是 的奇偶性,因為只有奇團有貢獻。因此 為偶數。尚未使用的全鄰頂點構成一個該偶數階的團,可以彼此配對。我們構造出了一個完美匹配,與沒有完美匹配的飽和性矛盾。這就證明了充分性,從而證明了判別準則。
把障礙轉化為精確虧量
證明
(加入 個全鄰頂點)
令 ,加入 個新頂點,使它們彼此相鄰,並與每個原有頂點相鄰。把擴充後的圖記為 。由已證明的奇偶性結論,其階數 為偶數。我們對每個刪除集 驗證其奇分支條件。
若至少有一個新頂點保留下來,則所有保留的頂點位於同一個分支中。對非空的 ,其奇分支個數至多為一,因而至多為 。對空的 ,總階數為偶數,故個數為零。若沒有新頂點保留下來,把 寫成全部 個新頂點連同原有頂點 。剩下的圖是 ,而 的定義給出 。
判別準則給出 的一個完美匹配。刪去其中的新頂點及其關聯的所選邊。至多有 個原有頂點失去夥伴,所以 中的這個匹配至多留下 個未匹配頂點。結合前面的下界,即證明了等式。當 時,同樣的論證就是直接對 應用判別準則。
對於奇數階圖,每個候選虧量都是奇數,其最大值非負,故 。所述的近完美條件說明 ,因而等價於 ,由此完成該推論的證明。
存在性證明沒有高效計算的內容
飽和論證需要判斷每條可能加入的額外邊是否產生完美匹配;它並沒有給出回答這一問題的高效方法。同樣,枚舉每個刪除集給出的是有限但指數級的檢驗。該等式是一個結構性的證書定理,而不是隱藏在存在性構造中的多項式時間匹配實現。
前面的二部圖增廣路徑論證避開了部分這類困難,因為它的交錯搜尋具有固定的兩側結構。在一般圖中,奇交錯結構需要額外處理。這裏的定理獨立於任何此類實現來解釋精確的障礙,並且提供了一種驗證所給下界證書的方法:刪去所列出的頂點並數出奇分支的個數。
例題詳解
例題 6.2.5
(三個奇分支在偶數階時阻礙完美匹配)
取三個互不相交的三角形與一個額外的樞紐頂點。把樞紐與每個三角形中選定的一個頂點相連,沒有其他的跨邊。共有十個頂點。刪去樞紐後留下三個奇分支,所以條件不成立,因為三大於一。
存在大小為四的匹配:把樞紐與某個三角形中的一個頂點匹配,把該三角形的另外兩個頂點配成一對,並在其餘每個三角形內部各取一條邊。它留下兩個未匹配的頂點。刪去樞紐給出虧量二,而所給出的匹配說明不可能出現更強的下界。因此最大匹配大小恰好為四,儘管每個頂點的度數至少為二。
例題 6.2.6
(奇圈恰好有一個未匹配頂點)
在按循環順序排列的五圈頂點 上,選取 與 ,留下一個未匹配頂點。空刪除集給出一個奇分支,因而虧量至少為一。匹配下界的論證同時說明,每個虧量表達式至多等於該匹配中那一個未匹配頂點。
因此 ,並且該匹配是最大的。奇數階阻止了完美性,但並不迫使有三個或更多未匹配頂點。精確虧量定理刻劃了這一區別。
例題 6.2.7
(偶數階完全圖滿足每個刪除檢驗)
在 中,刪除 後留下階數為 的團。當該階數為正且為奇數時它有一個奇分支,否則有零個。若 為空,則個數為零;若 非空,則個數至多為一,因而至多為 。
條件成立,並且兩條互不相交的邊給出一個完美匹配。該圖含有三角形,所以非二部性本身並不構成障礙。相關的條件涉及的是刪除之後的奇分支,而不是原圖中是否沒有奇圈。
概念視角組合
每個奇分支都需要一個不同的邊界夥伴,否則就有一個未匹配頂點
若一個奇分支的所有匹配邊都留在其內部,則它有一個奇偶虧欠。一個被刪除的頂點至多吸收一個這樣的虧欠。在所有邊界上取超出量的最大值,就得到不可避免的未匹配頂點的精確個數。充分性的證明表明,一旦所有這些奇偶性需求都得到滿足,就不再有隱藏的額外虧欠。
常見錯誤
反例模式
總階數為偶數並不能抵銷分離的奇需求
三葉星圖有四個頂點,但刪去其中心後留下三個奇數階的單點分支,而只有一個被刪頂點可供它們使用。其最大匹配只有一條邊,留下兩個未匹配頂點。僅有偶數階不能取代奇分支條件。
常見錯誤
(奇圈不是奇分支)
不要把奇圈當作奇連通分支來計數。偶數階團含有許多奇圈,卻仍有完美匹配; 通過每一個刪除檢驗。
常見錯誤
(高度數或連通性不能防止虧量刪除)
不要以為較高的最小度或連通的原圖就能防止一個小的刪除集暴露出若干彼此獨立的奇需求。三個三角形接到一個中心頂點的圖連通且最小度為二,但只刪去中心就留下三個奇分支,迫使兩個頂點未被匹配。
總結
奇分支對任何匹配給出必要的奇偶性需求。飽和障礙論證證明,滿足所有這些需求對於存在完美匹配是充分的。再加入全鄰頂點,就把判別準則轉化為未匹配頂點個數的精確公式。這些結構性證明給出完整的證書,而高效的一般匹配搜尋則留作另一個獨立的算法任務。
練習
快速檢查
(求兩個三角形的不交並的最大匹配與精確虧量。)
利用空刪除集與一個具體給出的匹配,從兩側界定同一個量。
解答 · 答案
空集暴露出兩個奇分支,所以每個匹配至少留下兩個未匹配頂點。在每個三角形中各選一條邊,得到兩條邊,恰好留下兩個未匹配頂點。因此 且 。在圖中從概念上把這兩個分支連起來會改變這個圖;它們各自分離的奇需求無法共用一條並不存在的匹配邊。
快速檢查
(對有四片葉子的星圖,求一個達到最大虧量的刪除集,並解釋為甚麼加入三個全鄰頂點後,擴充圖就有完美匹配。)
先把中心與某一片葉子配對,再分配其餘的葉子。
解答
刪去中心後留下四個奇數階的單點分支,超出量為 。單獨一條從中心到葉子的邊就是最大匹配,因為所有邊都共用中心,它留下三個未匹配頂點。因此最大虧量恰好為三。
加入三個全鄰頂點。把中心與一片原有的葉子匹配,並把每個新頂點與一片不同的剩餘葉子匹配。這四條邊覆蓋全部八個頂點。去掉新頂點後,恰好剩下原來的單邊匹配,這說明了虧量證明,而不需要任何新頂點之間的所選邊。
快速檢查
(直接從完美匹配判別準則證明:奇數階圖存在漏掉一個頂點的匹配,當且僅當加入一個全鄰頂點後得到完美匹配。)
考察新頂點的夥伴,並利用原圖的近完美不等式驗證判別準則。
解答
漏掉一個頂點的匹配,可以透過把該頂點與新的全鄰頂點配對而擴充為完美匹配。反過來,從完美匹配中刪去新頂點;它在原圖中的那個夥伴變成未匹配的,而其他所有原有頂點仍保持匹配。
對於判別準則,設對每個原有的 都有 。在擴充圖中,包含新頂點的刪除集留下 ,其大小為 ,所以滿足條件。若新頂點保留下來,則剩下的圖是連通的;非空的刪除集至多容許一個奇分支,而空的刪除集留下偶數總階數。因此每個刪除集都滿足判別準則,從而得到所述的完美匹配,進而得到原圖的近完美匹配。