【正文】 v1與 vi相鄰 ,vn與 vi1相鄰 ,于是 G′存在一條哈密爾頓回路 (v1,v2,…,vi1,vn,vn1,…,vi+1,vi,v1),但這與 G ′是最大的非哈密爾頓圖矛盾。證畢。 容易看出定理 ―7 的條件是充分的但非必要。例如 ,設(shè) G是一個(gè) n邊形 ,n＞ 5,任何兩個(gè)頂點(diǎn)的度數(shù)之和是 4,但在 G中有一條哈密爾頓回路。 第 8章 圖論 推論 ―7 在簡單無向圖中 ,若每一頂點(diǎn)的度 數(shù) ,則該圖是哈密爾頓圖。 在有向圖中 ,也可類似地定義出哈密爾頓有向回路和哈密爾頓有向路徑 ,但結(jié)論不全相似 ,限于篇幅不詳述了 ,現(xiàn)在介紹一個(gè)與哈密爾頓回路有聯(lián)系的問題 —— 巡回售貨員問題 。 1 ( 3 )2 nn??第 8章 圖論 一個(gè)售貨員希望去訪問 n個(gè)城市的每一個(gè) ,開始和結(jié)束于 v1城市。每兩城市間都有一條直接通路 ,我們記 vi城市到 vj城市的距離為 W(i,j),問題是去設(shè)計(jì)一個(gè)算法 ,它將找出售貨員能采取的最短路徑。 這個(gè)問題用圖論術(shù)語敘述就是 :G=〈 V,E,W〉 是 n個(gè)頂點(diǎn)的無向完全圖 ,這里 W是從 E到正實(shí)數(shù)集的一個(gè)函數(shù) ,對在 V中任意三點(diǎn) vi,vj,vk滿足 W(i,j)+W(j,k)≥W(i,k) 試求出賦權(quán)圖上的最短哈密爾頓回路 。 第 8章 圖論 至今未找出有效的方法 ,但已找到了若干近似算法 ,現(xiàn)介紹其一 ——最鄰近算法 ,它為巡回售貨員問題得出一個(gè)近似解。 (1)選任意點(diǎn)作為始點(diǎn) ,找出一個(gè)與始點(diǎn)最近的點(diǎn) ,形成一條邊的初始路徑。然后用第 (2)步方法逐點(diǎn)擴(kuò)充這條路徑。 (2)設(shè) x表示最新加到這條路徑上的點(diǎn) ,從不在路徑上的所有點(diǎn)中 ,選一個(gè)與 x最鄰近的點(diǎn) ,把連接 x與此點(diǎn)的邊加到這條路徑中。重復(fù)這一步 ,直至 G中所有頂點(diǎn)包含在路徑中。 第 8章 圖論 圖 ―15 第 8章 圖論 (3)把始點(diǎn)和最后加入的頂點(diǎn)之間的邊放入 ,這樣就得出一個(gè)回路 。 例如 ,對于圖 ―15( a)所示的圖 ,如果我們從 a點(diǎn)開始 ,根據(jù)最鄰近算法構(gòu)造一個(gè)哈密爾頓回路 ,過程如圖 (b)到 (e)所示 ,所得回路的總距離是 44, 其實(shí)圖 ―15( a)的最小哈密爾頓回路應(yīng)如 (f)所示 ,總距離是 43。 第 8章 圖論 二部圖 定義 ― 1若無向圖 G=〈 V,E〉 的頂點(diǎn)集合 V可 以劃分成兩個(gè)子集 X和 Y,使 G中的 每一條邊 e的一個(gè)端點(diǎn)在 X中 ,另一個(gè)端點(diǎn)在 Y中 ,則稱 G為二部圖或偶圖 。 二部圖可記為 G=〈 X,E,Y〉 ,X和 Y稱為互補(bǔ)結(jié)點(diǎn)子集 。 由定義可知 ,二部圖不會(huì)有自回路 。 第 8章 圖論 定義 ―2 二部圖 G=〈 X,E,Y〉 中 ,若 X的每一 頂點(diǎn)都與 Y的每一頂點(diǎn)鄰接 ,則稱 G為完全二部圖 ,記為Km,n,這里 m=｜ X｜ ,n=｜ Y｜。 下圖給出 K2,4和 K3,3的圖示。 第 8章 圖論 定理 ―1 無向圖 G=〈 V,E〉 為二部圖的充分必 要條件為 G中所有回路的長度均為偶數(shù)。 定義 ―3 給定一個(gè)二部圖 G=〈 X,E,Y〉 ,如果 E 的子集 M中的邊無公共端點(diǎn) ,則稱 M為二部圖 G的一個(gè)匹配。含有最多邊數(shù)的匹配稱為 G的最大匹配。 例如 ,下圖中 ,M={(x1,y5),(x3,y1),(x4,y3)}是 G的一個(gè)匹配 。 求最大匹配要應(yīng)用交替鏈概念 ,其定義如下 。 第 8章 圖論 定義 ―4 如果二部圖 G中的一條鏈由不屬于匹 配 M的邊和屬于 M的邊交替組成 ,且鏈的兩端點(diǎn)不是 M中邊的端點(diǎn) ,那么稱此鏈為 G中關(guān)于匹配 M的交替鏈。 例如 ,下圖中的 (x2,y1,x3,y4)是交替鏈 。 第 8章 圖論 交替鏈可用標(biāo)記法找出 ,標(biāo)記法的過程如下 : 首先把 X中所有不是 M的邊的端點(diǎn)用 ()加以標(biāo)記 ,然后交替進(jìn)行以下所述的過程 Ⅰ 和 Ⅱ 。 Ⅰ .選一個(gè) X的新標(biāo)記過的結(jié)點(diǎn) ,比如說 xi,用 (xi)標(biāo)記不通過在 M中的邊與 xi鄰接且未標(biāo)記過的 Y的所有結(jié)點(diǎn)。對所有 X的新標(biāo)記過的結(jié)點(diǎn)重復(fù)這一過程。 Ⅱ .選一個(gè) Y的新標(biāo)記過的結(jié)點(diǎn) ,比如說 yi,用 (yi)標(biāo)記通過 M的邊與 yi鄰接且未標(biāo)記過的 X的所有結(jié)點(diǎn)。對所有 Y的新標(biāo)記過結(jié)點(diǎn)重復(fù)這一過程。 第 8章 圖論 例如 ,在下圖中 ,可用如下標(biāo)記過程 : (1) 把 x’2標(biāo)記 (*)。 (2) 從 x2出發(fā) ,應(yīng)用過程 Ⅰ ,把 y1和 y3標(biāo)記 (x2)。 (3)從 y1出發(fā) ,應(yīng)用過程 Ⅱ ,把 x3標(biāo)記 (y1)。從 y3出發(fā) ,應(yīng)用過程 Ⅱ ,把 x4標(biāo)記 (y3)。 (4)從 x3出發(fā) ,應(yīng)用過程 Ⅰ ,把 y4標(biāo)記 (x3),因 y4不是 M中邊的端點(diǎn) ,說明已找到了一條交替鏈 ,即 (x2,y1,x3,y4)。 第 8章 圖論 在二部圖 G中 ,如果能找出一條關(guān)于匹配 M的交替鏈 γ,則把 γ中屬于 M的邊從 M中刪去 ,而把 γ中不屬于 M的邊添到 M中 ,得到一新集合 M′,此 M′也是 G的匹配。這是因?yàn)樘砣氲倪呑陨聿幌嘟?,又不與 M中不屬于 γ的邊相交。例如在圖 ―2 中作這樣變換后 ,所得的 M′(用粗黑線標(biāo)出 )如圖 ―3 所示。但 M′比 M多一條邊。因此 ,反復(fù)進(jìn)行這樣的過程 ,直至找不出關(guān)于 M的交替鏈為止 ,就可崐求出 G的最大匹配 ,即 M。 第 8章 圖論 圖 ―3 第 8章 圖論 例 1求出圖 ― 4中的二部圖的最大匹配 。 解步驟 、 操作內(nèi)容及 M情況 (1)置 M為 M= (2) 找出一條邊的交替鏈 (x2,y2) M={(x2,y2)} (3)找出一條邊的交替鏈 (x3,y3) M={(x2,y2),(x3,y3)} (4)找出一條邊的交替鏈 (x4,y4) M={(x2,y2),(x3,y3),(x4,y4)} ? ?第 8章 圖論 (5)用標(biāo)記法找出交替鏈 (x1,y3,x3,y2,x2,y1),進(jìn)行變換得 M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}。 (6)再用標(biāo)記法找交替鏈。但已找不到交替鏈。所以M={(x1,y3),(x3,y2),(x2,y1),(x4,y4)}就是所求的最大匹配。