【文章內(nèi)容簡(jiǎn)介】 旅行售貨員問(wèn)題 圖論模型 ：在賦權(quán)完全圖 G中求具有最小權(quán)的哈密爾頓圈，這個(gè)圈稱為 最優(yōu)圈 。 一個(gè)可行解法： （ 1）任取 G 的一個(gè)哈密爾頓圈 C。 （ 2） 修改 C 為 Cij 使 Cij 比 C 優(yōu)，其方法為：設(shè) C = v1 v2… vn v1， 若存在整數(shù) i， j， 滿足 0 i+1j n，且 w (vivj) + w (v i+1v j+1) w (vi vi+1) + w (vj vj+1) 則 Cij = v1 v2… vi vj vj1… v i+1 v j+1 vj+2 … vnv1 比 C 優(yōu)。其中 C與 Cij的關(guān)系如圖所示。 Vj V2 V1 Vn Vj+1 Vj1 Vi Vi+1 例 3 求圖中（ a） 所示圖的最優(yōu)圈。 解 任取一個(gè)哈密爾頓圈 C = bcadb， 如圖（ b）。 ∵ w (ca) + w (db) = 18+7 = 25 23 = w (cd) + w(ab) ∴ 取 C ‘ = b c d a b。 (a) b a c d 10 18 11 7 14 12 (b) a b d c 10 11 12 14 18 7 第五章 匹配與因子分解 167。 匹配 定義 設(shè) M是圖 G的邊子集，若任意的 e∈ M， e 都不是環(huán)，且屬于 M 的邊互不相鄰，則稱 M 為 G的一個(gè) 匹配 。設(shè) M 為 G 的一個(gè)匹配，對(duì) v∈ V(G)， 若 v 是 M 中某邊的一個(gè)端點(diǎn)，則稱 v 為 M 飽和點(diǎn) ，否則稱為 M 非飽和點(diǎn) 。 匹配還可分為 最大匹配 （含邊數(shù)最多的匹配）和 完美匹配 （ 圖中的點(diǎn)均為 M 飽和點(diǎn)的匹配 M ） 等類型。 對(duì) M2， 點(diǎn) v1是的飽和點(diǎn)，點(diǎn) v2是非飽和點(diǎn)。 v1 v2 v3 v4 v8 v5 v7 v6 例 1中的 M1 和 M2既不是最大匹配，也不是完美匹配，而 M3是最大匹配，也是完美匹配。 例 1 設(shè)圖 G 為 : G的匹配有： M1 = {v1v8} M2 = {v1v3， v8v4， v7v5} M3 = {v1v2， v8v3， v7v4， v6v5} 等等 關(guān)系： (1) 完美匹配必是最大匹配，而最大匹 配不一定是完美匹配。 (2) 一個(gè)圖的最大匹配必存在，但完美匹配不一定存在。 (3) 圖 G 存在完美匹配的一個(gè)必要條件 是 G 的點(diǎn)數(shù)為偶。 設(shè) M 為圖 G的一個(gè)匹配 可看出：對(duì) Г3 ， 若取 Г3中非 M 的邊再連同 M 的不在 Г3中的邊組成 M’， 則 M’ 的邊數(shù)比 M的邊數(shù)多，這表明 M 不是該圖的最大匹配。 M 交 錯(cuò) 路： G 中由 M中的邊與非 M 中的邊交替組成的路。 M 可擴(kuò)路： 起點(diǎn)與終點(diǎn)均為 M 非飽和點(diǎn)的 M交 錯(cuò) 路 。 例如， 取 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就 不是最大匹配。 反之，假設(shè) M不是最大匹配 ，且令 M′是 G的最大匹配，則 | M′| |M| () 置 H = G[M△ M′]，這里 M△ M′表示 M和 M′的對(duì)稱差。 貝爾熱 (19262022) 法國(guó)著名數(shù)學(xué)家。他的 《 無(wú)限圖理論及其應(yīng)用 》 (1958) 是繼哥尼之后的圖論歷史上的第二本圖論專著。他不僅在圖論領(lǐng)域做出了許多貢獻(xiàn)，而且四處奔波傳播圖論，推動(dòng)了圖論的普及和發(fā)展。 1993年，他獲得組合與圖論領(lǐng)域頒發(fā)的歐拉獎(jiǎng)?wù)隆? 貝爾熱在博弈論、拓?fù)鋵W(xué)領(lǐng)域里也有杰出貢獻(xiàn)。在博弈領(lǐng)域，他引入了 Nash均衡之外的另一種均衡系統(tǒng)。 Nash的生活被改編成電影 《 美麗的心靈 》 ，獲 02年奧斯卡金像獎(jiǎng)。 貝爾熱對(duì)中國(guó)的手工藝很感興趣。他也是一位象棋高手，還創(chuàng)作過(guò)小說(shuō) 《 誰(shuí)殺害了 Densmore公爵 》 。 H 的每個(gè)頂點(diǎn)在 H中具有的度是 1或 2。因?yàn)樗疃嘀荒芎?M的一條邊以及 M′的一條邊相關(guān)聯(lián)，因此 H 的每個(gè)分支或是由 M和 M′中的邊交錯(cuò)組成的偶圈，或是由 M和 M′中的邊交錯(cuò)組成的路。由（ ）式， M′包含的邊多于 M的邊，因而 H中必定有的一條路 P,其邊始于 M′且終止于 M′ ，因此 P的起點(diǎn)和終點(diǎn)在 H中被 M′所飽和，在圖 G中就是 M非飽和的。于是 P是 G的一條 M可擴(kuò)路 。 167。 偶圖的匹配與覆蓋 取圖 G 的一個(gè)頂點(diǎn)子集 S， 令 N (S) = { v | 存在 u∈ S， 且 v與 u 相鄰 } 稱 N (S) 為 S 的 鄰集 。 取 S = {v1, v2}， 則 N (S) = {v8, v3,v1, v2} v1 v2 v3 v4 v8 v5 v7 v6 例如圖 中 定理 2（ Hall， 1935） 設(shè) G為具有二分類（ X, Y）的偶圖，則G包含飽和 X的每個(gè)頂點(diǎn)的匹配當(dāng)且僅當(dāng) |N(S)|≥|S| （ ） 對(duì)所有 S ? X 成立 . 證明 假設(shè) G包含匹配 M，它飽和 X的每個(gè)頂點(diǎn)，并設(shè) S是 X的子集。由于 S的頂點(diǎn)在 M 下和 N(S)中的相異頂點(diǎn)配對(duì)，顯然有 |N(S)|≥|S| 。 反之，假設(shè) G是滿足（ ）式的偶圖， M*是 G的最大匹配。若 M*不飽和 X的所有頂點(diǎn)，我們則將有如下矛盾。 設(shè) u 是 X的一個(gè) M* 非飽和點(diǎn)，并設(shè) Z={ v | v∈ V，且 v通過(guò) M*交錯(cuò)路與 u連接 } 置 S = Z∩X 和 T = Z∩Y （見(jiàn)圖） 由于 M*是最大匹配，從上節(jié)定理 1可知： u為 Z中唯一的 M*非飽和點(diǎn) (否則將含 M * 可擴(kuò)路 ) 。且任意一對(duì)配對(duì)點(diǎn) v和 w,若v∈ S,則必 w∈ T, 反之亦然 . 因此 S u T=N (S) | T |= |S |1 （ ） 而且 T ? N(S ) 。 又因 N(S)中每個(gè)頂點(diǎn) v 均由一個(gè) M*交錯(cuò)路連接于 u，故 v∈ Z, 從而 v∈ T, 這表明 N(S ) ? T , 于是 有 T = N(S ) () 由（ ）式和（ ）式推出 |N(S )| = | T |= |S |1 |S | 這與假定（ ）式矛盾。 所以 M*飽和 X的所有頂點(diǎn) . 推論 若 G是 k正則偶圖（ k0），則 G有完美匹配。 證明 設(shè) G是具有二分類 （ X, Y） 的 k正則偶圖 （ k0） 。 首先有 |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是完美匹配。 圖 G的一個(gè)覆蓋 : 指 V(G)的一個(gè)子集 K，使得 G的每條邊都至少有一個(gè)端點(diǎn)在 K 中。 G的最小覆蓋 : G中點(diǎn)數(shù)最少的覆蓋 一個(gè)覆蓋 一個(gè)最小覆蓋 例 匹配與覆蓋的關(guān)系 : 設(shè) K是 G的覆蓋， M是 G的匹配 , 則有 理由 : K至少包含 M中每條邊的一個(gè)端點(diǎn)。 (1) |M|≤| K |, 特別地 ,若 M*是最大匹配，且 是最小覆蓋 , 則 |M*|≤ () K~|~|K(2) 定理 4 設(shè) M是匹配， K是覆蓋，若 |M|＝ |K|，則 M是最大匹配，且 K是最小覆蓋。 K~證明 設(shè) M*是最大匹配 , 是最小覆蓋，則由（ ）式， |M|≤|M*|≤| |≤|K| 由于 |M|＝ |K |，所以 |M| = |M*|, | | = |K|。 K~K~(3) 定理 5（ Kǒnig， 哥尼， 1931） 偶圖中，最大匹配的邊數(shù)等于最小覆蓋的頂點(diǎn)數(shù)。 證明 設(shè) G 是具有二分類（ X, Y）的偶圖， M*是 G的最大匹配，用 U 表示 X 中的 M* 非飽和頂點(diǎn)的集，用 Z 表示由 M 交錯(cuò)路連接到 U 中頂點(diǎn)的所有頂點(diǎn)的集。置 S = Z∩X , T = Z∩Y。 類似于定理 2的證明，可知 T中的每個(gè)頂點(diǎn)都是 M*飽和的，并且 N(S)＝ T。定義 = (X\S)∪ T（見(jiàn)圖）。 K~S U T=N (S) X \S 哥尼 (K214。nig ， 18841944))—— 第一本圖論教材 《 有限圖與無(wú)限圖理論 》 （ 1936年）的撰寫(xiě)者。 該書(shū)對(duì)青年學(xué)者產(chǎn)生