離散數(shù)學(7.4歐拉圖與漢密爾頓圖)

1、7.4 歐拉圖與漢密爾頓圖 7.4.1 歐拉圖歐拉圖 7.4.2漢密爾頓圖漢密爾頓圖 7.4.1 歐拉圖 歷史上的哥尼斯堡七橋問題是著名歷史上的哥尼斯堡七橋問題是著名 的圖論問題。的圖論問題。 問題是這樣的：問題是這樣的： 18世紀的東普魯士世紀的東普魯士 有個哥尼斯堡城，有個哥尼斯堡城， 在橫貫全城的普雷格在橫貫全城的普雷格 爾河兩岸和兩個島之間架設了爾河兩岸和兩個島之間架設了7座橋，座橋， 它它 們把河的兩岸和兩個島連接起來（如圖們把河的兩岸和兩個島連接起來（如圖 7.4.1）。）。 每逢假日，每逢假日， 城中居民進行環(huán)城游玩，城中居民進行環(huán)城游玩， 人們對此提出了一個人們對此提出了一個“

2、遍游遍游”問題，問題， 即即 能否有這樣一種走法，能否有這樣一種走法， 使得從某地出發(fā)使得從某地出發(fā) 通過且只通過每座橋一次后又回到原地通過且只通過每座橋一次后又回到原地 呢？呢？ 我們將圖我們將圖7.4.1中的哥尼斯堡城中的哥尼斯堡城 的的4塊陸地部分分別標以塊陸地部分分別標以A， B， ， D， 將陸地設想為圖的結點，將陸地設想為圖的結點， 而把橋畫成相而把橋畫成相 應的連接邊，應的連接邊， 這樣圖這樣圖7.4.1可簡化成圖可簡化成圖 7.4.2。 于是七橋于是七橋“遍游遍游”問題等價于問題等價于 在圖在圖7.4.2中，中， 從某一結點出發(fā)找到一從某一結點出發(fā)找到一 條回路，條回路， 通過

3、它的每條邊一次且僅一次，通過它的每條邊一次且僅一次， 并回到原來的結點。并回到原來的結點。 圖 7.4.1哥尼斯堡七橋問題示圖 圖圖 7.4.2哥尼斯保七橋問題簡化圖哥尼斯保七橋問題簡化圖 定義定義 7.5.1 給定無孤立結點的給定無孤立結點的 圖圖G， 若若存在一條存在一條經(jīng)過經(jīng)過G中中每邊一次每邊一次 且僅一次且僅一次的回路，的回路， 則該回路為歐拉回則該回路為歐拉回 路。路。 具有歐拉回路的圖稱為歐拉圖。具有歐拉回路的圖稱為歐拉圖。 例如，例如， 給出如圖給出如圖7.4.3所示的所示的 兩個圖，兩個圖， 容易看出，容易看出， (a)是歐拉圖，是歐拉圖， 而而(b)不是歐拉圖。不是歐拉圖。

4、 圖圖 7.4.3 定理定理 7.5.1 連通圖連通圖G是歐拉圖是歐拉圖 的的充要條件充要條件是是G的所有結點的度數(shù)都的所有結點的度數(shù)都 是偶數(shù)。是偶數(shù)。 證明證明: 必要性：必要性： 設設G是一歐拉是一歐拉 圖，圖， 是是G中的一條歐拉回路。中的一條歐拉回路。 當當通通 過過G的任一結點時，的任一結點時， 必通過關聯(lián)于該必通過關聯(lián)于該 點的兩條邊。點的兩條邊。 又因為又因為G中的每條邊僅中的每條邊僅 出現(xiàn)一次，出現(xiàn)一次， 所以所以所通過的每個結點所通過的每個結點 的度數(shù)必定是偶數(shù)。的度數(shù)必定是偶數(shù)。 圖圖 7.4.4 圖圖G 充分性：充分性： 我們可以這樣來作我們可以這樣來作 一個閉跡一個閉

5、跡， 假設它從某結點假設它從某結點A開始，開始， 沿著一條邊到另一結點，沿著一條邊到另一結點， 接著再從這接著再從這 個結點，個結點， 沿沒有走過的邊前進，沿沒有走過的邊前進， 如此如此 繼續(xù)下去。繼續(xù)下去。 因為我們總是沿著先前沒因為我們總是沿著先前沒 有走過的新邊走，有走過的新邊走， 又由于圖又由于圖G的邊數(shù)的邊數(shù) 有限，有限， 所以這個過程一定會停止。所以這個過程一定會停止。 但但 是，是， 因為每一個結點都與偶數(shù)條邊關因為每一個結點都與偶數(shù)條邊關 聯(lián)，聯(lián)， 而當沿而當沿前進到達結點前進到達結點v 時，時， 若若 vA， 走過了與走過了與v關聯(lián)的奇數(shù)條邊，關聯(lián)的奇數(shù)條邊， 這樣在這樣在v

6、上總還有一條沒有走過的邊。上總還有一條沒有走過的邊。 因此，因此， 必定返回停止在必定返回停止在A（見圖（見圖 7.4.4）。）。 如果如果走遍了走遍了G的所有邊，的所有邊， 那么我們就得到所希望的一條歐拉那么我們就得到所希望的一條歐拉 回路?；芈贰?如果不是這樣，如果不是這樣， 那么在那么在上上 將有某一結點將有某一結點B， 與它關聯(lián)的一些與它關聯(lián)的一些 邊尚未被邊尚未被走過（因走過（因G連通）。連通）。 但是，但是， 實際上，實際上， 因為因為走過了與走過了與B關聯(lián)的偶關聯(lián)的偶 數(shù)條邊，數(shù)條邊， 因此不屬于因此不屬于的與的與B關聯(lián)的關聯(lián)的 邊也是偶數(shù)條。邊也是偶數(shù)條。 對于其他有未走過對于

7、其他有未走過 邊所關聯(lián)的所有結點來說，邊所關聯(lián)的所有結點來說， 上面的上面的 討論同樣正確。討論同樣正確。 于是若設于是若設G1是是G 的包含點的包含點B的一個連通分支，的一個連通分支， 則則G1 的結點全是偶數(shù)度結點。的結點全是偶數(shù)度結點。 運用上面的討論，運用上面的討論， 我們在我們在G1中中 得到一個從得到一個從B點出發(fā)的一條閉跡點出發(fā)的一條閉跡1。 這樣我們就得到了一條更大的閉跡，這樣我們就得到了一條更大的閉跡， 它是從它是從A點出發(fā)沿點出發(fā)沿前進到達前進到達B， 然后然后 沿閉跡沿閉跡1回到回到B， 最后再沿最后再沿由由B走到走到 A。 如果我們?nèi)匀粵]有走遍整個圖，如果我們?nèi)匀粵]有走

8、遍整個圖， 那么我們再次把閉跡擴大，那么我們再次把閉跡擴大， 以此類推，以此類推， 直到最后得到一個歐拉回路。直到最后得到一個歐拉回路。 由于在七橋問題的圖由于在七橋問題的圖7.4.2中，中， 有個點是奇數(shù)度結點，有個點是奇數(shù)度結點， 故不存在歐故不存在歐 拉回路，拉回路， 七橋問題無解。七橋問題無解。 在圖在圖7.2.3中，中， (a)圖的每個結點圖的每個結點 的度數(shù)都為，的度數(shù)都為， 所以它是歐拉圖；所以它是歐拉圖；(b) 圖不是歐拉圖。圖不是歐拉圖。 但我們繼續(xù)考察但我們繼續(xù)考察(b)圖圖 可 以 發(fā) 現(xiàn) ，可 以 發(fā) 現(xiàn) ， 該 圖 中 有 一 條 路該 圖 中 有 一 條 路 v2v

9、3v4v5v2v1v5， 它經(jīng)過它經(jīng)過(b)圖中的每條圖中的每條 邊一次且僅一次，邊一次且僅一次， 我們把這樣的路稱為我們把這樣的路稱為 歐拉路歐拉路(非歐拉回路非歐拉回路)。 定義定義7.5.2 通過圖通過圖G的每條邊一的每條邊一 次且僅一次的路稱為圖次且僅一次的路稱為圖G的歐拉路。的歐拉路。 對對 于歐拉路有下面的判定方法。于歐拉路有下面的判定方法。 定理定理7.5.2 連通圖連通圖G具有一條連具有一條連 接結點接結點vi和和vj的歐拉路當且僅當?shù)臍W拉路當且僅當vi和和vj是是G 中中僅有僅有的的奇數(shù)度結點奇數(shù)度結點。 證明證明: 將邊將邊(vi， vj)加于圖加于圖G上，上， 令其所得的

10、圖為令其所得的圖為G（可能是多重圖）。（可能是多重圖）。 由定理由定理7.5 .1知：知： G有連接結點有連接結點vi和和vj的歐拉路，的歐拉路， iff G有一條歐拉回路，有一條歐拉回路， iff G的所有結點均為偶度結點，的所有結點均為偶度結點， iff G的所有結點除的所有結點除vi和和vj外均為外均為 偶度結點，偶度結點， iff vi和和vj是是G中僅有的奇度結點。中僅有的奇度結點。 我國民間很早就流傳一種我國民間很早就流傳一種“一筆一筆 畫畫”游戲。游戲。 由定理由定理7.5 .1和定理和定理7.5.2知，知， 有兩種情況可以一筆畫。有兩種情況可以一筆畫。 1) 如果圖中所有結點是

11、偶數(shù)度結如果圖中所有結點是偶數(shù)度結 點，點， 則可以任選一點作為始點一筆畫完；則可以任選一點作為始點一筆畫完； 2) 如果圖中只有兩個奇度結點，如果圖中只有兩個奇度結點， 則可以選擇其中一個奇度結點作為始點則可以選擇其中一個奇度結點作為始點 也可一筆畫完。也可一筆畫完。 【例【例7.4.1】圖圖7.4.5(a)是一幢房子是一幢房子 的平面圖形，的平面圖形， 前門進入一個客廳，前門進入一個客廳， 由客廳通向由客廳通向4個房間。個房間。 如果要求每如果要求每 扇門只能進出一次，扇門只能進出一次， 現(xiàn)在你由前門現(xiàn)在你由前門 進去，進去， 能否通過所有的門走遍所有能否通過所有的門走遍所有 的房間和客廳

12、，的房間和客廳， 然后從后門走出。然后從后門走出。 圖圖 7.4.5 解解: 將將4個房間和一個客廳及前個房間和一個客廳及前 門外和后門外作為結點，門外和后門外作為結點， 若兩結點有若兩結點有 邊相連就表示該兩結點所表示的位置邊相連就表示該兩結點所表示的位置 有一扇門相通。有一扇門相通。 由此得圖由此得圖7.4.5(b)。 由于圖中有由于圖中有4個結點是奇度結點，個結點是奇度結點， 故由故由 定理定理7.5.2知本題無解。知本題無解。 類似于無向圖的結論，類似于無向圖的結論， 對有向對有向 圖有以下結果。圖有以下結果。 定理定理7.5.3 一個連通有向圖具有一個連通有向圖具有 （有向）歐拉回路

13、的充要條件是圖中每（有向）歐拉回路的充要條件是圖中每 個結點的入度等于出度。個結點的入度等于出度。 一個連通有向一個連通有向 圖具有有向歐拉路的充要條件是圖具有有向歐拉路的充要條件是最多最多除除 兩個兩個結點外的每個結點的入度等于出度，結點外的每個結點的入度等于出度， 但在這兩個結點中，但在這兩個結點中， 一個結點的入度比一個結點的入度比 出度大出度大1， 另一個結點的入度比出度少另一個結點的入度比出度少1。 下面舉一個有趣的例子是計算機下面舉一個有趣的例子是計算機 鼓輪的設計。鼓輪的設計。 【例【例7.4.1】設一個旋轉鼓的表面被分設一個旋轉鼓的表面被分 成成24個部分，個部分， 如圖如圖7

14、 - 26所示。所示。 其中每其中每 一部分分別由導體或絕緣體構成，一部分分別由導體或絕緣體構成， 圖中圖中 陰影部分表示導體，陰影部分表示導體， 空白部分表示絕緣空白部分表示絕緣 體，體， 絕緣體部分給出信號絕緣體部分給出信號0，導體部分，導體部分 給出信號給出信號1。 根據(jù)鼓輪轉動后所處的位根據(jù)鼓輪轉動后所處的位 置，置， 4個觸頭個觸頭a， b， c， d將獲得一定將獲得一定 的信息。的信息。 圖中所示的信息為圖中所示的信息為1101， 若將若將 鼓輪沿順時針方向旋轉一格，鼓輪沿順時針方向旋轉一格， 則則4個觸個觸 頭頭a， b， c， d獲得獲得1010 。試問鼓輪上。試問鼓輪上 16

15、個部分怎樣安排導體及絕緣體，個部分怎樣安排導體及絕緣體， 才能才能 使鼓輪每旋轉一格后，使鼓輪每旋轉一格后， 4 個觸頭得到的個觸頭得到的 每組信息（共每組信息（共16組）均不相同？這個問組）均不相同？這個問 題也即為：題也即為： 把把16個二進制數(shù)字排成一個個二進制數(shù)字排成一個 環(huán)形，環(huán)形， 使得使得4個依次相連的數(shù)字所組成個依次相連的數(shù)字所組成 的的16個個4位二進制數(shù)均不相同。位二進制數(shù)均不相同。 圖圖 7.4.6 解解: 問題的答案是肯定的。問題的答案是肯定的。 下面下面 談一下解決這個問題的思路。談一下解決這個問題的思路。 設設i 0， 1 （i16）。）。 每旋轉一格，每旋轉一格，

16、 信號從信號從1234轉到轉到 2345， 前者的右前者的右 3 位決定了后者的位決定了后者的 左左 3 位。位。 于是，于是， 我們的想法是將這我們的想法是將這16個個 二進制數(shù)字的環(huán)形二進制數(shù)字的環(huán)形1216對應一個歐拉對應一個歐拉 有向路，有向路， 使其邊依次為使其邊依次為1234， 2345， 3456， （圖（圖7 27）。）。 我們把我們把234對應一個結點，對應一個結點， 它是弧它是弧 1234的終點也是弧的終點也是弧2345的始點。的始點。 這樣我們的問題就轉化為以位二進制數(shù)這樣我們的問題就轉化為以位二進制數(shù) 為結點作一個有向圖，為結點作一個有向圖， 再在圖中找出歐再在圖中找出

17、歐 拉回路。拉回路。 圖圖 7.4.7 歐拉有向路示圖歐拉有向路示圖 構造一個有個結點的有向圖構造一個有個結點的有向圖G （圖（圖7 28）。）。 其結點分別記為位其結點分別記為位 二進制數(shù)二進制數(shù)000、 001、 010、 011、 100、 101、 110、 111。 從結點從結點 123出發(fā)可引出兩條有向邊，出發(fā)可引出兩條有向邊， 其終其終 點分別是點分別是23和和23， 記這兩條記這兩條 有向邊為有向邊為123和和123。 這樣這樣 圖圖G就有就有16條邊。條邊。 由于由于G中每點的入度中每點的入度 等于出度都等于，等于出度都等于， 故在圖中可找到故在圖中可找到 一條歐拉回路。一條

18、歐拉回路。 例如（僅寫出邊的序列）例如（僅寫出邊的序列） e0e1e2e4e9e3e6e13e10e5e11e7e15e14e1 2e8。 。 根據(jù)鄰接邊的標號記法，根據(jù)鄰接邊的標號記法， 這這 16個二進制數(shù)可寫成對應的二進制個二進制數(shù)可寫成對應的二進制 序列序列0000100110101111， 把這個把這個 序列排成環(huán)狀，序列排成環(huán)狀， 與所求的鼓輪相對與所求的鼓輪相對 應，應， 如圖如圖7.4.6所示。所示。 該例可推廣到鼓輪有該例可推廣到鼓輪有n個觸個觸 點的情況。點的情況。 圖圖 7.4.8 具有具有 8 個結點的有向圖個結點的有向圖G 7.4.2 漢密爾頓圖漢密爾頓圖 與歐拉回路

19、類似的是漢密爾與歐拉回路類似的是漢密爾 頓回路問題。頓回路問題。 它是它是1859年漢密爾頓年漢密爾頓 首先提出的一個關于首先提出的一個關于12面體的數(shù)學面體的數(shù)學 游戲：游戲： 能否在圖能否在圖7.4.9中找到一個回中找到一個回 路，路， 使它含有圖中使它含有圖中所有結點所有結點一次且一次且 僅一次僅一次？ 若把每個結點看成一座城若把每個結點看成一座城 市，市， 連接兩個結點的邊看成是交通連接兩個結點的邊看成是交通 線，線， 那么這個問題就變成能否找到那么這個問題就變成能否找到 一條旅行路線，一條旅行路線， 使得沿著該旅行路使得沿著該旅行路 線經(jīng)過每座城市恰好一次，線經(jīng)過每座城市恰好一次，

20、再回到再回到 原來的出發(fā)地呢？為此，原來的出發(fā)地呢？為此， 這個問題這個問題 也被稱作周游世界問題。也被稱作周游世界問題。 圖圖 7.4.9 12 面體游戲示圖面體游戲示圖 對圖對圖7.4.9 ， 圖中粗線給出了這圖中粗線給出了這 樣的回路。樣的回路。 定義定義 7.5.3 給定圖給定圖G， 若有一條若有一條 路通過路通過G中每個結點恰好一次，中每個結點恰好一次， 則這樣的則這樣的 路稱為漢密爾頓路；若有一個圈，路稱為漢密爾頓路；若有一個圈， 通過通過G 個每個結點恰好一次，個每個結點恰好一次， 這樣的圈稱為漢密這樣的圈稱為漢密 爾頓回路（或漢密爾頓圈）。爾頓回路（或漢密爾頓圈）。 具有漢密爾

21、具有漢密爾 頓頓回回路的圖稱為漢密爾頓圖。路的圖稱為漢密爾頓圖。 盡管漢密爾頓回路與歐拉回路問盡管漢密爾頓回路與歐拉回路問 題在形式上極為相似，題在形式上極為相似， 但是到目前為止還但是到目前為止還 不知道一個圖為漢密爾頓圖的充要條件，不知道一個圖為漢密爾頓圖的充要條件， 尋找該充要條件仍是圖論中尚未解決的主尋找該充要條件仍是圖論中尚未解決的主 要問題之一。要問題之一。 下面先給出一個簡單而有用下面先給出一個簡單而有用 的必要條件。的必要條件。 定理定理7.5.4 設圖設圖GV ,E 是漢密爾頓圖，是漢密爾頓圖， 則對于則對于V的每個非的每個非 空子集空子集S， 均有均有 W（GS）|S| 成

22、立，成立， 其中其中W（GS）是圖）是圖G S的連通分支數(shù)。的連通分支數(shù)。 證明證明: 設設是是G的漢密爾頓回的漢密爾頓回 路，路， S是是V的任一非空子集。的任一非空子集。 在在G S中，中， 最多被分為最多被分為|S|段，段， 所以所以 W （ G S ） |S| 利用本定理可判別某些圖不利用本定理可判別某些圖不 為漢密爾頓圖。為漢密爾頓圖。 如在圖如在圖7.4.10中，中， 若取若取Sv1， v4， 則則GS有有 3 個連通分支，個連通分支， 故該圖不是漢密爾頓故該圖不是漢密爾頓 圖。圖。 判斷漢密爾頓圖的充分條件判斷漢密爾頓圖的充分條件 很多，很多， 我們僅介紹其中一個。我們僅介紹其中

23、一個。 圖圖7.4.10 定理定理 7.5.5 設設GV ,E是有是有n個個 結點的簡單圖，結點的簡單圖， 1） 如果任兩結點如果任兩結點u， vV， 均有均有 deg(u)deg(v) n 1， 則在則在G中存在一條漢密爾頓路；中存在一條漢密爾頓路； 2） 如果對任兩結點如果對任兩結點u， vV， 均有均有 deg(u)deg(v) n， 則則G是漢密爾頓圖。是漢密爾頓圖。 證明證明 略。略。 【例【例7.4.2】某地有個風景點。某地有個風景點。 若每個若每個 景點均有兩條道路與其他景點相通，景點均有兩條道路與其他景點相通， 問是問是 否可經(jīng)過每個景點恰好一次而游完這處？否可經(jīng)過每個景點恰好

24、一次而游完這處？ 解解 將景點作為結點，將景點作為結點， 道路作為邊，道路作為邊， 則得到一個有個結點的無向圖。則得到一個有個結點的無向圖。 由題意，由題意， 對每個結點對每個結點vi， 有有deg(vi) 2（i5）。）。 則對任兩點則對任兩點vi， vj（i， j5）均有）均有 deg(vi)deg(vj)2245 1 可知此圖一定有一條漢密爾頓路，可知此圖一定有一條漢密爾頓路， 本題本題 有解。有解。 我們再通過一個例子，我們再通過一個例子， 介紹一個判別漢介紹一個判別漢 密爾頓路不存在的標號法。密爾頓路不存在的標號法。 【例【例7.4.3】證明圖證明圖7 31所示的圖沒所示的圖沒 有漢

25、密爾頓路。有漢密爾頓路。 證明證明: 任取一結點如任取一結點如v1， 用用A標記，標記， 所有與它相鄰的結點標所有與它相鄰的結點標B。 繼續(xù)不斷地繼續(xù)不斷地 用用A標記所有鄰接于標記所有鄰接于B的結點，的結點， 用用B標記標記 所有鄰接于所有鄰接于A的結點，的結點， 直到圖中所有結直到圖中所有結 點全部標記完畢。點全部標記完畢。 如果圖中有一條漢密爾頓路，如果圖中有一條漢密爾頓路， 則必交替通過結點則必交替通過結點A和和B。 因此或者結點因此或者結點 A和和B數(shù)目一樣數(shù)目一樣， 或者兩者或者兩者相差相差個。個。 圖圖7.4.11 而本題有個結點標記而本題有個結點標記A， 個結點標記個結點標記B

26、， 它們相差個，它們相差個， 所以該圖不存在漢密爾頓路。所以該圖不存在漢密爾頓路。 作為漢密爾頓回路的自然推作為漢密爾頓回路的自然推 廣是著名的廣是著名的貨郎擔貨郎擔問題。問題。 問題是這問題是這 樣敘述的：樣敘述的： 設有一個貨郎，設有一個貨郎， 從他所從他所 在的城鎮(zhèn)出發(fā)去在的城鎮(zhèn)出發(fā)去n個城鎮(zhèn)。個城鎮(zhèn)。 要要 求經(jīng)過每個城鎮(zhèn)恰好一次，求經(jīng)過每個城鎮(zhèn)恰好一次， 然后返然后返 回原地，回原地， 問他的旅行路線怎樣安排問他的旅行路線怎樣安排 才最經(jīng)濟？從圖論的觀點來看，才最經(jīng)濟？從圖論的觀點來看， 該該 問題就是：問題就是： 在一個有權在一個有權完全圖完全圖中找中找 一條一條權最小權最小的漢密爾頓的漢密爾頓回回路。路。 研究這個問題是十分有趣且研究這個問題是十分有趣且 有實用價值的。有實用價值的。 但很可惜