【正文】 定理 ―4 無(wú)向連通圖 G具有一條歐拉路徑當(dāng)且 僅當(dāng) G具有零個(gè)或兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)。 證必要性。如果圖具有歐拉路徑 ,那么順著這條路徑畫(huà)出的時(shí)候 ,每次碰到一個(gè)頂點(diǎn) ,都需通過(guò)關(guān)聯(lián)于這個(gè)頂點(diǎn)的兩條邊 ,并且這兩條邊在以前未畫(huà)過(guò)。因此 ,除路徑的兩端點(diǎn)外 ,圖中任何頂點(diǎn)的次數(shù)必是偶數(shù)。如果歐拉路徑的兩端點(diǎn)不同 ,那么它們就是僅有的兩個(gè)奇數(shù)頂點(diǎn) ,如果它們是重合的 ,那么所有頂點(diǎn)都有偶數(shù)次數(shù) ,并且這條歐拉路徑成為一條歐拉回路。因此必要性得證。 第 8章 圖論 充分性。我們從兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)之一開(kāi)始 (若無(wú)奇數(shù)次數(shù)的頂點(diǎn) ,可從任一點(diǎn)開(kāi)始 ),構(gòu)造一條歐拉路徑。以每條邊最多畫(huà)一次的方式通過(guò)圖中的邊。對(duì)于偶數(shù)次數(shù)的頂點(diǎn) ,通過(guò)一條邊進(jìn)入這個(gè)頂點(diǎn) ,總可通過(guò)一條未畫(huà)過(guò)的邊離開(kāi)這個(gè)頂點(diǎn)。因此 ,這樣的構(gòu)造過(guò)程一定以到達(dá)另一個(gè)奇數(shù)次數(shù)頂點(diǎn)而告終 (若無(wú)奇數(shù)次數(shù)的頂點(diǎn) ,則以回到原出發(fā)點(diǎn)而告終 )。如果圖中所有邊已用這種方法畫(huà)過(guò) ,顯然 ,這就是所求的歐拉路徑。如果圖中不是所有邊被畫(huà)過(guò) ,我們?nèi)サ粢旬?huà)過(guò) 的邊 ,得到由剩下邊組成的一個(gè)子圖 ,這個(gè)子圖的頂點(diǎn)次數(shù)全是偶數(shù)。 第 8章 圖論 并且因?yàn)樵瓉?lái)的圖是連通的 ,因此 ,這個(gè)子圖必與我們已畫(huà)過(guò)的路徑在一個(gè)點(diǎn)或多個(gè)點(diǎn)相接。由這些頂點(diǎn)中的一個(gè)開(kāi)始 ,我們?cè)偻ㄟ^(guò)邊構(gòu)造路徑 ,因?yàn)轫旤c(diǎn)次數(shù)全是偶數(shù) ,因此 ,這條路徑一定最終回到起點(diǎn)。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。如果必要 ,這一論證重復(fù)下去 ,直到我們得到一條通過(guò)圖中所有邊的路徑 ,即歐拉路徑。因此充分性得證。 第 8章 圖論 例 2 (a)一筆畫(huà)問(wèn)題。就是判斷一個(gè)圖形能否一筆畫(huà)成 ,實(shí)質(zhì)上就是判斷圖形是否存在歐拉路徑和歐拉回路的問(wèn)題。例如 ,圖 ―9( a)和 (b)均可一筆畫(huà)成 ,因?yàn)榉洗嬖跉W拉路徑和歐拉回路條件。 第 8章 圖論 (b)我們想知道是否可能將 28塊不同的多米諾骨牌排成一個(gè)圓形 ,使得在這個(gè)排列中 ,每?jī)蓧K相鄰的多米諾骨牌其相鄰的兩個(gè)半面是相同的。我們構(gòu)造一個(gè)具有 7個(gè)頂點(diǎn)的圖 ,這些頂點(diǎn)對(duì)應(yīng)于空白、 5和 6,在每?jī)蓚€(gè)頂點(diǎn)之間都有一條邊 ,我們把這條邊當(dāng)作一塊多米諾骨牌 ,并且把這條邊相關(guān)聯(lián)的兩 個(gè)頂點(diǎn)當(dāng)作它的兩個(gè)半面。 第 8章 圖論 圖 ―9 第 8章 圖論 定理 ―5 一個(gè)有向連通圖具有歐拉回路 ,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù)。一個(gè)有向連通圖具有歐拉路徑 ,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù) ,可能有兩個(gè)頂點(diǎn)是例外 ,其中一個(gè)頂點(diǎn)的引入次數(shù)比它的引出次數(shù)大 1,另一個(gè)頂點(diǎn)的引入次數(shù)比它的引出崐次數(shù)小 1。證明是類(lèi)似的 ,不重復(fù)。 第 8章 圖論 例 3布魯英 (DeBruijn)序列?，F(xiàn)以旋轉(zhuǎn)鼓設(shè)計(jì)為 例說(shuō)明布魯英序列。 旋轉(zhuǎn)鼓的表面分成 8塊扇形 ,如圖 ―10 所示。圖中陰影區(qū)表示用導(dǎo)電材料制成 ,空白區(qū)用絕緣材料制成 ,終端 a、 b和 c是接地或不是接地分別用二進(jìn)制信號(hào) 0或 1表示。因此 ,鼓的位置可用二進(jìn)制信號(hào)表示。試問(wèn)應(yīng)如何選取這 8個(gè)扇形的材料使每轉(zhuǎn)過(guò)一個(gè)扇形都得到一個(gè)不同的二進(jìn)制信號(hào) ,即每轉(zhuǎn)一周 ,能得到 000到 111的 8個(gè)數(shù)。 第 8章 圖論 圖 ―10 第 8章 圖論 圖 ―10 第 8章 圖論 哈密爾頓路徑與哈密爾頓回路 在無(wú)向圖 G=〈 V,E〉 中 ,穿程于 G的每個(gè)結(jié)點(diǎn)一次且僅一次的路徑稱(chēng)為哈密爾頓路徑。穿程于 G的每個(gè)結(jié)點(diǎn)一次且僅一次的回路稱(chēng)為哈密爾頓回路。具有哈密爾頓回路的圖稱(chēng)為哈密爾頓圖。 哈密爾頓 ,愛(ài)爾蘭數(shù)學(xué)家 ,1859年他首先提出這一類(lèi)問(wèn)題。它的問(wèn)題如下 : 如何沿 12面體的棱線(xiàn) ,通過(guò)每個(gè)角一次且僅一次 ?(稱(chēng)為環(huán)游全世界游戲 。 ) 第 8章 圖論 圖 ―11 第 8章 圖論 定理 ―6 若 G=〈 V,E〉 是哈密爾頓圖 ,則對(duì) V的每個(gè)非空真子集 S均成立 : ω(GS)≤｜ S｜ 這里 |S|表示 S中的頂點(diǎn)數(shù) ,ω(GS)表示 G刪去頂點(diǎn)集 S后得到的圖的連通分圖個(gè)數(shù)。 證 設(shè) C是圖的一條哈密爾頓回路 ,則對(duì)于 V的任一非空真子集 S有 ω(CS)≤|S| 第 8章 圖論 這里 ω(CS),是 C刪去子集 S后得到的圖的分圖個(gè)數(shù)。但 G是由 C和一些不在 C中的邊構(gòu)成的 ,CS是 GS的生成子圖 ,所以 ω(GS)≤ω(CS)≤|S| 應(yīng)用本定理可以判定某些圖不是哈密爾頓圖 ,例如 ,圖 ―12 所示的圖 ,刪去其中 3個(gè)黑點(diǎn) ,即知此圖不符合必要條件 ,因而不是哈密爾頓圖。但一般要考察多個(gè)真子集 ,應(yīng)用不方便 ,例 4給出了一種較簡(jiǎn)便的否定一個(gè)圖是哈密爾頓圖的方法 ,但也不是通用的。 第 8章 圖論 圖 ―12 第 8章 圖論 例 4 證明圖 ― 13(a)中的圖沒(méi)有哈密爾頓路徑 。 證用 A標(biāo)記頂點(diǎn) a,所有與 A鄰接的頂點(diǎn)標(biāo)記為 B。繼續(xù)不斷地用 A標(biāo)記所有鄰接于 B的頂點(diǎn) ,用 B標(biāo)記所有鄰接于 A的頂點(diǎn) ,直到所有頂點(diǎn)標(biāo)記完 ,得到如圖 ―13( b)所示的圖 ,圖中有 3個(gè)頂點(diǎn)標(biāo) A和 5個(gè)頂點(diǎn)標(biāo) B,標(biāo)號(hào) A和 B崐相差 2個(gè) ,因此不可能存在一條哈密爾頓路徑。 第 8章 圖論 圖 ―13 第 8章 圖論 定理 ―6 中的條件不是充分的 ,圖 ―5 中給出的彼得森圖 ,它對(duì)任意 SV都滿(mǎn)足 ω(GS)≤|S|,但不是哈密爾頓圖。 定理 ―7 設(shè) G=〈 V,E〉 是具有 n個(gè)頂點(diǎn)的簡(jiǎn)單無(wú)向圖 ,若在 G中每一對(duì)頂點(diǎn)的次數(shù)之和大于等于 n,則在 G中存在一條哈密爾頓回路。 第 8章 圖論 證用反證法。設(shè) G是符合題設(shè)條件 ,但不是哈密爾頓圖 ,通過(guò)把不相鄰的頂點(diǎn)加邊 ,總可得到一個(gè)最大的非哈密爾頓圖 G′。由于 G′是最大的非哈密爾頓圖 ,所以給G′的不相鄰的頂點(diǎn) u和 v加上邊 (u,v),這時(shí)有 (v1,v2,…,vn,v1)這條哈密爾頓回路 ,不妨設(shè) v1=u,vn=v,因?yàn)榛芈繁亟?jīng)過(guò)(u,v)。于是必存在兩個(gè)相鄰的頂點(diǎn) vi和 vi1使 v1與 vi,vi1與vn相鄰 ,如圖 ―14 所示。 若不然 ,設(shè)在 G′中 v1與 相鄰 ,而 vn與 都不相鄰 ,則 deg(vn)≤nk1,這樣 deg(v1)+deg(vn)≤n1＜ n,與題設(shè)不符。 121 1 1, , ,ki i i? ? ?? ? ?12, ki i i? ? ?第 8章 圖論 圖 ―14 第 8章 圖論