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