離散數(shù)學(xué)第七章

7.4歐拉圖與哈密爾頓圖7.4 歐拉圖與漢密爾頓圖 哥尼斯堡七橋問題： 18世紀(jì)在哥尼斯堡城(今俄羅斯加里寧格勒)的普萊格爾河上有7座橋，將河中的兩個島和河岸連結(jié)，如圖1所示。城中的居民經(jīng)常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地看成A、B、C、D，4個點，7座橋表示成7條連接這4個點的線，如圖所示。于是“七橋問題”就等價于圖中所畫圖形的一筆畫問題了。歐拉注意到，每個點如果有進(jìn)去的邊就必須有出來的邊，從而每個點連接的邊數(shù)必須有偶數(shù)個才能完成一筆畫。上圖的每個點都連接著奇數(shù)條邊，因此不可能一筆畫出，這就說明不存在一次走遍7座橋，而每座橋只許通過一次的走法。歐拉對“七橋問題”的研究是圖論研究的開始，同時也為拓?fù)鋵W(xué)的研究提供了一個初等的例子。一、基本概念：1、歐拉圖：給定無孤立結(jié)點圖G，若存在一條路，經(jīng)過圖中每邊一次且僅一次，該條路稱為歐拉路；若存在一條回路，經(jīng)過圖中每邊一次且僅一次，該回路稱為歐拉回路。 具有歐拉回路的圖稱為歐拉圖。v2v3v4v1C（V1、V2、V3、V1、V4、V3）定理1：無向圖G有一條歐拉路，當(dāng)且僅當(dāng)G是連通的，且有零個或兩個奇數(shù)度結(jié)點。v2v3v4v1推論：給定無向連通圖G，G是歐拉圖，當(dāng)且僅當(dāng)G是連通的且圖中每個結(jié)點都是偶數(shù)度結(jié)點。一筆畫問題與七橋問題類似的還有一筆畫的判別問題，要判定一個圖是否可一筆畫出，有兩種情況：一是從圖G中某一結(jié)點出發(fā)，經(jīng)過圖中的每一邊一次且僅一次到達(dá)另一結(jié)點；另一種情況是從G的某個結(jié)點出發(fā)，經(jīng)過G的每一邊一次且僅一次再回到該結(jié)點。 上述兩種情況分別可由歐拉路和歐拉回路的判定條件予以解決。定義：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）。定理2：有向圖G具有一條單向歐拉回路，當(dāng)且僅當(dāng)是連通的，且每個結(jié)點入度等于出度。一個有向圖G中具有單向歐拉路，當(dāng)且僅當(dāng)它是連通的，而且除兩個結(jié)點外，每個結(jié)點的入度等于出度，但這兩個結(jié)點中，一個結(jié)點的入度比出度小1，一個結(jié)點的入度比出度大1。有向圖中歐拉圖例：從圖中找一條歐拉路。解奇數(shù)度頂點是:v1和v9。{v1,v2}和{v4,v6}是橋。L=v1,v2,v3,v4,v5,v2,v4,v6,v7,v8,v9,v10,v6,v8,v10,v7,v9是一條歐拉路。歐拉回路問題既是一個有趣的游戲問題,又是一個有實用價值的問題。郵遞員一般的郵遞路線是需要遍歷某些特定的街道,理想地,他應(yīng)該走一條歐拉路,即不重復(fù)地走遍圖中的每一條邊。一般郵遞路線感興趣的是圖中的邊。但有的郵遞任務(wù)是聯(lián)系某些特定的收發(fā)點,不要求走遍每一條邊,只要求不重復(fù)地遍歷圖中的每一個頂點,此時感興趣的是圖中的頂點,這就是下面研究的漢密爾頓圖。1859年,愛爾蘭數(shù)學(xué)家漢密爾頓(Halmiton)提出一個“周游世界”的游戲,它把圖(a)所示的正十二面體的二十個頂點當(dāng)作是地球上的二十個城市,要求旅游者從某個城市出發(fā),沿棱走過每個城市一次且僅一次,最后回到出發(fā)點。(b)圖中粗線所構(gòu)成的回路就是問題的答案漢密爾頓圖ab二、漢密爾頓圖1、定義：給定圖G，若存在一條路，經(jīng)過圖中的每個結(jié)點恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經(jīng)過圖中的每個結(jié)點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。例：(a)存在漢密爾頓回路,(a)是漢密爾頓圖。(b)存在漢密爾頓路但不存在漢密爾頓回路,(b)不是漢密爾頓圖。(c)不存在漢密爾頓路且不存在漢密爾頓回路,(c)不是漢密爾頓圖。（a）（b）（c）歐拉圖、歐拉回路和漢密爾頓圖、漢密爾頓回路之間的區(qū)別。(1)歐拉回路是一條閉跡,而漢密爾頓圖是一個圈。閉跡：各邊全不相同的回路。圈：除終點與始點外，各結(jié)點全不相同的回路。(2)歐拉圖遍歷邊,而漢密爾頓圖遍歷頂點。聯(lián)系它們之間幾乎沒有什么聯(lián)系。 有的圖只是歐拉圖， 有的圖只是漢密爾頓圖, 有的圖既是歐拉圖又是漢密爾頓圖, 有的圖則兩者皆不是。雖然