【正文】 數(shù) ， 可 由 再 經(jīng) 關(guān) 聯(lián) 邊 到 ， 如此 下 去 ， 每 邊 僅 取 一 次 。 由 于 連 通 ， 必 定 可 以 到 達(dá) 另 一 個 奇 數(shù) 度 結(jié)點 停 下 ， 得 到 一 條 跡 。Gve v v v e vGLV1V2V3V4V574 歐拉圖與漢密爾頓圖 111112 1 2（ 2 ） 若 中 沒 有 奇 數(shù) 度 結(jié) 點 ， 則 從 任 一 結(jié) 點 出 發(fā) ， 用 上 述 方 法 必 定可 以 回 到 此 結(jié) 點 ， 得 到 一 條 閉 跡 。 若 包 含 了 中 的 所 有 邊 ， 則 就 是 歐 拉 路 。 否 則 ， 去 掉 得 到 子 圖 ， 則 中 每 個 結(jié) 點 的 度 數(shù) 仍 為 偶 數(shù) ，且 中 至 少 有 一 個 結(jié) 點 與 中 某 個 結(jié) 點 重 合 ， 重 復(fù) 前 面 方 法 ， 得 到閉 跡 。 如 果 和 合 起 來 為 圖 ， 則 得 到 歐 拉 路 ， 否 則 繼 續(xù) 。GLL G LL G GGLL L L G???V1V2V3V4V6V5推論：無向圖 G具有一條歐拉回路 ，當(dāng)且僅當(dāng) G是連通 的，且 所有結(jié)點的度數(shù)全為偶數(shù) 半歐拉圖 歐拉圖 74 歐拉圖與漢密爾頓圖 V1V2V3V4V6V5V1V2V3V4V5可見 deg(A)=5， deg(B)=deg(C)=deg(D)=3，故在圖中不存在歐拉回路，哥尼斯堡七橋問題有了確切的否定答案 奇數(shù) 74 歐拉圖與漢密爾頓圖 CDAB思考：無向完全圖 Kp當(dāng) p取何值時為歐拉圖？ （ 3）一筆畫問題： 1）從圖 G中某個結(jié)點出發(fā)，經(jīng)過 G中的每一邊一次且僅一次 到達(dá)另一個結(jié)點（半歐拉圖） 2）從圖 G中某個結(jié)點出發(fā)，經(jīng)過 G中的每一邊一次且僅一次 回到該結(jié)點（歐拉圖） 74 歐拉圖與漢密爾頓圖 半歐拉圖 歐拉圖 V1V2V3V4V6V5V1V2V3V4V5單向歐拉路 ： 通過有向圖 G中每邊一次且僅一次的單向路 單向歐拉回路 ： 通過有向圖 G中每邊一次且僅一次的單向回路 （ 4） G為有向圖： 定理： 有向圖 G具有一條單向歐拉回路 ，當(dāng)且僅當(dāng) G是連通的 ， 且 每個結(jié)點的入度等于出度 有向圖 G具有單向歐拉路 ，當(dāng)且僅當(dāng) G是連通 的，且 除 兩個結(jié)點外 （一個結(jié)點的入度比出度大 1，另一個結(jié)點的入度比出度小 1 ），每個結(jié)點的入度等于出度 74 歐拉圖與漢密爾頓圖 歐拉回路是邊的遍歷問題，而漢密爾頓回路則是點的遍歷問題 ，即能否找到一條經(jīng)過每個點一次且僅一次最終回到起點的回路。經(jīng)典問題：十二面體問題 漢密爾頓圖 （ 1）定義：給定圖 G， 漢密爾頓路 ： 經(jīng)過圖中每個結(jié)點恰好一次的路 漢密爾頓回路 ： 經(jīng)過圖中每個結(jié)點恰好一次的回路 半漢密爾頓圖 ：具有漢密爾頓路的圖 漢密爾頓圖 ： 具有漢密爾頓回路的圖 74 歐拉圖與漢密爾頓圖 74 歐拉圖與漢密爾頓圖 （ 2） 必要條件的判定 ： 定理： 圖 G=V,E具有漢密爾頓回路，則對于 V的任何非空 子集 S， W(GS)≤|S|成立，其中 W(GS)是 GS的連通分支數(shù)。 證明：設(shè) C是 G的一條漢密爾頓回路，則對于 V的任意非空子 集 S，在 C中刪去 S的任意一個結(jié)點 a1，則 C a1是連通的非回 路。若再刪去 S中的另一結(jié)點 a2，則 W(C a1 a2) ≤2，歸納可 得： W(CS)≤|S| 而 CS是 GS的一個生成子圖，有 W(GS) ≤ W(CS) ≤|S| V1V2V3V4V5V674 歐拉圖與漢密爾頓圖 由此定理的結(jié)論，我們可以證明某些圖是非漢密爾頓圖 下圖中，選取 S={v1,v4}，則 GS中有三個分圖，因此 G不是漢密爾頓圖 考慮：用上面定理能證明某個特定的圖不是漢密爾頓圖， 那是否對于任意的非漢密爾頓圖，都能用上面方法證明呢？ 如果不行，該如何處理？ V1V7V4V3V5V8V6V2V3V5V8V6V2V774 歐拉圖與漢密爾頓圖 考慮 彼得森圖（ 不是漢密爾頓圖） ： 刪去一個或兩個結(jié)點，不能使圖變?yōu)椴贿B通圖；刪去三個結(jié)點，最多得到兩個連通分支的子圖；刪去四個結(jié)點，最多得到三個連通分支的子圖；刪去五個或者五個以上的結(jié)點，剩余的結(jié)點個數(shù)不會超過五個，故子圖的連通分支數(shù)也不會超過五 V1V2V3V4V5V6V7V8V9V1 0因而無法根據(jù)上述定理判定彼得森圖不是漢密爾頓圖 74 歐拉圖與漢密爾頓圖 另一個能判定非半漢密爾頓圖的方法： 如果一個圖中存在漢密爾頓路，我們用 A標(biāo)記圖中的任意一個結(jié)點，所有與其相鄰的結(jié)點標(biāo)記為 B，再標(biāo)記所有鄰接于B的結(jié)點為 A，鄰接于 A的結(jié)點為 B，直到所有的結(jié)點都有標(biāo)記結(jié)束。如果出現(xiàn)相鄰結(jié)點的標(biāo)記相同時，在對應(yīng)邊上增加一個結(jié)點，加上相異標(biāo)記。 如果圖中存在漢密爾頓路，則必定交替通過結(jié)點 A和 B，所以 A和 B的個數(shù)必定相同。 如果 A和 B的個數(shù)不同，表明此圖中肯定不會存在漢密爾頓路，不是半漢密爾頓圖，更不是漢密爾頓圖。 74 歐拉圖與漢密爾頓圖 V1V2V3V4V5V6V7V8V9V1 0A B B B A A A A A A B B B B B B 以此法標(biāo)記彼得森圖，得 7個 A9個 B，可知不是漢密爾頓圖。 74 歐拉圖與漢密爾頓圖 不是漢密爾頓圖 ABBABABAAABBAAAB74 歐拉圖與漢密爾頓圖 考慮：是否標(biāo)上標(biāo)記后，如果 A和 B的個數(shù)相等，圖中就一定有 漢密爾頓回路？ 不是 例如下圖 3A3B，但仍不存在漢密爾頓路。 AAABBB74 歐拉圖與漢密爾頓圖 （ 3） 充分條件的判定 ： 1）定理： 簡單圖 G具有 n個結(jié)點， G中 每一對結(jié)點度數(shù)之和大 于等于 n1，則 G中存在漢密爾頓路 。 證明： I. G是連通圖：若 G有兩個或多個不連通的分圖，設(shè)一個分 圖中有 n1個結(jié)點，另一個分圖中有 n2個結(jié)點，分別在兩個分圖中 選取兩個結(jié)點 v1和 v2，可知 d(v1) ≤ n11， d(v2) ≤ n21， d(v1) + d(v2) ≤ n1+ n22 n1，與已知條件矛盾，所以 G是連通圖。 74 歐拉圖與漢密爾頓圖 II. 構(gòu)造漢密爾頓路： 設(shè)在 G中有 p1條邊的通路， pn，其結(jié)點序列為 v1,v2,… ,vp。 i) v1或 vp鄰接于不在這條路上的一個結(jié)點：加入這個結(jié)點，擴(kuò)展路，得到 p條邊的通路； ii) v1和 vp只鄰接于這條路上的結(jié)點，則需證明存在回路包含這 p個結(jié)點： a) v1鄰接于 vp，顯然成立 74 歐拉圖與漢密爾頓圖 b) 假設(shè) v1的鄰接點集是 {vl,vm,… ,vt}， 2 ≤l,m,…,t ≤p1。 若 vp鄰接于 vl1,vm1,… ,vt1中的任意一個 vj1，則 v1v2… vj1 vp vp1… vj v1即為所求回路。 若 vp不鄰接于 vl1,vm1,… ,vt1中的任意一個，則 vp至多鄰接 于 pk1個結(jié)點， deg(vp) ≤pk1， deg(v1)=k，有 deg(v1)＋ deg(vp) ≤p1n1，與已知條件矛盾。 由于 G是連通圖，所以必定存在不屬于該回路的結(jié)點與回路 中某個結(jié)點鄰接，加入這個頂點，可以得到一個邊為 p的通路 iii) 重復(fù)上面方法，可得到有 n1條邊的通路 74 歐拉圖與漢密爾頓圖 只是充分條件而非必要 例如右圖， n=6，任何兩個結(jié)點之和為46－ 16，但 G中存在漢密爾頓（回）路。 2）定理： 簡單圖 G具有 n個結(jié)點，如果 G中 每一對結(jié)點度數(shù)之和大于等于 n，則 G中存在一條漢密爾頓回路 。 同樣的，這只是漢密爾頓回路存在的充分而非必要條件，從上例中類似可以推出。 74 歐拉圖與漢密爾頓圖 定理： G為漢密爾頓圖，當(dāng)且僅當(dāng)其閉包是漢密爾頓圖 。 （ 4） G的閉包 G=V,E有 n個結(jié)點，將 G中度數(shù)之和大于等于 n的非鄰接點連接起來得到圖 G’，對 G’重復(fù)以上步驟，直到不再存在這樣的結(jié)點對而得到的圖，即為 G的閉包 ，記為 C(G) (a) (b) (c) (d) 例： 第七章 圖論小結(jié) ? 圖、有 /無向邊、有 /無向圖、鄰接點 /邊、孤立結(jié)點、零圖、平凡圖、自回路、結(jié)點度數(shù)、出 /入度、多重圖、完全圖、補圖、子圖、生成子圖、子圖的補圖、圖的同構(gòu) ? 路、跡、通路、圈、結(jié)點連通、連通分支、連通圖、點 /邊割集、割點 /邊、連通度、邊連通度、可達(dá)性、圖的直徑、單側(cè) /強(qiáng) /弱連通、單側(cè) /強(qiáng) /弱分圖 ? 鄰接矩陣、可達(dá)性矩陣、完全關(guān)聯(lián)矩陣 ? 歐拉（回）路、（半）歐拉圖、漢密爾頓（回 )路、（半）漢密爾頓圖、圖的閉包