第五章 匹配與因子分解

一、偶圖的匹配問題

(一)、圖的匹配與貝爾熱定理

1、圖的匹配相關概念

(1)、匹配 M— 如果M是圖G的邊子集(不含環），且M中的任意兩條邊沒有共同頂點，則稱M是G的一個匹配或對集或邊獨立集。

如果G中頂點v是G的匹配 M中某條邊的端點，稱它為M飽和點，否則為M非飽和點。

(2)、最大匹配 M— 如果M是圖G的包含邊數最多的匹配，稱M是G的一個最大匹配。特別是，若最大匹配飽和了G的所有頂點，稱它為G的一個完美匹配。

注：1、一個圖G不一定存在完美匹配；
2、一個圖G的完美匹配若存在，不一定唯一；
3、一個圖G的最大匹配不一定唯一。

(3)、M交錯路— 如果M是圖G的匹配，G中一條由M中的邊和非M中的邊交錯形成的路，稱為G中的一條M交錯路。特別地，若M交錯路的起點與終點是M非飽和點，稱這種M交錯路為M可擴路。

2、貝爾熱定理

定理1 (貝爾熱，1957) G的匹配M是最大匹配，當且僅當G不包含M可擴路。

注：貝爾熱定理給我們提供了擴充G的匹配的思路。

(二)、偶圖的匹配與覆蓋

1、問題的提出

2、偶圖匹配存在性判定----Hall定理

**定理2 (Hall定理）**設G=(X, Y)是偶圖，則G存在飽和X每個頂點的匹配的充要條件是：對$?S?X$,有$|N(S)|\ge |S|...(?)$

? 其中，$N(S)$表示S的鄰點集

注: (1) G=(X,Y) “飽和X每個頂點的匹配”也常說成“存在由X到Y的匹配”。

? (2) Hall定理也可表述為：設G=(X,Y)是偶圖，如果存在X的一個子集S,使得|N(S)| < |S| ，那么G中不存在由X到Y的匹配。

? (3) Hall定理也稱為“婚姻定理”，表述如下：
? “婚姻定理” ：在一個由r個女人和s個男人構成的人群中，1≦r≦s。在熟識的男女之間可能出現r對婚姻的充分必要條件是，對每個整數k(1≦k≦r),任意k個女人共認識至少k個男人。
? (4) Hall定理是在偶圖中求最大匹配算法的理論基礎，即匈牙利算法基礎。

推論：若G是k (k>0)正則偶圖，則G存在完美匹配。

? (1) 證明：每個k方體都有完美匹配(k大于等于2)

k方體是k正則偶圖，故存在完美匹配

? (2) 求K2n和Kn,n中不同的完美匹配的個數。

$K_{2n}$不同的完美匹配的個數為$(2n?1)!!$，$K_{n,n}$不同的完美匹配的個數為$n!$

(3)證明樹至多存在一個完美匹配。

證明：若不然，設M1與M2是樹T的兩個不同的完美匹配，那么$M_1\Delta M_2=?$，且$T[M_1\Delta M_2]$每個頂點度數為2，即它存在圈，于是推出T中有圈，矛盾。

3、點覆蓋與哥尼定理

(1)、圖的點覆蓋概念與性質

定義1：圖的點覆蓋 —G的一個頂點子集K稱為G的一個點覆蓋，如果G的每條邊都至少有一個端點在K中。G的一個包含點數最少的點覆蓋稱為G的最小點覆蓋，其包含的點數稱為G的覆蓋數，記為α(G).

定理2 設M是G的匹配，K是G的覆蓋，若|M|=|K|,則M是最大匹配，而G是最小覆蓋。

(2)、偶圖的點覆蓋與偶圖匹配間的關系----哥尼定理

定理2 (哥尼，1931) 在偶圖中，最大匹配的邊數等于最小覆蓋的頂點數。

二、圖的因子分解

研究圖的因子分解主要是兩個方面：一是能否進行分解(因子分解的存在性),二是如何分解(分解算法).

(一)、托特定理

定理 (托特定理，1947) 圖G有完美匹配當且僅當對V的任意非空真子集S, 有：
$$o(G?S)\le |S|$$
? 其中，$o(G?s)$表示奇分支數目,（奇分支是階數為奇的連通分支）

? 推論 (彼得森定理) 沒有割邊的3正則圖存在完美匹配。

注：推論中的條件是G存在完美匹配的充分條件而不是必要條件

(二)、圖的一因子分解

所謂一個圖G的因子$G_i$，是指至少包含G的一條邊的生成子圖。

所謂一個圖G的因子分解，是指把圖G分解為若干個邊不重的因子之并。

所謂一個圖G的n因子，是指圖G的n度正則因子。

如果一個圖G能夠分解為若干n因子之并，稱G是可n因子分解的。

圖的一個一因子實際上就是圖的一個完美匹配的導出子圖。一個圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配的導出子圖之并。

定理1 $K_{2n}$可一因子分解。

(作圖)

例2 證明：每個k (k>0)正則偶圖G是一可因子分解的。

證明：因為每個k (k>0)正則偶圖G存在完美匹配，設Q是它的一個一因子，則G-Q還是正則偶圖，由歸納知，G可作一因子分解。

定理2 具有H圈的三正則圖可一因子分解。

證明：先從三正則圖G中抽取H圈，顯然剩下邊構成G的一個一因子。而H圈是偶圈，它顯然可以分解為兩個一因子。所以G可以分解為3個一因子。

定理3 若三正則圖有割邊，則它不能一因子分解。

證明：若不然，設G的三個一因子為G1,G2,G3。不失一般性，設割邊e∈ G1。 顯然，G-G2的每個分支必然為圈。所以e在G的某個圈中，這與e是G的割邊矛盾。

注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。

(三)、圖的二因子分解

如果一個圖可以分解為若干2度正則因子之并，稱G可以2因子分解。注意：G的一個H圈肯定是G的一個2因子，但是G的一個2因子不一定是G的H圈。2因子可以不連通。

一個顯然結論是：G能進行2因子分解，其頂點度數必然為偶數。(注意，不一定是歐拉圖)

定理4 $K_{2n+1}$可因子分解。

定理5 $K_{2n}$可分解為一個1因子和n-1個2因子之和。

定理6 每個沒有割邊的3正則圖是一個1因子和1個2因子之和。

定理7 一個連通圖可2因子分解當且僅當它是偶數度正則圖。

(四)、圖的森林因子分解

把一個圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。

三、匈牙利算法與最優匹配算法

(一)、匈牙利算法

(1)、問題

設G=(X, Y), |X|=|Y|, 在G中求一完美匹配M.

(2)、基本思想

從任一初始匹配M0出發，通過尋求一條M0可擴路P，令M1=M0ΔE§, 得到比M0更大的匹配M1(近似于迭代思想)。

? M可擴路尋找方法—交錯樹方法

(3)、算法流程

設M是初始匹配。H是扎根于M非飽和點u的交錯樹。令：S=V(H)∩X, T=V(H)∩Y。

(a) 、若M飽和X所有頂點，停止。否則，設u為X中M非飽和頂點，置S=｛u｝,T=Φ;

(b) 、若N(S)=T, 則G中不存在完美匹配。否則設 y ∈N(S) – T.

(c ) 若y為M飽和點，且y z ∈M, 置S=S∪｛z｝, T=T∪｛y｝,轉(b)。否則，設P為M可擴路，置M1=MΔE§，轉(a).

(4)、求偶圖最大匹配

分析：使用匈牙利算法求完美匹配時，當在扎根于M非飽和點u的交錯樹上有|N(S)|<|S|時，由Hall定理，算法停止。要求出最大匹配，應該繼續檢查X-S是否為空，如果不為空，則檢查是否在其上有M非飽和點。一直到所有M非飽和點均沒有M可擴路才停止。

(二)、最優匹配算法(庫恩算法)

1 、問題

設G=(X, Y)是邊賦權完全偶圖，且X=｛x1, x2,…,xn｝Y=｛y1, y2,…,yn｝, wij=w(xiyj)。在G中求出一個具有最大權值的完美匹配，稱為最優匹配。

2 、可行頂點標號與相等子圖

定義2 設G=(X, Y), 若對任意的x ∈X, y ∈Y,有：$l(x)+l(y)\ge w(xy)$， 稱 l 是賦權完全偶圖G的可行頂點標號。

? 事實上，設：
$$\{\begin{array}{l}l(x)=\underset{y\in Y}{\max }w(xy),若x\in X,\\ l(y)=0,若y\in Y\end{array}$$
? 則 l 是G的一個可行頂點標號。

定義3 設 l 是賦權完全偶圖G=(X, Y)的可行頂點標號，令：$E_l=\{xy\in E(G)|l(x)+l(y)=w(xy)\}$， 稱$G_l=G[E_l]$為G的對應于l 的相等子圖。

定理 設 l 是賦權完全偶圖G=(X, Y)的可行頂點標號，若相等子圖$G_l$有完美匹配M*,則M*是G的最優匹配。

? 證明：設M*是$G_l$的完美匹配，則：
$$w(M^{?})=\sum _{e\in M^{?}}w(e)=\sum _{v\in V(G)}l(V)$$
又設M是G的任一完美匹配，則：
$$w(M)=\sum _{e\in M}w(e)\le \sum _{v\in V(G)}l(V)$$
? 所以，w (M*)≥w (M)。即M*是G的最優匹配。

3、算法思想及流程

采用頂點標號修改策略。流程如下：

給一初始頂點標號l ,在G$G_l$任選一個匹配M。

(1) 若X是M飽和的，則M是最優匹配。否則，令u是一個M非飽和點，置：S=｛u｝,T=Φ。

(2) 若$N_{G_l}(S)?T$ ，轉(3)。否則，計算：$$\begin{gathered} {\alpha }_l=\underset{x\in S \\ y\in /T}{\min }\{l(x)+l(y)?w(xy)\} \end{gathered}$$
$$\hat{l}=??\begin{array}{l}l(v)?{\alpha }_l,v\in S\\ l(v)+{\alpha }_l,v\in T\\ l(v),其他\end{array}$$
給出新的可行頂點標號，在新標號下重新開始。

(3) 在$N_{G_l}(S)?T$中選擇點y。若y是M飽和的，yz ∈M,則置S=S∪｛z｝,T=T∪｛y｝轉(2)。否則，設P是$G_l$中M可擴路，置M=MΔE§,轉(1).

注：該算法把匈牙利算法用于其中，主要是用來判定和求完美匹配。

總結：常用符號

$\alpha (G)$ 表示圖$G$的覆蓋數，為G的最小點覆蓋包含的點數

總結：常用性質定理

1、貝爾熱定理

G的匹配M是最大匹配，當且僅當G不包含M可擴路

2、偶圖匹配存在性判定----Hall定理

? G=(X, Y)是偶圖，則G存在飽和X每個頂點的匹配的充要條件是：

? 對$\forall S \subseteq X $,有$|N(S)|\geq|S|…(*)$

? 其中，$N(S)$表示S的鄰點集

3、哥尼定理

在偶圖中，最大匹配的邊數等于最小覆蓋的頂點數

4、托特定理

? 圖G有完美匹配當且僅當對V的任意非空真子集S, 有：
$$o(G?S)\le |S|$$
? 其中，$o(G?s)$表示奇分支數目,（奇分支是階數為奇的連通分支）

5、彼得森定理

? 沒有割邊的3正則圖存在完美匹配

6、匈牙利算法（偶圖中求完美匹配以及最大匹配）

7、庫恩算法（最優匹配算法）

設G=(X, Y)是邊賦權完全偶圖，且X=｛x1, x2,…,xn｝Y=｛y1, y2,…,yn｝, wij=w(xiyj)。在G中求出一個具有最大權值的完美匹配。

方法：可行頂點標號----生成子圖----匈牙利完美匹配算法----計算權值$$\begin{gathered} {\alpha }_l=\underset{x\in S \\ y\in /T}{\min }\{l(x)+l(y)?w(xy)\} \end{gathered}$$----更改相應可行頂$\hat{l}=?\begin{array}{l}l(v)?{\alpha }_l,v\in S\\ l(v)+{\alpha }_l,v\in T\\ l(v),其他\end{array}$,重復

8、其他

定理 設 l 是賦權完全偶圖G=(X, Y)的可行頂點標號，若相等子圖$G_l$有完美匹配M*,則M*是G的最優匹配。

總結：一些結論

• 一個圖G不一定存在完美匹配。一個圖G的完美匹配若存在，不一定唯一。一個圖G的最大匹配不一定唯一

• 若G是k (k>0)正則偶圖，則G存在完美匹配。

• 每個k方體都有完美匹配(k大于等于2)

• $K_{2n}$不同的完美匹配的個數為$(2n?1)!!$，$K_{n,n}$不同的完美匹配的個數為$n!$

• 樹至多存在一個完美匹配

• 有完美匹配的三正則圖不一定沒有割邊

• 三正則哈密爾頓圖存在完美匹配，可1-因子分解

• 任意非平凡正則偶圖包含完美匹配且能夠1-因子分解

• $K_{2n}$可一因子分解，$K_{2n+1}$可2因子分解， $K_{2n}$可分解為一個1因子和n-1個2因子之和。

• 每個沒有割邊的3正則圖是一個1因子和1個2因子之和

• 一個連通圖可2因子分解當且僅當它是偶數度正則圖

總結

以上是生活随笔為你收集整理的电子科技大学《图论及其应用》复习总结--第五章 匹配与因子分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。