【正文】 ω (CS) ≤ | S | （ *） 而 C 是 G 的 生成子圖，又有 ω (GS) ≤ ω (C S ) 所以 ω (G S )≤ | S | 定理 5 若 G是 H圖，則對于 V的每個非空真子集 S ， 均有 ω(GS)≤|S | () 依據(jù)定理 4可判斷下圖（ a） 不是哈密爾頓圖，這是因若取 S = {v }， 有 ω (G S ) =2 1 = | S | （ a） v 可驗證彼得森圖（上圖（ b） 所示）不是哈密爾頓圖，但滿足式（ *）式。 (b) 引理 1 設(shè) G是簡單圖， u和 v是 G中不鄰接的頂點，且適合 d(u) + d(v)≥n 則 G是 H圖的充要條件是 G + uv為 H圖。 充分性 ： 設(shè) G + uv是 H圖。 如果 G + uv的 H 圈中 含有 uv 邊，不妨設(shè) H圈為 C = uvv3v4… vnu。從而 )(1 udG)(1 udG這與已知條件相矛盾。 (v) ≤ (n1) – ( 2) = n dG(u) 1Gd )(1 udGdG(v) d(u) + d(v) n 定義 1 在 n階簡單圖 G中，若對 d(u)+d(v)≥ n的任何一對點 u和 v均有 u adj v， 則稱 G是 閉圖 。 11( ) ( )GGd u d v n?? nvdud GG ?? )()( 22由 G1和 G2是閉圖， u和 v在 G1和 G2中都鄰接，故 u和 v在G中也鄰接，從而 G是閉圖。例如 G1 G2 G1∪ G2 G1∩G2 定義 2 若一個與 G 有相同點集的閉圖 ，使 G ? ，且對異于 的任何圖 H， 若有 G ? H ? ，則 H不是閉圖，則稱 是 G的閉包，即 G的閉包是包含 G的極小閉圖。 例 下圖給出了 6個頂點的圖的閉包的構(gòu)造過程。 引理 3 圖 G的閉包是唯一的。則由 G? G? ,得 1?G2?G2?G而 ∩ 是閉圖 (引理 2) , 且 1?G 1?G2?G∩ ? , 1?G2?G2?G∩ ? , 故由 閉包的定義 1?G1?G? 2?G 2?G?∩ 1?G證明 如果 G是 H圖，顯然， 是 H圖。 ?G?G?G?G 如果 是 H圖，當(dāng) G= 時，結(jié)論成立；當(dāng) G≠ 時，必相繼存在若干條邊，使得 ?GG + e1 + e2 + … + ek = ( ) ( )d u d v n??其中 ei?G， (i =1,2,…, k)。 注 : 一個圖 G的閉包不一定是完全圖。 （ a） （ b） 推論 1 設(shè)是 n ≥3的簡單圖。 ?G 推論 2 （ 1） 設(shè) G是 n ≥3的簡單圖。 (由此得定理 6) （ 2） 設(shè) G是 n ≥3的簡單圖，若 G中任何兩個不鄰接的點 u和 v均有 d(u) + d(v) ≥ n 則 G是 H圖。因此，由推論 1，它是 H圖，其 H圈為 C =1234567891。 說明： 判斷一個圖是否哈密爾頓圖，往往要結(jié)合定義進行。 不是哈密爾頓圖， 因圖中二度頂點所 關(guān)聯(lián)的 8條邊（紅邊） 已構(gòu)成圈，而此圈不是 哈密爾頓圈。問如何安排路線使其能恰好訪問每個城鎮(zhèn)一次且走過的總路程最短？這個問題稱為旅行售貨員問題 . 求最優(yōu)圈，目前還沒有一個理想的算法。 旅行售貨員問題 圖論模型 ：在賦權(quán)完全圖 G中求具有最小權(quán)的哈密爾頓圈，這個圈稱為 最優(yōu)圈 。 （ 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)。 Vj V2 V1 Vn Vj+1 Vj1 Vi Vi+1 例 3 求圖中（ a） 所示圖的最優(yōu)圈。 ∵ w (ca) + w (db) = 18+7 = 25 23 = w (cd) + w(ab) ∴ 取 C ‘ = b c d a b。 匹配 定義 設(shè) M是圖 G的邊子集，若任意的 e∈ M， e 都不是環(huán)，且屬于 M 的邊互不相鄰，則稱 M 為 G的一個 匹配 。 匹配還可分為 最大匹配 （含邊數(shù)最多的匹配）和 完美匹配 （ 圖中的點均為 M 飽和點的匹配 M ） 等類型。 v1 v2 v3 v4 v8 v5 v7 v6 例 1中的 M1 和 M2既不是最大匹配，也不是完美匹配，而 M3是最大匹配，也是完美匹配。 (2) 一個圖的最大匹配必存在，但完美匹配不一定存在。 設(shè) M 為圖 G的一個匹配 可看出：對 Г3 ， 若取 Г3中非 M 的邊再連同 M 的不在 Г3中的邊組成 M’， 則 M’ 的邊數(shù)比 M的邊數(shù)多，這表明 M 不是該圖的最大匹配。 M 可擴路： 起點與終點均為 M 非飽和點的 M交 錯 路 。 反之，假設(shè) M不是最大匹配 ，且令 M′是 G的最大匹配，則 | M′| |M| () 置 H = G[M△ M′]，這里 M△ M′表示 M和 M′的對稱差。他的 《 無限圖理論及其應(yīng)用 》 (1958) 是繼哥尼之后的圖論歷史上的第二本圖論專著。 1993年，他獲得組合與圖論領(lǐng)域頒發(fā)的歐拉獎?wù)?。在博弈領(lǐng)域，他引入了 Nash均衡之外的另一種均衡系統(tǒng)。 貝爾熱對中國的手工藝很感興趣。 H 的每個頂點在 H中具有的度是 1或 2。由（ ）式， M′包含的邊多于 M的邊，因而 H中必定有的一條路 P,其邊始于 M′且終止于 M′ ，因此 P的起點和終點在 H中被 M′所飽和，在圖 G中就是 M非飽和的。 167。 取 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的每個頂點的匹配當(dāng)且僅當(dāng) |N(S)|≥|S| （ ） 對所有 S ? X 成立 . 證明 假設(shè) G包含匹配 M，它飽和 X的每個頂點，并設(shè) S是 X的子集。 反之，假設(shè) G是滿足（ ）式的偶圖， M*是 G的最大匹配。 設(shè) u 是 X的一個 M* 非飽和點，并設(shè) Z={ v | v∈ V，且 v通過 M*交錯路與 u連接 } 置 S = Z∩X 和 T = Z∩Y （見圖） 由于 M*是最大匹配，從上節(jié)定理 1可知： u為 Z中唯一的 M*非飽和點 (否則將含 M * 可擴路 ) 。 又因 N(S)中每個頂點 v 均由一個 M*交錯路連接于 u，故 v∈ Z, 從而 v∈ T, 這表明 N(S ) ? T , 于是 有 T = N(S ) () 由（ ）式和（ ）式推出 |N(S )| = | T |= |S |1 |S | 這與假定（ ）式矛盾。 證明 設(shè) G是具有二分類 （ X, Y） 的 k正則偶圖 （ k0） 。 圖 G的一個覆蓋 : 指 V(G)的一個子集 K，使得 G的每條邊都至少有一個端點在 K 中。 (1) |M|≤| K |, 特別地 ,若 M*是最大匹配，且 是最小覆蓋 , 則 |M*|≤ () K~|~|K(2) 定理 4 設(shè) M是匹配， K是覆蓋，若 |M|＝ |K|，則 M是最大匹配，且 K是最小覆蓋。 K~K~(3) 定理 5（ Kǒnig， 哥尼， 1931） 偶圖中，最大匹配的邊數(shù)等于最小覆蓋的頂點數(shù)。置 S = Z∩X , T = Z∩Y。定義 = (X\S)∪ T（見圖）。nig ， 18841944))—— 第一本圖論教材 《 有限圖與無限圖理論 》 （ 1936年）的撰寫者。在 20多年時間里，它都是世界上唯一一本圖論著作。 哥尼早期學(xué)習(xí)拓?fù)鋵W(xué)，但對圖論興趣特別大。講課很有激情，吸引了很多優(yōu)秀學(xué)生轉(zhuǎn)向圖論研究。s ,Gallai, 。 則 G的每條邊必然至少有一個端點在 中，因為否則就存在一條邊，其一個端點在 S中，而另一個端點在 Y\T中，這與 N(S)＝ T相矛盾。并且顯然有 K~K~|M*|= |~|KK~由定理 4，是 最小覆蓋。證明：包含了一個（ 0,1）矩陣中所有 〝 1〞 的線的最小條數(shù)，等于具有性質(zhì) 〝 任意兩個 1都不在同一條線上 〞 的 〝 1