【正文】 ()( ) ( )()lll u a u Sl u l u a u Tl u o the r????? ? ???? 這樣 就可以 確定 新的 可行 頂標(biāo) 。 (5)若 y為 M飽和點(diǎn)轉(zhuǎn) (6),否則作求一條從 x到 y的 M可增廣路P,置 M=M?P,轉(zhuǎn) (2) (6)由于 y是 M飽和點(diǎn) ,故 M中有一邊 {y,u},置 S=S?{u}, T=T?{y},轉(zhuǎn) (4). 例 1 如圖 G所示， V1={x1,x2,x3,x4,x5}，V2={y1,y2,y3,y4,y5}，試求圖 G的最大匹配。 (3)在 V1中找一非 M飽和點(diǎn) x,置 S={x},T=?。 P是 G中以 x為端點(diǎn)的 M可增廣路 ,與(a)矛盾 . (b)?(c)任取 y?NG(S)?V2,則存在 u?S=H ?V1和邊 e?E(G) 使 ?G(e)={u,y}.若 u=x,顯然有 y? u?x,則 G中存在以 x和 u為端點(diǎn)的交錯路 x是唯一非 M飽和點(diǎn) ,所以 u為 M飽和點(diǎn) .若 P不含 y,則 e? H的定義知 ,y ? H?V2=T,所以NG(S)?T,再由 (1),T= NG(S). 顯然 y?T(交錯路中不可能含有兩個非 M飽和點(diǎn) ),與 T=NG(S)矛盾 .若 y?S,則顯然有 ?T?=?S? . 所以 G中不存在以 x為端點(diǎn)的 M可增廣路 . (3) (c)?(a)反設(shè) G中存在以 x為端點(diǎn)的 M可增廣路 ,則 G中至少還存在一個異于 x的非 M飽和點(diǎn) y,若 y?S,則 y?T ? NG(S), 匈牙利算法 基本思想 :設(shè) G是具有二部劃分 (V1,V2)的二分圖 ,從圖 G的任意匹配 M開始 .若 M飽和 V1,則 M是 G的匹配 .若 M不能飽和V1,則在 V1中選擇一個非 M飽和點(diǎn) x,若 G中存在以 x為起點(diǎn)的 M可增廣路 P,則 M’=M?P就是比 M更大的匹配 ,利用 M’代替 M,并重復(fù)這個過程 .若 G中不存在以 x為起點(diǎn)的 M可增廣路 ,則令 H是根在 x的 M交錯子圖的頂點(diǎn)集 ,并令S=H?V1,T=H?V2, 由定理 1,T=NG(S),且 G中不存在以 x為起點(diǎn)的 M可增廣路 ,此時 稱 x為檢驗(yàn)過的非 M飽和點(diǎn) .對 V1中其它未檢驗(yàn)過的非 M飽和點(diǎn)重復(fù)該過程 ,直到 V1中的所有非 M飽和點(diǎn)全部檢驗(yàn)過為止 .當(dāng)整個過程結(jié)束時 ,由于 G中不存在 M可增廣路 ,從而 M為 G的最大匹配 . 匈牙利算法步驟 : 設(shè) G是具有二部劃分 (V1,V2)的二分圖 . (1)任給初始匹配 M。 (b)x是 H中唯一的非 M飽和點(diǎn) 。 G中由起點(diǎn)為 x的 M交錯路所能連接的頂點(diǎn)集所導(dǎo)出的 G的導(dǎo)出子圖 稱為根在 x的 M交錯子圖 . 定理 1. 設(shè) M是具有二部劃分 (V1,V2)的二分圖 G的匹配 , x?V1是非 M飽和點(diǎn) ,H是 G中根在 x的 M交錯子圖的頂點(diǎn) 集 S=H?V1,T=H?V2,則 : (1)T?NG(S)。 (2)匹配的定義與邊的方向無關(guān) ,故匹配是針對無向圖而言 . (3)圖 G的邊不交匹配的最小數(shù)目即為 G的邊色數(shù) . 定義 3.(可增廣路 ):設(shè) M是圖 G的匹配 ,P是 G的一條路 ,且在 P中 ,M的邊和 E(G)M的邊交替出現(xiàn) ,則稱 P是 G的一條交錯路 .若 M交錯路 P的兩個端點(diǎn)為 M非飽和點(diǎn) ,則稱 P為 M可增廣路 . 例 G的一條交錯路和一條可增廣路 . 6 2 3 4 1 5 8 7 匹配的幾個性質(zhì)定理 定理 M1和 M2是圖 G的兩個不同匹配 ,由 M1?M2導(dǎo)出的 G 的邊導(dǎo)出子圖記作 H,則 H的任意連通分支是下列情況之 一 :(1)邊在 M1和 M2中交錯出現(xiàn)的偶圈 . (2)邊在 M1和 M2中交錯出現(xiàn)的路 . 證明 :記 H= M1?M2,因?yàn)?H是邊導(dǎo)出子圖 ,所以 ?(H)≥ 于 M1和 M2是圖 G的兩個不同匹配 ,所以 H的任意頂點(diǎn) x至多 與一條 M1的邊關(guān)聯(lián) ,同時也至多與一條 M2的邊關(guān)聯(lián) ,所以 Deg(x)≤2,所以 ? ≤2,故 H的每個連通分支或者是一條路 或者是一個圈 .據(jù)匹配的定義 ,H的任意兩條鄰接邊一定分 別屬于不同的匹配 M1和 M2,從而每條路或者圈的邊交錯 地屬于 M1和 M2且每個圈是偶圈 . 定理 G的最大匹配 ,當(dāng)且僅當(dāng) G中不存在 M可增廣路 . 證明 :(?)假設(shè)存在 M可增廣路 P,則 M’=M?P是 G的一個新的匹配 ,且 |M’|＝ |M|＋ 1|M|,矛盾 . (?)若 M不是 G的最大匹配 ,則存在匹配 M’,使得 |M’||M|,作H=M’?M,由定理 1,H的任意邊導(dǎo)出子圖 Q是下列兩種情況之一 :(1)交錯偶圈 :Q中每個結(jié)點(diǎn)度數(shù)為 2.(2)交錯路 .Q中除端點(diǎn)外 ,其余結(jié)點(diǎn)度數(shù)均為 2. 因?yàn)?|M’||M|,故 |E(H)?M’||E(H)?M|,因而 H中必有一條起始于 M’且終止于 M’的連通分支 P,故 P是 M可增廣路 ,矛盾 ,所以命題正確 . 定義 :NG(S):設(shè) S是圖 G的任意頂點(diǎn)子集 ,G中與 S的頂點(diǎn)鄰接的所有頂點(diǎn)的集合 ,稱為 S的鄰集 ,記做 NG(S). 定理 3(Hall定理 ,1935)設(shè) G是有二部劃分 (V1,V2)的二分圖 , 則 G含有飽和 V1的每個頂點(diǎn)的匹配 M的 充要條件 是 ,對?S?V1,有 ?N(S)???S?. 證明 :(?)對 ?S?V1,匹配 M將 S中的每個頂點(diǎn)與 N(S)中的頂 點(diǎn)配對 ,所以 ?N(S)???S?. (?)當(dāng) 對 ?S?V1,有 ?N(S)???S?時 .可按下述方法作出飽和 V1的匹配 M. 先作一初始匹配 M1,若已經(jīng)飽和 V1,定理得證 .否則 ,V1中至少有一非飽和點(diǎn) x1,檢查以 x1為起點(diǎn) ,終點(diǎn)在 V2中的交錯路 .考慮下面兩種情形 : (1)不存在任何一條交錯路可以到達(dá) V2的非飽和點(diǎn) .此時從 X1開始的一切交錯路的終點(diǎn)還是在 V1中 .故存在 A?V1,使得 ?N(A)??A?,矛盾 . (2)存在一條以 x1為起點(diǎn) ,終點(diǎn)為 V2的非飽和點(diǎn)的交錯路 P,顯然 P是可增廣路 ,作新匹配 M2=M1?P,則M2飽和 x1,且 ?M2??M1?,因此 ,重復(fù)該過程就可以找到飽和 V1的全部頂點(diǎn)的匹配 M. 推論 1 具 有二部劃分 (V1,V2)的二分圖 G有完美匹配 ? ?V1?=?V2?,且 對 ?S?V1(或 V2),有 ?N(S)???S?. 證明 :必要性 .若 二分圖 G有完美匹配 ,由定理 3有 ?V2=N(V1)???V1?,即 ?V2???V1?,同理 ?V1???V2?,因此?V1?=?V2?. 充分性 :因?yàn)?對 ?S?V1,有 ?N(S)???S?,由定理 1,G中存在飽和 V1的每個頂點(diǎn)匹配 M,又 G是二分圖 ,故匹配 M的每一邊的兩個端點(diǎn)分別屬于 V1和 V2,據(jù) ?V1?=?V2?即知 M飽和V2,所以 M為完美匹配 . 推論 2. 設(shè) G是 k(0)正則二分圖 ,則 G有完美匹配 . 證明 :因?yàn)?G是二部劃分 (V1,V2)的 k正則二分圖 ,故 k?V1?=E(G)=k?V2? 又 k?0,所以 ?V1?=?V2?.任取 S?V1,并用 E1和 E2分別表示 G中與 S和 N(S)中關(guān)聯(lián)的邊集 ,則 E1?E2,則 k?N(S)?=?E2???E1?=k?S?即 ?N(S)???S?,? S?V1, 由定理 3可知 ,G有飽和 V1的匹配 M,再據(jù) ?V1?=?V2?和推 論 1即知 M是完美匹配 . 推論 3. 設(shè) G是二部劃分 (V1,V2)的簡單二分圖 ,且 ?V1?=?V2?=n,若 ?(G)?n/2,則 G有完美匹配 . 證明 :?S?V1,(1)若 S中至少有兩個頂點(diǎn) ,由 ?(G)?n/2可知 ?N(S)??n/2+n/2=n=?V1???S? (2)若 S中只有一個頂點(diǎn) ,由 ?(G)?n/2可知 ?N(S)??n/2, 所以 ?N(S)??1??S?=1. 綜上 ,對 ?S?V1,均有 ?N(S)???S?,所以 G中有完美匹配 . 定理 4. G有完美匹配 ?O(GS)??S?,?S?V(G),其中 O(GS)是 GS的奇數(shù)階連通分支數(shù)目 .(不證 ) 例 n張紙牌 ,每張紙牌的正反兩面都寫上 1,2,…n 的某一個數(shù) .證明 :如果每個數(shù)字恰好出現(xiàn)兩次 ,則這些紙牌一定可以這樣攤開 ,使朝上的面中 1,2,…n 都出現(xiàn) . 證明 :作一個二分圖 G=V1,V2,E,其中V1={1,2,…,n},V 2={y1,y2,…,y n}表示這 n張紙牌 .i與 yi之間連接的邊數(shù) 等于 數(shù) i在紙牌 yj中出現(xiàn)的次數(shù) ,這樣得到的圖G是一個 2正則二分圖 ,因此圖 G中有完美匹配 ,設(shè)為 M={1yi1,2yi2,…,ny in} 則只要把紙牌 yi1中的 1朝上 ,yi2中的 2朝上 ,…,y in的 n朝上 , 這樣攤開 ,這樣攤開的紙牌就能使上面中 1,2,…,n 都出現(xiàn) . 例 6種不同顏色的紗布織成的雙色