大學(xué)離散數(shù)學(xué)歐拉圖和哈密爾頓圖課件

2023/6/301第15章歐拉圖和哈密頓圖15.1歐拉圖15.2哈密爾頓圖2023/6/30215.1歐拉圖15.1.1問題引入15.1.2歐拉圖15.1.3歐拉圖的判定定理15.1.4中國郵路問題2023/6/30315.1.1問題引入哥尼斯堡七橋問題SevenbridgesofK?nigsbergproblem問題分析：ACBD2023/6/30415.1.2歐拉圖定義15.1：設(shè)Ｇ＝＜V，E＞是連通圖歐拉通路（EulerPath） 半歐拉圖歐拉回路（EulerCircuit） 歐拉圖(Eulerian)說明規(guī)定平凡圖是歐拉圖；歐拉通路是簡單通路,歐拉回路是簡單回路；環(huán)不影響圖的歐拉性。2023/6/30515.1.2歐拉圖實(shí)例2023/6/30615.1.3歐拉圖的判定定理無向歐拉（半歐拉）圖的判定定理定理15.1無向圖G是歐拉圖

G是連通的且無奇度頂點(diǎn)。定理15.2無向圖G是半歐拉圖

G是連通的，且G中恰有2個(gè)奇度頂點(diǎn)2023/6/30715.1.3歐拉圖的判定定理例1：無歐拉通(回)路歐拉圖歐拉圖半歐拉圖半歐拉圖無歐拉通(回)路2023/6/30815.1.3歐拉圖的判定定理例2：ACBD2023/6/30915.1.3歐拉圖的判定定理例3：一筆畫問題及推廣問題描述問題分析設(shè)圖中有2k個(gè)奇度點(diǎn)，若k＝0，可以一筆畫成，且起點(diǎn)和終點(diǎn)相同；若k＝1，可以一筆畫成，起點(diǎn)和終點(diǎn)恰為圖中的兩個(gè)奇度點(diǎn)；若k＞1，可以k筆畫成，每筆的起點(diǎn)和終點(diǎn)恰為圖中的兩個(gè)奇度點(diǎn)；2023/6/301015.1.3歐拉圖的判定定理有向歐拉（半歐拉）圖的判定定理定理15.3有向圖D是歐拉圖

D是強(qiáng)連通且所有頂點(diǎn)的入度等于出度。定理15.4有向圖D是半歐拉圖

D是單向連通的且D中恰有兩個(gè)奇度頂點(diǎn)，其中一個(gè)頂點(diǎn)的入度比出度大1,一個(gè)頂點(diǎn)的入度比出度小1,其余的頂點(diǎn)的入度等于出度。2023/6/301115.1.3歐拉圖的判定定理例1歐拉圖無歐拉通路無歐拉通路半歐拉圖無歐拉通路半歐拉圖2023/6/301215.1.3歐拉圖的判定定理例2：問題描述計(jì)算機(jī)鼓輪設(shè)計(jì)中模數(shù)轉(zhuǎn)換問題問題分析ABC100011102023/6/301315.1.4中國郵路問題

問題描述：設(shè)有某郵遞員為送信，從郵局出發(fā)，到所管轄的街道投遞郵件，最后返回郵局，若必須走遍所轄各街道中每一條最少一次，則怎樣選擇投遞路線使所走的路程最短？問題抽象：將街區(qū)用一個(gè)圖G進(jìn)行表示，上述問題可以用圖論的語言來描述：在一個(gè)賦權(quán)圖中，能否找到一條包含每條邊最少一次且長度最短回路？2023/6/301415.1.4中國郵路問題問題分析若G不連通，則無解否則：若G是歐拉圖，則G的歐拉回路就是問題的最優(yōu)解。若G是半歐拉圖，且郵局就是其中一個(gè)奇度點(diǎn)問題轉(zhuǎn)化為求G的歐拉通路和兩點(diǎn)的最短路徑問題。若G中次數(shù)為奇數(shù)的結(jié)點(diǎn)多于2則回路中必須增加更多的重復(fù)邊，這時(shí)，怎樣使重復(fù)邊的總長度最小？2023/6/301515.1.4中國郵路問題例如：2023/6/301615.1.4中國郵路問題判斷條件定理：設(shè)L是圖G的包含所有邊的回路，則L具有最小長度的充分必要條件是：每條邊最多重復(fù)一次；G的每個(gè)回路上，所有重復(fù)邊的長度之和，不超過該回路長度的一半。2023/6/301715.2Hamilton

圖15.2.1問題引入15.2.2Hamilton圖的定義15.2.3Hamilton圖的判定方法15.2.4應(yīng)用舉例2023/6/301815.2.1問題引入周游世界問題(W.Hamilton,1859年)2023/6/301915.2.1問題引入WillamRowanHamilton(1805~1865):

2023/6/302015.2.2Hamilton圖的定義定義15.2：設(shè)圖G＝＜V，E＞哈密頓通路 半哈密頓圖哈密頓回路 哈密頓圖說明：規(guī)定平凡圖是哈密頓圖2023/6/302115.2.2Hamilton圖的定義例：判斷下圖是否為H圖？2023/6/302215.2.3Hamilton圖的判定方法定理15.6（必要條件）設(shè)G＝＜V，E＞是H圖，則對V的每個(gè)非空子集V1均有下式成立：

p（G－V1）≤|V1|----------（1）證明：若G是H回路C，則（1）顯然成立；若G是H圖，則設(shè)C是G的一條H回路，則對V的任意非空子集V1

，均有p（C－V1）≤|

V1

|，而C－V1是G－V1的生成子圖，故有p（G－V1）≤p（C－V1）于是有：

p（G－V1）≤|V1|

成立。2023/6/302315.2.3Hamilton圖的判定方法|V1|＝3，

p（G－V1）＝4p（G－V1）≤|V1|不成立，故G非H圖。GG－V1例1：2023/6/302415.2.3Hamilton圖的判定方法例2：證明下述各圖不是哈密頓圖:(a)(b)推論1:哈密爾頓圖無割點(diǎn).2023/6/302515.2.3Hamilton圖的判定方法例3：證明下述各圖不是哈密頓圖。2023/6/302615.2.3Hamilton圖的判定方法推論2：對二部圖G＝＜V1,V2,E＞若|V1|≠|(zhì)V2|，則一定不是H圖。證明：對二部圖G＝＜V1,V2,E＞設(shè)|V1|＜|V2|，則 p(G－V1)＝|V2|＞|V1|，這與定理15.6p(G－V1)＜|V1|相矛盾,故G不是H圖。2023/6/302715.2.3Hamilton圖的判定方法例4：證明右圖不是哈密頓圖證：設(shè)存在一條哈密頓回路,∵a,f,g是2度頂點(diǎn),∴邊(a,c),(f,c)和(g,c)必在這條哈密頓回路上,從而點(diǎn)c出現(xiàn)3次,與假設(shè)矛盾.故該圖不是哈密頓圖abcde

fg2023/6/302815.2.3Hamilton圖的判定方法哈密頓回路(通路)的充分條件定理15.7：設(shè)G是n(n3)階無向簡單圖,若任意兩個(gè)不相鄰的頂點(diǎn)u,v有：

d(u)+d(v)≥n-1，則G中存在哈密頓通路;

推論：設(shè)G是n(n3)階無向簡單圖,若任意兩個(gè)不相鄰的頂點(diǎn)u,v有：d(u)+d(v)≥nG中存在哈密頓回路，G為哈密頓圖;2023/6/302915.2.4應(yīng)用舉例例1（排座問題）有7個(gè)人,A會講英語,B會講英語和漢語,C會講英語、意大利語和俄語,D會講日語和漢語,E會講德語和意大利語,F會講法語、日語和俄語,G會講法語和德語.問：能否將他們沿圓桌安排就坐成一圈,使得每個(gè)人都能與兩旁的人交談?解：作無向圖,每人是一個(gè)頂點(diǎn),2人之間有邊他們有共同的語言.ACEGFDBA是一條哈密頓回路，按此順序就坐即可.ABCDEFG2023/6/303015.2.4應(yīng)用舉例