【正文】 |M|≤|M*|≤| |≤|K| 由于 |M|＝ |K |，所以 |M| = |M*|, | | = |K|。 G的最小覆蓋 : G中點(diǎn)數(shù)最少的覆蓋 一個(gè)覆蓋 一個(gè)最小覆蓋 例 匹配與覆蓋的關(guān)系 : 設(shè) K是 G的覆蓋， M是 G的匹配 , 則有 理由 : K至少包含 M中每條邊的一個(gè)端點(diǎn)。 首先有 |X| = |Y| (習(xí)題 1的 9). 任取 X的一個(gè)子集 S ， 令 E1={e | e∈ E,并且 e 與 S 中的頂點(diǎn)關(guān)聯(lián) } E2={e | e∈ E,并且 e 與 N(S) 中的頂點(diǎn)關(guān)聯(lián) } 因與 S 中的頂點(diǎn)關(guān)聯(lián)的邊必與 N(S) 中的頂點(diǎn)關(guān)聯(lián)，所以 E1 ? E2 ? ? 21k N S E E k S? ? ?? ?N S S?再根據(jù)定理 2，可知 G有一個(gè)飽和 X的每個(gè)頂點(diǎn)的匹配 M，由于 |X| = |Y|，所以 M是完美匹配。 所以 M*飽和 X的所有頂點(diǎn) . 推論 若 G是 k正則偶圖（ k0），則 G有完美匹配。且任意一對(duì)配對(duì)點(diǎn) v和 w,若v∈ S,則必 w∈ T, 反之亦然 . 因此 S u T=N (S) | T |= |S |1 （ ） 而且 T ? N(S ) 。若 M*不飽和 X的所有頂點(diǎn)，我們則將有如下矛盾。由于 S的頂點(diǎn)在 M 下和 N(S)中的相異頂點(diǎn)配對(duì)，顯然有 |N(S)|≥|S| 。 偶圖的匹配與覆蓋 取圖 G 的一個(gè)頂點(diǎn)子集 S， 令 N (S) = { v | 存在 u∈ S， 且 v與 u 相鄰 } 稱 N (S) 為 S 的 鄰集 。于是 P是 G的一條 M可擴(kuò)路 。因?yàn)樗疃嘀荒芎?M的一條邊以及 M′的一條邊相關(guān)聯(lián)，因此 H 的每個(gè)分支或是由 M和 M′中的邊交錯(cuò)組成的偶圈，或是由 M和 M′中的邊交錯(cuò)組成的路。他也是一位象棋高手，還創(chuàng)作過(guò)小說(shuō) 《 誰(shuí)殺害了 Densmore公爵 》 。 Nash的生活被改編成電影 《 美麗的心靈 》 ，獲 02年奧斯卡金像獎(jiǎng)。 貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動(dòng)了圖論的普及和發(fā)展。 貝爾熱 (19262022) 法國(guó)著名數(shù)學(xué)家。 例如， 取 M = {紅邊 } Г1 Г2 Г3 M 交 錯(cuò) 路 M 可擴(kuò)路 定理 1（ Berge， 貝爾熱， 1957） G 的匹配 M是最大匹配當(dāng)且僅當(dāng) G 不含 M 可擴(kuò)路 . （ 等價(jià)于： M不 是最大匹配當(dāng)且僅當(dāng) G 含 M 可擴(kuò)路 ） 證明 設(shè) M是 G的匹配，并假設(shè) G 包 含 M可擴(kuò)充路 v0v1…v 2m+1 , 定義 M′? E 為 M′= (M\{ v1v2, v3v4,…,v 2m1 v2m})∪ { v0v1, v2v3,…,v 2m v2m+1} 則 M′是 G的匹配，且 | M′| = |M| +1，因而 M就 不是最大匹配。 M 交 錯(cuò) 路： G 中由 M中的邊與非 M 中的邊交替組成的路。 (3) 圖 G 存在完美匹配的一個(gè)必要條件 是 G 的點(diǎn)數(shù)為偶。 例 1 設(shè)圖 G 為 : G的匹配有： M1 = {v1v8} M2 = {v1v3， v8v4， v7v5} M3 = {v1v2， v8v3， v7v4， v6v5} 等等 關(guān)系： (1) 完美匹配必是最大匹配，而最大匹 配不一定是完美匹配。 對(duì) M2， 點(diǎn) v1是的飽和點(diǎn)，點(diǎn) v2是非飽和點(diǎn)。設(shè) M 為 G 的一個(gè)匹配，對(duì) v∈ V(G)， 若 v 是 M 中某邊的一個(gè)端點(diǎn)，則稱 v 為 M 飽和點(diǎn) ，否則稱為 M 非飽和點(diǎn) 。 (a) b a c d 10 18 11 7 14 12 (b) a b d c 10 11 12 14 18 7 第五章 匹配與因子分解 167。 解 任取一個(gè)哈密爾頓圈 C = bcadb， 如圖（ b）。其中 C與 Cij的關(guān)系如圖所示。 一個(gè)可行解法： （ 1）任取 G 的一個(gè)哈密爾頓圈 C。 167。 問(wèn)題 ： 一個(gè)旅行售貨員想訪問(wèn)若干城市（假定各城鎮(zhèn)之間均有路可通），然后返回。由定義知：一個(gè)圖若有度為 1的頂點(diǎn)，一定不是哈密爾頓圖，只可能有哈密爾頓路；若圖是哈密爾頓圖，則圖中 2度頂點(diǎn)關(guān)聯(lián)的邊必屬于所有哈密爾頓圈；一個(gè)頂點(diǎn)關(guān)聯(lián)的邊再多，一個(gè)哈密爾頓圈只能用其兩條邊。 而僅僅改動(dòng)一條邊的一個(gè)端點(diǎn)所得之圖 H圖。 6 5 3 4 2 9 7 8 1 例 右圖的閉包是完全圖。若 G中每個(gè)點(diǎn)的度d(v) ≥n/2， 則 G是 H圖。若 是完全圖，則 G是 H圖。比如下圖中（ a）、（ b） 兩個(gè)均不是完全圖，但它們卻是自己的閉包。 根據(jù)閉包的定義，對(duì) 中邊ek的端點(diǎn) u和 v有 ?G 因?yàn)?G +e1 +e2 +…+ ek是 H圖，由引理 1知 G+e1+e2+…+ ek1 是 H圖，反復(fù)應(yīng)用引理 1可知 G是 H圖。 ?G定理 7 (Bondy 1969) 一個(gè)簡(jiǎn)單圖 G是 H圖的充要條件為它的閉包 是 H圖。 2?GG? ∩ 1?G2?G1?G證明 如果 和 是 G 的兩個(gè)閉包。 故唯一。 ?G?G?G?G?G圖的閉包的構(gòu)造方法 : 將圖中度數(shù)之和至少是圖的頂點(diǎn)個(gè)數(shù)的非鄰接頂點(diǎn)對(duì) 遞歸地 連接起來(lái)，直到不再有這樣的頂點(diǎn)對(duì)存在時(shí)為止。 )(1 wdG )(2 wdG證明 因?qū)θ魏?w∈ V，有 dG(w)≤ , dG(w)≤ ( ) ( )GGd u d v n?? , 可得 故由 注 : 閉圖的并不一定是閉圖。 引理 2 若 G1和 G2是同一個(gè)點(diǎn)集 V 的兩個(gè)閉圖，則 G = G1∩G2是閉圖。故在假設(shè)的 dG(u) + dG(v) ≥ n的條件下，一定存在上述圖示那樣的 i ， 使 G中存在一個(gè)H 圈，所以 G為 H圖。 當(dāng) G1= G + uv時(shí)，有 1 ( ) ( ) 1GGd u d u?? 1 ( ) ( ) 1GGd v d v??故有 11( ) ( ) ( ) ( ) 2 2G G G Gd u d v d u d v n? ? ? ? ? ? 若有 i (3≤i≤n1) 使 u adj vi， v adj vi+1 (如圖 )， 則 G 中有一個(gè) H圈 C1 = uvivi1… v3 v vi+1vi+2… vn u 即 G是 H 圖 vi1 vi2 v3 vi vi+1 vi+2 vi+3 v u vn 若不存在這樣的 i ， 因 v3, v4,…, vn1中有 2 個(gè)點(diǎn)與 u鄰接，故 v4, v5, …, vn中就有 2 個(gè)點(diǎn)不能與v 鄰接。如果 G + uv的 H圈 不含 邊 uv，則由 G = (G+uv) uv 知 G中有一個(gè) H圈。 證明 必要性 ： 若 G是 H圖，則顯然 G + uv也是 H圖。這表明定理 5給出的條件只是圖 G 是哈密爾頓圖的 必要條件而不是充分條件 。任取 V 中 非空子集 S ， 因 C 是 G 的 哈密爾頓圈含 G 的所有點(diǎn)，故 S 也是子圖 C 的 非空子集。Hamilton路也簡(jiǎn)稱 H路 。 (a) (b) (c) 167。 (b)中有色圈中重復(fù)邊的數(shù)目為 5，大于圈長(zhǎng) 8的一半，在這個(gè)圈上交換重復(fù)邊和不重復(fù)邊，得到 (c)。 算法復(fù)雜性分析 (2) 考查 G’的圈 , 若存在圈 C,其中重復(fù)邊的總長(zhǎng)大于圈長(zhǎng)的一半，則在圈 C上交換重復(fù)邊和不重復(fù)邊得圖 G”.重復(fù)這個(gè)過(guò)程 ,直到得到一個(gè)圖 G*,在 G*中沒(méi)有重復(fù)邊的總長(zhǎng)大于圈長(zhǎng)的一半的圈 . 不是 Euler圖求最優(yōu)環(huán)游的方法 (1) 用每條邊最多添一條邊的方法任意添一些重復(fù)邊使圖 G 成為一個(gè)歐拉多重圖 G’. (3) 用 Fleury算法求 G*的 Euler環(huán)游 . 例 圖 G如圖 (a)所示 (各邊權(quán)為 1),它有 10個(gè)奇度點(diǎn)。 為了在 G中求出一條起點(diǎn)為 e,終點(diǎn)為 g的歐拉跡，在 e和 g間添加一條平行邊 m a f e d c b i h g j m 用 Fleury算法求出歐拉環(huán)游為： emgcfabchbdhgdjiejge 所以：解為： egjeijdghdbhcbafcg 設(shè) G=(n, m)是歐拉圖 由 Fleury算法知：算法需要 m次循環(huán)； 算法中主要運(yùn)算是判斷： ，該判斷的時(shí)間復(fù)雜性是 n2數(shù)量級(jí)的。請(qǐng)找出從博物館 e進(jìn)入，經(jīng)過(guò)每個(gè)走廊恰好一次，最后從 g處離開(kāi)的路線。 例 可證， Fleury算法是一個(gè)好算法。 2. 假設(shè)跡 wi=v0e1v1… eivi已經(jīng)選定，那么按下述方法從 E \ {e1,e2,…, ei}中選取邊 ei+1：使 (1) ei+1和 vi相關(guān)聯(lián)； (2) 除非沒(méi)有別的邊可選擇，否則 ei+1 不是 G=G {e1,e2,…, ei}的割邊。 說(shuō)明 : (1) 若 G是 Euler圖，則 G的任何 Euler環(huán)游都是最優(yōu)環(huán)游 . (2) 若 G 不是 Euler圖，用添加重復(fù)邊以使 G成為歐拉圖 G* 的方法時(shí)，添加的重復(fù)邊具有的特征由定理 3給出 . 定理 3 若 W是圖 G中一條包含所有邊的閉通道，則 W在這樣的閉通道中具有最短的長(zhǎng)度的充要條件是： (1) 每一條邊最多重復(fù)經(jīng)過(guò)一次； (2) 在 G的每一個(gè)圈上，重復(fù)經(jīng)過(guò)的邊的數(shù)目不超過(guò)圈的長(zhǎng)度的一半 算法的思