第二章道路與回路2.1道路與回路

1、第二章第二章 道路與回路道路與回路2.1道路與回路道路與回路l定義2.1.1 有向圖 中，若邊序列 ，其中 滿足是 的終點(diǎn)，是 的始點(diǎn)，就稱 是 的一條有向道路。如果的終點(diǎn)也是 的始點(diǎn)，則稱 是 的一條有向回路。),.,(21iqiieeeP ),(jlikvve lv1ikejv1ikeiqeileEVG,GGPP道路與回路道路與回路l 如果 中的邊沒有重復(fù)出現(xiàn)，則分別稱為簡單有向道路和簡單有向回路。進(jìn)而，如果 中結(jié)點(diǎn)也不重復(fù)出現(xiàn)，又分別稱它們是初級有向道路和初級有向回路簡稱為路和回路。顯然，初級有向道路(回路)一定是簡單有向道路(回路)。PP道路與回路道路與回路l定義2.1.2 無向圖 中

2、，若點(diǎn)邊交替序列 滿足 是的兩個(gè)端點(diǎn),則稱 是 中的一條鏈或道路。如果，則稱 是 中的一個(gè)圈，或回路。 如果 中沒有重復(fù)出現(xiàn)的邊，稱之為簡單道路或簡單回路，若其中結(jié)點(diǎn)也不重復(fù)，又稱之為初級道路或初級回路。),.,(12211iqiqiiiiveevevP1,ikikvvikeiliqvv EVG,PGPGP道路與回路道路與回路l定義2.1.3 設(shè) 是無向圖，若 的任意兩結(jié)點(diǎn)之間都存在道路，就稱 是連通圖，否則稱為非連通圖。 如果 是有向圖，不考慮其邊的方向，即視為無向圖，若它是連通的，則稱 是連通圖。 若連通子圖 不是 的任何連通子圖的真子圖，則稱 是 的極大連通子圖，或稱連通支。顯然 的每個(gè)

3、連通支都是它的導(dǎo)出子圖。 GGGGGGGGHH道路與回路道路與回路l定義2.1.4 設(shè) 是簡單圖 中含結(jié)點(diǎn)數(shù)大于3的一個(gè)初級回路，如果結(jié)點(diǎn) 和 在 中不相鄰，而邊 ，則稱 是 的一條弦。CGivjvC GEvvji,jivv ,C道路與回路道路與回路l證明：若對每一個(gè)證明：若對每一個(gè) ，都有，都有 ，則，則 中必含帶弦的回路。中必含帶弦的回路。 證明：在 中構(gòu)造一條初級道路 ，不妨設(shè) ， 。由于 是極長的初級道路，所以 和 的鄰接電都在該道路 了。由已知條件， ，不妨設(shè) 。其中 ，這時(shí) 是一條初級回路，而 就是該回路中的一條弦。 GVvkG 3kvdGiliieeeP,21101,vveill

4、ilvve,1P0vlvP 3kvd ,10ikijvvvvkj 1010,vvvvikijvv ,0道路與回路道路與回路l定義2.1.5 設(shè) 是無向圖，如果 可以劃分為子集 和 ，使得對所有的 ， 和 都分屬于 和 ，則稱 是二分圖。EVG, GVXYu GEvue,vXYG道路與回路道路與回路l證明：如果二分圖證明：如果二分圖 中存在回路，則它們都是中存在回路，則它們都是由偶數(shù)條邊組成的。由偶數(shù)條邊組成的。 證明：設(shè) 是二分圖 的任一條回路，不妨設(shè) 是 的始點(diǎn)，由于 是二分圖，所以沿回路 必須經(jīng)過偶數(shù)條邊才能達(dá)到某結(jié)點(diǎn) ，因而只有經(jīng)過偶數(shù)條邊才能回到 。GGCXv 0CGCXvi0v道路與

5、回路道路與回路l證明：設(shè)證明：設(shè) 是簡單圖，當(dāng)是簡單圖，當(dāng) 時(shí)，時(shí)， 是連通圖。是連通圖。 證明：假定 是非連通圖，則它至少含有2個(gè)連通分支。設(shè)分別是 。其中 由于 是簡單圖，因此 G2121nnmGG222111,EVGEVGnnnnGVnGV21222111,G.121121,121,121221122221111nnnnmnnGEnnGE道路與回路道路與回路由于 ， 所以 與已知條件矛盾，故 是連通圖。1, 121nnnn,21211112121nnnnnmG2.3 歐拉道路與回路歐拉道路與回路歐拉道路與回路歐拉道路與回路l1736年瑞士著名數(shù)學(xué)家歐拉(Leonhard Euler)發(fā)表

6、了圖論的第一篇論文“哥尼斯堡七橋問題”。成功地回答了，圖中是否存在經(jīng)過每條邊一次且僅一次的回路。歐拉道路與回路歐拉道路與回路歐拉道路與回路歐拉道路與回路l定義2.3.1 無向連通圖 中的一條經(jīng)過所有邊的簡單回路(道路)稱為 的歐拉回路(道路)。l定理2.3.1 無向連通圖 存在歐拉回路的充要條件是 中各結(jié)點(diǎn)的度都是偶數(shù)。GGGEVG,歐拉道路與回路歐拉道路與回路l定理2.3.1的證明：1.必要性：若 中有歐拉回路 ，則 過每條邊一次且僅一次。對任一結(jié)點(diǎn) 來說，如果 經(jīng)過進(jìn)入 ，則一定通過另一條邊從 離開。因此結(jié)點(diǎn) 的度是偶數(shù)。2.充分性：由于 是有窮圖，因此可以斷定，從 的任一結(jié)點(diǎn)出發(fā)一定存在

7、 的一條簡單回路 。這是因?yàn)楦鹘Y(jié)點(diǎn)的度都是偶數(shù)，所以這條簡單道路不可能停留在以外的某個(gè)點(diǎn)，而不能再向前延伸以致構(gòu)成回路 。ie0vie0vGCCvCvvvGGGCC歐拉道路與回路歐拉道路與回路l推論2.3.1 若無向連通圖 中只有2個(gè)度為奇的結(jié)點(diǎn)。則 存在歐拉道路。證明：設(shè)和是兩個(gè)度為奇數(shù)的結(jié)點(diǎn)。作，則中各點(diǎn)的度都是偶數(shù)。由定理2.3.1，有歐拉回路，它含邊，刪去該邊，得到一條從到的簡單道路，它恰好經(jīng)過了 的所有邊，亦即是一條歐拉道路。ivjv),(jivvGG),(jivvGGivjvGGG歐拉道路與回路歐拉道路與回路l推論2.3.2 若有向連通圖 中各結(jié)點(diǎn)的正，負(fù)度相等，則 存在有向歐拉道

8、路。其證明與定理2.3.1的證明相仿。GG歐拉道路與回路歐拉道路與回路l例2.3.3 設(shè)連通圖G=(V,E)有k個(gè)度為奇數(shù)的結(jié)點(diǎn)，那么E(G)可以劃分成k/2條簡單道路。證明：由性質(zhì)1.1.2，k是偶數(shù)。在這k個(gè)結(jié)點(diǎn)間增添k/2條邊，使每個(gè)結(jié)點(diǎn)都與其中一條邊關(guān)聯(lián)，得到G，那么G中各結(jié)點(diǎn)的度都為偶數(shù)。 由定理2.3.1，G包含一個(gè)歐拉回路C。而新添的k/2條邊再C上都不相鄰。所以刪去這些邊后，我們就得到由E(G)劃分成的k/2條簡單道路。2.4 哈密頓道路與回路哈密頓道路與回路哈密頓道路與回路哈密頓道路與回路哈密頓道路與回路哈密頓道路與回路l定義2.4.1 無向圖的一條過全部結(jié)點(diǎn)的初級回路(道路

9、)稱為G的哈密頓回路(道路)，簡記為H回路(道路)。 哈密頓回路是初級回路，是特殊的簡單回路，因此它與歐拉回路不同。當(dāng)然在特殊情況下，G的哈密頓回路恰好也是其歐拉回路。鑒于H回路是初級回路，所以如果G中含有重邊或自環(huán)，刪去它們后得到的簡單圖G，那么G和G關(guān)于H回路（道路）的存在性是等價(jià)的。因此，判定H回路存在性問題一般是針對簡單圖的。哈密頓道路與回路哈密頓道路與回路l定理2.4.1 如果簡單圖G的任意兩結(jié)點(diǎn) 之間恒有 ，則G中存在哈密頓路。 jivv ,1)()(nvdvdji哈密頓道路與回路哈密頓道路與回路l推論2.4.1 若簡單圖 的任意兩結(jié)點(diǎn) 和 之間恒有 ，則 中存在哈密頓回路。l推論2.4.2若簡單圖 中每個(gè)結(jié)點(diǎn)的度都大于等于 ，則 有 回路。ivjvnvdvdji)()(GGGGH2n哈密頓道路與回路哈密頓道路與回路l引理2.4.1設(shè) 是簡單圖， 是不相鄰結(jié)點(diǎn)，且滿足 ，則 存在 回路的充要條件是 有 回路。l定義2.4.2若 和 是簡單圖 的不相鄰結(jié)點(diǎn)，且滿足 ，則令 對 重復(fù)上述過程，直至不再有這樣的結(jié)點(diǎn)對為止。最終得到的圖為 的閉合圖，記作 。jivv ,nvdvdji)()(),(jivv