【正文】 求的安排對(duì)應(yīng) G 中一個(gè)完美匹配。所以此問題實(shí)際上是求偶圖的完美匹配問題 . 進(jìn)一步： 若不要求人數(shù)與工作數(shù)相等，則問題是求偶圖的飽和 V1的每個(gè)點(diǎn)的匹配問題，其中 V1是工人的集合；進(jìn)一步，若問：能否存在一種安排使盡可能多的人能分到他能勝任的工作或使盡可能多的工作被分配，則問題為 求偶圖的最大匹配問題 。 167。 最優(yōu)匹配與匈牙利算法 一、匈牙利算法 算法思想： 先任取一個(gè)匹配 M， 然后尋找 M 可擴(kuò)路。若不存在 M 可擴(kuò)路，則 M 為最大匹配；若存在，則將可擴(kuò)路中 M 與非 M 的邊互換，得到一個(gè)比 M 多一條邊的匹配 M ’， 再對(duì) M ’ 重復(fù)上面過程。 算法是從 V1 的每個(gè)非飽和點(diǎn)出發(fā)尋找 M 可擴(kuò)路的。若從 V1 的每個(gè)非飽和點(diǎn)出發(fā)都無 M 可擴(kuò)路，則 M 必?zé)o可擴(kuò)路，從而 M 是最大匹配。這是因偶圖中不可能存在兩個(gè)端點(diǎn)均在 V 2 中的 M 可擴(kuò)路。 定義 1 設(shè) M是 G中的匹配， u是 X的 M非飽和點(diǎn)，若樹 H?G 滿足 （ ⅰ ） v∈ V(H)； （ ⅱ ）對(duì) H的每個(gè)頂點(diǎn) v， H中唯一的（ u, v）路是一條 M交錯(cuò)路， 則稱樹 H是一棵 扎根于 u的 M交錯(cuò)樹 （如下圖） x1 x2 x3 x4 x5 x6 y1 y2 y3 y4 y5 y6 G的一個(gè)匹配 M x6 y5 y6 x3 x2 x4 x1= u G的一棵 M交錯(cuò)樹 算法中 ,尋找以 u為起點(diǎn)的一條 M可擴(kuò)路，其過程包含了“生長”一棵扎根于 u的 M交錯(cuò)樹 H。開始時(shí)， H僅由單一頂點(diǎn)u組成，而在以后的步驟中若始終是下圖 (a)的情況 , 則無 M可擴(kuò)路：若出現(xiàn)下圖 (b)的情況 , 則找到了 M可擴(kuò)路： u （ a） u （ b） 匈牙利算法 (求飽和 X中每個(gè)點(diǎn)的或最大匹配 ) 給定具有二分類 ( X, Y)。 的偶圖 . (1) 任取一個(gè)匹配 M。 (3) 取 X 的非飽和點(diǎn) u， 令 S = {u}， T =Φ。 （有|T|=|S|1） (2) 若 X 中每個(gè)點(diǎn)均為 M 飽和點(diǎn)，則停（輸出 M）； 否 則繼續(xù)（ 3）。 (4) 若 N (S) = T， 則 （此時(shí)由于 |T|=|S|1，所以 |N(S)||S|, 若求飽和 X中每個(gè)點(diǎn)的匹配則停 (問題無解 )。若求最大匹配則將 u也作為 M 飽和點(diǎn)對(duì)待，轉(zhuǎn) (2))；否則取 y∈ N( S)\ T。 (5) 若 y 為飽和點(diǎn)，則轉(zhuǎn)（ 6）；否則轉(zhuǎn)（ 7）。 (6) 存在 z∈ X， 有 yz∈ M， 令 S = S∪ {z}， T = T∪ {y}， 轉(zhuǎn)（ 4）。 （注意，這樣替換后， |T|=|S|1依然成立） (7) 存在 u 到 y 的 M 可擴(kuò)路 Γ， 令 M’= ( M∪ E(Γ)) \ ( M∩E(Γ))， M= M’， 轉(zhuǎn)（ 2）。 例 1 求圖 G（ 如圖（ a） 所示）的最大匹配，其中 X={v1, v2, v3, v4, v5}。 （ 1） 任取一個(gè)匹配 M = {v1u1， v3 u3， v5u5}， 如圖（ a） 的紅邊所示。 ( 2 ) 顯然 X中存在非飽和點(diǎn)，取其中一個(gè) v2， 令 S = {v2}， T =Φ。 ① 因 N (S) = {u1, u3}≠T ， 故取 u1∈ N (S) \ T = N (S) = {u1, u3}。 ② u1為飽和點(diǎn)，且 v1u1 ∈ M ，令 S = S∪ { v1} = {v1,v2}， T = T∪ { u1}= { u1}。 ③ 因 N (S)= {u1, u2, u3}≠T ， 故取 u2∈ N (S) \ T = {u2, u3}。 ④ u2 為非飽和點(diǎn)，得 M可擴(kuò)路 Γ= v2u1v1u2 v1 u3 u4 u2 u1 v3 v4 v5 u5 v2 (a) ⑤ 取 M = ( M∪ E(Γ))\ ( M∩E(Γ)) = {v2u1, v1u2, v3u3, v5u5}，如圖（ b） 中的紅邊。 ( 3 ) 取 X的非飽和點(diǎn) v4。 從 v4出發(fā)重復(fù)（ 2）的過程得 M可擴(kuò)路 Γ= v4u5v5u4 ( 4 ) X已無非飽和點(diǎn)，故結(jié)束。 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） 中紅邊。 二、最優(yōu)匹配 工作安排問題未考慮每人做某項(xiàng)工作的效率。若要求考慮效率，并問 “ 如何安排使效率最大 ” ，這稱為 最優(yōu)安排問題 。最優(yōu)安排的圖論模型是在賦權(quán)偶圖中尋找 具有最大權(quán)的匹配 ， 稱為 最優(yōu)匹配 。 167。 匹配在矩陣?yán)碚撝械膽?yīng)用 定理 16 v階方陣 M = (aij) 的行列式展開式中每一項(xiàng)均為零的充要條件是存在 n≤v，使 M 有一個(gè) n (vn+1) 階的子矩陣，它的所有的元素均為零。 證明 作一個(gè)具有二分類 (X , Y) 的偶圖 G，其中 X = {x1,x2,…, xv} ， Y = {y1,y2,…, yv}， xi 與 yj 鄰接當(dāng)且僅當(dāng)在 M 中 aij≠0。 021 21 ?? vvjjj aaa ?則 . ,{21 211 jj yxyxE ? )(}, GEyx vjv ??這樣 , 若在行列式 det M 中有一項(xiàng) 因 (j1, j2, … , jv) 是 (1, 2, … , v) 的一個(gè)排列，故 E1是一個(gè)完美匹配。 Hall定理表明不存在這樣的完美匹配當(dāng)且僅當(dāng)存在 X的一個(gè)子集 S，使 |N(S)|≤|S|1, 設(shè) |S| = n。這對(duì)應(yīng) M中有n行，這 n行中至多只有 n－ 1列中有非零元，而在其余的 (vn+1) 列中每個(gè)元均為零。于是 M有一個(gè) n (vn+1)階的零子矩陣。 例 1 在 5階方陣 2 0 1 0 10 0 4 0 00 0 3 7 01 1 0 5 60 0 0 8 0M?????????????中，第 2,3,5行和第 1,2,5列導(dǎo)出了一個(gè) 3階零矩陣。取 n=3， vn+1=3 ，故由定理 16知 det M 的每一項(xiàng)均為零。 事實(shí)上，從矩陣 M對(duì)應(yīng)的偶圖 G中（右圖），若取 S= {x2, x3, x5}，則 N (S)= {y3, y4}， 顯然 |S||N(S)| ，故 G沒有完美匹配，因而 det M 的展式中每項(xiàng)均為 0。 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)行證明。 設(shè) G=(n, m)是連通圖。令 vl， v2， …,v k,vk+1,…,v 2k是 G的所有奇度點(diǎn)。 在 vi與 vi+k間連新邊 ei得圖 G*（ 1≦i≦k). 則 G*是歐拉圖，因此，由 Fleury算法得歐拉環(huán)游 C. 在 C中刪去 ei （ 1≦ i≦ k).得 k條邊不重的跡 Qi （ 1≦ i≦ k): 12( ) ( ) ( ) ( )kE G E Q E Q E Q?章 4習(xí) 9 ， 設(shè) G是非平凡的歐拉圖，且 v ∈ V(G)。證明： G的每條具有起點(diǎn) v的跡都能擴(kuò)展成 G的歐拉環(huán)游當(dāng)且僅當(dāng)Gv是森林。 證明：“必要性” 若不然，則 Gv有圈 C。 考慮 G1=GE(G)的含有頂點(diǎn) v的分支 H。 由于 G是非平凡歐拉圖，所以 G1的每個(gè)頂點(diǎn)度數(shù)為偶數(shù)，從而， H是歐拉圖。 H是歐拉圖，所以存在歐拉環(huán)游 T. 對(duì)于 T，把它看成 v為起點(diǎn)和終點(diǎn)的一條歐拉跡，顯然不能擴(kuò)充為 G的歐拉環(huán)游。這與條件矛盾！ “充分性” 若不然，設(shè) Q=(v, w)是 G的一條不能擴(kuò)充為 G的歐拉環(huán)游的最長跡，顯然 v = w,且 Q包含了與 v關(guān)聯(lián)的所有邊。即 Q是一條閉跡。 于是， Gv包含 GQ且 GQ的每個(gè)頂點(diǎn)度數(shù)為偶數(shù) . 于是， GQ的非平凡分支是歐拉圖，說明有圈，即 Gv有圈，這與條件矛盾 . 章 5習(xí) 2 (1) 證明：每個(gè) k方體都有完美匹配 (k大于等于 2) (2) 求 K2n和 Kn,n中不同的完美匹配的個(gè)數(shù)。 (1) 證明一：證明每個(gè) k方體都是 k正則偶圖。 事實(shí)上，由 k方體的構(gòu)造： k方體有 2k個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)可以用長度為 k的二進(jìn)制碼來表示，兩個(gè)頂點(diǎn)連線當(dāng)且僅當(dāng)代表兩個(gè)頂點(diǎn)的二進(jìn)制碼只有一位坐標(biāo)不同。 如果我們劃分 k方體的 2k個(gè)頂點(diǎn)，把坐標(biāo)之和為偶數(shù)的頂點(diǎn)歸入 X，否則歸入 Y。顯然， X中頂點(diǎn)互不鄰接， Y中頂點(diǎn)也如此。所以 k方體是偶圖。 又不難知道 k方體的每個(gè)頂點(diǎn)度數(shù)為 k,所以 k方體是 k正則偶圖。 由推論： k方體存在完美匹配。 證明二：直接在 k方體中找出完美匹配。 設(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是完美匹配。 (2) 我們用歸納法求 K2n和 Kn,n中不同的完美匹配的個(gè)數(shù)。 K2n的任意一個(gè)頂點(diǎn)有 2n1中不同的方法被匹配。所以 K2n的不同完美匹配個(gè)數(shù)等于 (2n1)K2n2,如此推下去，可以歸納出K2n的不同完美匹配個(gè)數(shù)為： (2n1)!! 同樣的推導(dǎo)方法可歸納出 K n, n的不同完美匹配個(gè)數(shù)為： (n)! 章 5習(xí) 3，證明樹至多存在一個(gè)完美匹配。 證明：若不然，設(shè) M1與 M2是樹 T的兩個(gè)不同的完美匹配，那么 M1ΔM2≠Φ,且 T[M1ΔM2]每個(gè)頂點(diǎn)度數(shù)為 2，即它存在圈，于是推出 T中有圈，矛盾。