【正文】 證明：若不然，設(shè) M1與 M2是樹 T的兩個(gè)不同的完美匹配，那么 M1ΔM2≠Φ,且 T[M1ΔM2]每個(gè)頂點(diǎn)度數(shù)為 2，即它存在圈，于是推出 T中有圈，矛盾。 K2n的任意一個(gè)頂點(diǎn)有 2n1中不同的方法被匹配。 設(shè) k方體頂點(diǎn)二進(jìn)制碼為 (x1 ,x2,…,x n),我們?nèi)?(x1 ,x2,…,x n1,0),和 (x1 ,x2,…,x n1,1) 之間的全體邊所成之集為 M. 顯然， M中的邊均不相鄰接，所以作成 k方體的匹配，又容易知道： |M|= M是完美匹配。 由推論： k方體存在完美匹配。所以 k方體是偶圖。 如果我們劃分 k方體的 2k個(gè)頂點(diǎn)，把坐標(biāo)之和為偶數(shù)的頂點(diǎn)歸入 X，否則歸入 Y。 (1) 證明一：證明每個(gè) k方體都是 k正則偶圖。即 Q是一條閉跡。 H是歐拉圖，所以存在歐拉環(huán)游 T. 對(duì)于 T，把它看成 v為起點(diǎn)和終點(diǎn)的一條歐拉跡，顯然不能擴(kuò)充為 G的歐拉環(huán)游。 考慮 G1=GE(G)的含有頂點(diǎn) v的分支 H。證明： G的每條具有起點(diǎn) v的跡都能擴(kuò)展成 G的歐拉環(huán)游當(dāng)且僅當(dāng)Gv是森林。令 vl， v2， …,v k,vk+1,…,v 2k是 G的所有奇度點(diǎn)。 y1 y2 y3 y4 y5 x1 x2 x3 x4 x5 章 4習(xí) 8，證明：若 G有 2k0個(gè)奇數(shù)頂點(diǎn)，則存在 k條邊不重的跡 Q1,Q2,…,Q k，使得： 12( ) ( ) ( ) ( )kE G E Q E Q E Q? 證明：不失一般性，只就 G是連通圖進(jìn)行證明。取 n=3， vn+1=3 ，故由定理 16知 det M 的每一項(xiàng)均為零。于是 M有一個(gè) n (vn+1)階的零子矩陣。 Hall定理表明不存在這樣的完美匹配當(dāng)且僅當(dāng)存在 X的一個(gè)子集 S，使 |N(S)|≤|S|1, 設(shè) |S| = n。 證明 作一個(gè)具有二分類 (X , Y) 的偶圖 G，其中 X = {x1,x2,…, xv} ， Y = {y1,y2,…, yv}， xi 與 yj 鄰接當(dāng)且僅當(dāng)在 M 中 aij≠0。 167。若要求考慮效率，并問 “ 如何安排使效率最大 ” ，這稱為 最優(yōu)安排問題 。 v1 u3 u4 u2 u1 v3 v4 v5 u5 v2 (b) v1 u3 u4 u2 u1 v3 v4 v5 u5 v2 (c) 取 M = {v1u2， v2u1， v3u3 ， v4u5， v5u4}， 如圖（ c） 中紅邊。 ( 3 ) 取 X的非飽和點(diǎn) v4。 ③ 因 N (S)= {u1, u2, u3}≠T ， 故取 u2∈ N (S) \ T = {u2, u3}。 ① 因 N (S) = {u1, u3}≠T ， 故取 u1∈ N (S) \ T = N (S) = {u1, u3}。 （ 1） 任取一個(gè)匹配 M = {v1u1， v3 u3， v5u5}， 如圖（ a） 的紅邊所示。 （注意，這樣替換后， |T|=|S|1依然成立） (7) 存在 u 到 y 的 M 可擴(kuò)路 Γ， 令 M’= ( M∪ E(Γ)) \ ( M∩E(Γ))， M= M’， 轉(zhuǎn)（ 2）。 (5) 若 y 為飽和點(diǎn)，則轉(zhuǎn)（ 6）；否則轉(zhuǎn)（ 7）。 (4) 若 N (S) = T， 則 （此時(shí)由于 |T|=|S|1，所以 |N(S)||S|, 若求飽和 X中每個(gè)點(diǎn)的匹配則停 (問題無解 )。 (3) 取 X 的非飽和點(diǎn) u， 令 S = {u}， T =Φ。開始時(shí)， H僅由單一頂點(diǎn)u組成，而在以后的步驟中若始終是下圖 (a)的情況 , 則無 M可擴(kuò)路：若出現(xiàn)下圖 (b)的情況 , 則找到了 M可擴(kuò)路： u （ a） u （ b） 匈牙利算法 (求飽和 X中每個(gè)點(diǎn)的或最大匹配 ) 給定具有二分類 ( X, Y)。這是因偶圖中不可能存在兩個(gè)端點(diǎn)均在 V 2 中的 M 可擴(kuò)路。 算法是從 V1 的每個(gè)非飽和點(diǎn)出發(fā)尋找 M 可擴(kuò)路的。 最優(yōu)匹配與匈牙利算法 一、匈牙利算法 算法思想： 先任取一個(gè)匹配 M， 然后尋找 M 可擴(kuò)路。所以此問題實(shí)際上是求偶圖的完美匹配問題 . 進(jìn)一步： 若不要求人數(shù)與工作數(shù)相等，則問題是求偶圖的飽和 V1的每個(gè)點(diǎn)的匹配問題，其中 V1是工人的集合；進(jìn)一步，若問：能否存在一種安排使盡可能多的人能分到他能勝任的工作或使盡可能多的工作被分配，則問題為 求偶圖的最大匹配問題 。 問能否存在一種工作安排方案，使每個(gè)人都能分配到他所能勝任的一件工作。 人員分派 問題： n 個(gè)工人 x1, x2,…, xn， n 件工作 y1, y2,…, yn。所以有 推論 完全圖和完全偶圖的蔭度為 ?????? ?????????? 1)(,2)( , sr rsKnK srn ??例 4 分 K7為生成林的最小分解如下圖所示。對(duì)于子圖 H，顯然有 σ(G)≥σ(H)，故σ(G)≥ 。 例 σ(K4)=2 σ(K5) =3 定理 14 令 G是一個(gè)非平凡圖，又令 ms是 G的任何一個(gè)有 s個(gè)點(diǎn)的子圖中邊的最多數(shù)目，則 ?????? ?? 1m a x)( smG ss?σ(G)≥ 的證明 因?yàn)槿?G有 n個(gè)點(diǎn)，則在任何一個(gè)生成林中邊的最多數(shù)目是 n－ 1。 (由定理 5的推論可證 ) 例 彼得森圖 是一個(gè)1因子和一個(gè) 2因 子的和 注 若沒有割邊的 3度正則圖中的 2因子是一些偶圈 , 則該圖也是 1可因子化的 . 定理 13 一個(gè)連通圖是 2可因子化的當(dāng)且僅當(dāng)它是偶數(shù)度正則的。 Pi 的第 j 點(diǎn)是 vk ，其中 k = i + (1) j P2=2(2+1)(21)(2+2)(22)(2+3)=231465 (mod 6) ? ?2j定理 11 完全圖 K2n是一個(gè) 1因子和 n1個(gè) H圈的和。其實(shí)線就是一個(gè) 2－因子，它是一個(gè) Hamilton圈 H1= v7v1v2v6v3v5v4v7，若將1, 2, 3, 4, 5, 6繞中心按順時(shí)間方向移動(dòng)一個(gè)位置（下圖（ b）），則得另一個(gè) H 圈 H2= v7v2v3v1v4v6v5v7，第三個(gè)H 圈必然是 H3 = v7v3v4v2v5v1v6v7，則 K7 =H1∪ H2∪ H3。 例 3 將 K7分解成 3個(gè)生成圈的和。 其中 Pi 的第 j 點(diǎn)是 vk ， k = i + (1) j ，并且所有下標(biāo)取為整數(shù) 1， 2， … ， 2n（ mod 2n）。 證明 為了在 K2n+1 中構(gòu)成 n個(gè)邊不相交的生成圈，先標(biāo)定它的點(diǎn) v1,v2,…, v2n+1。 (3) 若一個(gè) 2因子是連通的，則它是一個(gè) H圈。 二 . 2－因子分解 由定義有 : (1) 若一個(gè)圖是 2可因子化，則每個(gè)因子一定是不相交圈的一個(gè)并。 2n 2 3 2n1 n n+1 1 圖 1 v1 v2 v6 v3 v5 v4 K6 G2 G5 G1 G4 圖 2 G3 例 2 將 K3,3作 1因子分解 解 我們將 X的點(diǎn)用數(shù)字 1， 2， 3標(biāo)記，而 Y的點(diǎn)用 1’， 2’， 3’來標(biāo)記，用置換 G來表示 K3,3中 X的點(diǎn)與 Y的點(diǎn)間之匹配關(guān)系，則 11 2 31 2 3G??? ??? ? ??? 21 2 32 3 1G??? ??? ? ??? 31 2 33 1 2G??? ??? ? ??? 1 2 3 1’ 2’ 3’ K3,3 G1 G2 G3 圖為 定理 9 若 3正則圖有割邊，則不可 1因子分解。 如圖 1, 除 2n外，它們中的每一個(gè)數(shù)，按箭頭方向移動(dòng)一個(gè)位置；在每個(gè)位置中，同一行的兩點(diǎn)鄰接就得到一個(gè) 1因子，共有 2n1個(gè)不同的位置就產(chǎn)生了 2n1個(gè)不同的 1因子，從而完成了的 1因子分解。 例 1 求 K6的 1因子分解。所以 , 奇階圖不能有 1因子。 n因子分解 ：每個(gè)因子均為 n因子的因子分解，此時(shí)稱G本身是 n可因子化的。 例 彼得森圖滿足推論的條件（即沒有割邊的 3正則圖），故它有完美匹配 . 注 :有割邊的 3正則圖不一定有完美匹配 沒有完美匹配 有完美匹配 167。 定理 5（ Tutte） G有完美匹配當(dāng)且僅當(dāng) o(G－ S) ≤|S| , 對(duì)所有 S?V成立 （ ） 證明冗長，從略。 ?????????????1000001010100111Q x1 x2 x3 x4 y1 y2 y3 y4 167。而具有上述性質(zhì)的 1的最大個(gè)數(shù)，就是偶圖 G中最大匹配的邊數(shù)，由定理 5，問題得證 . 例如 , 矩陣 Q 及其對(duì)應(yīng)的偶圖如下圖。 這樣 , 此矩陣的第 i 行線包含 1的個(gè)數(shù)就是 G 中點(diǎn) xi 關(guān)聯(lián)的邊數(shù)，而第 j 列線包含 1的個(gè)數(shù)就是 G中點(diǎn) yj 關(guān)聯(lián)的邊數(shù)，故包含了（ 0,1）矩陣中所有 〝 1〞 的線的最小條數(shù)就是偶圖 G中的最小覆蓋的點(diǎn)數(shù)。 例 1 矩陣的一行或一列統(tǒng)稱為一條線。于是 是 G的覆蓋。 哥尼 1944年為免遭納碎迫害，選擇了自殺。特別是，他把一起獲得匈牙利國家高中數(shù)學(xué)競賽一等獎(jiǎng)的 3個(gè)學(xué)生都吸引來研究圖論，這 3個(gè)學(xué)生是：Erd214。他一直工作在布達(dá)佩斯工業(yè)大學(xué)。直到 1958年，法國數(shù)學(xué)家貝爾熱 (Berge）才出版專著 《 無限圖理論及其應(yīng)用 》 。 該書對(duì)青年學(xué)者產(chǎn)生了很大影響，推動(dòng)了圖論的進(jìn)一步發(fā)展。 K~S U T=N (S) X \S 哥尼 (K214。 類似于定理 2的證明，可知 T中的每個(gè)頂點(diǎn)都是 M*飽和的，并且 N(S)＝ T。 證明 設(shè) G 是具有二分類（ X, Y）的偶圖， M*是 G的最大匹配，用 U 表示 X 中的 M* 非飽和頂點(diǎn)的集，用 Z 表示由 M 交錯(cuò)路連接到 U 中頂點(diǎn)的所有頂點(diǎn)的集。 K~證明 設(shè) M*是最大匹配 , 是最小覆蓋，則由（ ）式，