【正文】 發(fā)點(diǎn)而告終 )。如果圖中不是所有邊被畫過 ,我們?nèi)サ粢旬嬤^ 的邊 ,得到由剩下邊組成的一個(gè)子圖 ,這個(gè)子圖的頂點(diǎn)次數(shù)全是偶數(shù)。由這些頂點(diǎn)中的一個(gè)開始 ,我們再通過邊構(gòu)造路徑 ,因?yàn)轫旤c(diǎn)次數(shù)全是偶數(shù) ,因此 ,這條路徑一定最終回到起點(diǎn)。如果必要 ,這一論證重復(fù)下去 ,直到我們得到一條通過圖中所有邊的路徑 ,即歐拉路徑。 第 8章 圖論 ? 例 2 ? (a)一筆畫問題。例如 ,圖 ―9( a)和 (b)均可一筆畫成 ,因?yàn)榉洗嬖跉W拉路徑和歐拉回路條件。我們構(gòu)造一個(gè)具有 7個(gè)頂點(diǎn)的圖 ,這些頂點(diǎn)對應(yīng)于空白、 5和 6,在每兩個(gè)頂點(diǎn)之間都有一條邊 ,我們把這條邊當(dāng)作一塊多米諾骨牌 ,并且把這條邊相關(guān)聯(lián)的兩 個(gè)頂點(diǎn)當(dāng)作它的兩個(gè)半面。一個(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。 第 8章 圖論 ? 例 3布魯英 (DeBruijn)序列。 ? 旋轉(zhuǎn)鼓的表面分成 8塊扇形 ,如圖―10 所示。因此 ,鼓的位置可用二進(jìn)制信號(hào)表示。 第 8章 圖論 圖 ―10 第 8章 圖論 圖 ―10 第 8章 圖論 ? 哈密爾頓路徑與哈密爾頓回路 ? 在無向圖 G=〈 V,E〉 中 ,穿程于 G的每個(gè)結(jié)點(diǎn)一次且僅一次的路徑稱為哈密爾頓路徑。具有哈密爾頓回路的圖稱為哈密爾頓圖。它的問題如下 : ? 如何沿 12面體的棱線 ,通過每個(gè)角一次且僅一次 ?(稱為環(huán)游全世界游戲 。 ? 證 設(shè) C是圖的一條哈密爾頓回路 ,則對于 V的任一非空真子集 S有 ? ω(CS)≤|S| 第 8章 圖論 ? 這里 ω(CS),是 C刪去子集 S后得到的圖的分圖個(gè)數(shù)。但一般要考察多個(gè)真子集 ,應(yīng)用不方便 ,例 4給出了一種較簡便的否定一個(gè)圖是哈密爾頓圖的方法 ,但也不是通用的。 ? 證用 A標(biāo)記頂點(diǎn) a,所有與 A鄰接的頂點(diǎn)標(biāo)記為 B。 第 8章 圖論 圖 ―13 第 8章 圖論 ? 定理 ―6 中的條件不是充分的 ,圖 ―5 中給出的彼得森圖 ,它對任意 SV都滿足 ω(GS)≤|S|,但不是哈密爾頓圖。 ? 第 8章 圖論 ? 證用反證法。由于 G′是最大的非哈密爾頓圖 ,所以給 G′的不相鄰的頂點(diǎn) u和 v加上邊 (u,v),這時(shí)有 (v1,v2,…,vn,v1)這條哈密爾頓回路 ,不妨設(shè) v1=u,vn=v,因?yàn)榛芈繁亟?jīng)過 (u,v)。 若不然 ,設(shè)在 G′中 v1與 相鄰 ,而vn與 都不相鄰 ,則deg(vn)≤nk1,這樣 deg(v1)+deg(vn)≤n1＜ n,與題設(shè)不符。證畢。例如 ,設(shè) G是一個(gè) n邊形 ,n＞ 5,任何兩個(gè)頂點(diǎn)的度數(shù)之和是 4,但在 G中有一條哈密爾頓回路。 ? 在有向圖中 ,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向路徑 ,但結(jié)論不全相似 ,限于篇幅不詳述了 ,現(xiàn)在介紹一個(gè)與哈密爾頓回路有聯(lián)系的問題 —— 巡回售貨員問題 。每兩城市間都有一條直接通路 ,我們記 vi城市到 vj城市的距離為 W(i,j),問題是去設(shè)計(jì)一個(gè)算法 ,它將找出售貨員能采取的最短路徑。 第 8章 圖論 ? 至今未找出有效的方法 ,但已找到了若干近似算法 ,現(xiàn)介紹其一 ——最鄰近算法 ,它為巡回售貨員問題得出一個(gè)近似解。然后用第 (2)步方法逐點(diǎn)擴(kuò)充這條路徑。重復(fù)這一步 ,直至 G中所有頂點(diǎn)包含在路徑中。 ? 例如 ,對于圖 ―15( a)所示的圖 ,如果我們從 a點(diǎn)開始 ,根據(jù)最鄰近算法構(gòu)造一個(gè)哈密爾頓回路 ,過程如圖 (b)到 (e)所示 ,所得回路的總距離是 44, 其實(shí)圖 ―15( a)的最小哈密爾頓回路應(yīng)如 (f)所示 ,總距離是 43。 ? 定義 ―1 若無向圖 G=〈 V,E〉 的頂點(diǎn)集合 V可 以劃分成兩個(gè)子集 X和 Y,使 G中的每一條邊 e的一個(gè)端點(diǎn)在 X中 ,另一個(gè)端點(diǎn)在 Y中 ,則稱 G為二部圖或偶圖。 ? 由定義可知 ,二部圖不會(huì)有自回路 。 ? 圖 ―1 給出 K2,4和 K3,3的圖示。 ? 證必要性。 C是 G中任一回路 ? C:(v0,v1,v2,…,vk,v0) ? 不妨設(shè) v0∈ X, 則v0,v2,v4,…∈ X,v1,v3,v5,…∈ Y,k必為奇 數(shù) ,不然 ,不存在邊 (vk,v0)。 第 8章 圖論 ? 充分性。設(shè) G=〈 V,E〉只含有偶數(shù)長度的回路 ,定義互補(bǔ)結(jié)點(diǎn)子集 X和 Y如下 : ? 任取一個(gè)頂點(diǎn) v0,v0∈ V,取 ? X={v｜從 v0到 v的距離是偶數(shù) } ? Y=VX 第 8章 圖論 ? 定義 ―3 給定一個(gè)二部圖 G=〈 X,E,Y〉 ,如果 E 的子集 M中的邊無公共端點(diǎn) ,則稱 M為二部圖 G的一個(gè)匹配。 ? 例如 , 圖 ― 2中 ,M={(x1,y5),(x3,y1),(x4,y3)}是 G的一個(gè)匹配 。 第 8章 圖論 ? 定義 ―4 如果二部圖 G中的一條鏈由不屬于匹 配 M的邊和屬于 M的邊交替組成 ,且鏈的兩端點(diǎn)不是 M中邊的端點(diǎn) ,那么稱此鏈為G中關(guān)于匹配 M的交替鏈。 最短的交替鏈?zhǔn)怯梢粭l邊組成 ,該邊的兩端點(diǎn)不是 M中邊的端點(diǎn) 。 ? Ⅰ .選一個(gè) X的新標(biāo)記過的結(jié)點(diǎn) ,比如說 xi,用 (xi)標(biāo)記不通過在 M中的邊與 xi鄰接且未標(biāo)記過的 Y的所有結(jié)點(diǎn)。 ? Ⅱ .選一個(gè) Y的新標(biāo)記過的結(jié)點(diǎn) ,比如說 yi,用 (yi)標(biāo)記通過 M的邊與 yi鄰接且未標(biāo)記過的 X的所有結(jié)點(diǎn)。 第 8章 圖論 ? 例如 ,在圖 ― 2中 ,可用如下標(biāo)記過程 : ? (1) 把 x’2標(biāo)記 (*)。 ? (3)從 y1出發(fā) ,應(yīng)用過程 Ⅱ ,把 x3標(biāo)記 (y1)。 ? (4)從 x3出發(fā) ,應(yīng)用過程 Ⅰ ,把 y4標(biāo)記 (x3),因 y4不是 M中邊的端點(diǎn) ,說明已找到了一條交替鏈 ,即 (x2,y1,x3,y4)。這是因?yàn)樘砣氲倪呑陨聿幌嘟?,又不與 M中不屬于 γ的邊相交。但 M′比 M多一條邊。 第 8章 圖論 圖 ―3 第 8章 圖論 ?例 1求出圖 ― 4中的二部圖的最大匹配 。 ? (6)再用標(biāo)記法找交替鏈。所以M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}就是所求的