【正文】 系的問題 —— 巡回售貨員問題 。 1 ( 3 )2 nn??第 8章 圖論 一個售貨員希望去訪問 n個城市的每一個 ,開始和結(jié)束于 v1城市。每兩城市間都有一條直接通路 ,我們記 vi城市到 vj城市的距離為 W(i,j),問題是去設計一個算法 ,它將找出售貨員能采取的最短路徑。 這個問題用圖論術語敘述就是 :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)設 x表示最新加到這條路徑上的點 ,從不在路徑上的所有點中 ,選一個與 x最鄰近的點 ,把連接 x與此點的邊加到這條路徑中。重復這一步 ,直至 G中所有頂點包含在路徑中。 第 8章 圖論 圖 ―15 第 8章 圖論 (3)把始點和最后加入的頂點之間的邊放入 ,這樣就得出一個回路 。 例如 ,對于圖 ―15( a)所示的圖 ,如果我們從 a點開始 ,根據(jù)最鄰近算法構(gòu)造一個哈密爾頓回路 ,過程如圖 (b)到 (e)所示 ,所得回路的總距離是 44, 其實圖 ―15( a)的最小哈密爾頓回路應如 (f)所示 ,總距離是 43。 第 8章 圖論 二部圖 從本節(jié)起將討論一些特殊的圖 ,首先討論二部圖 。 定義 ―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｜。 圖 ―1 給出 K2,4和 K3,3的圖示。 圖 ―1 第 8章 圖論 定理 ―1 無向圖 G=〈 V,E〉 為二部圖的充分必 要條件為 G中所有回路的長度均為偶數(shù)。 證必要性。設 G是具有互補結(jié)點子集 X和 Y的二部圖。C是 G中任一回路 C:(v0,v1,v2,…,vk,v0) 不妨設 v0∈ X,則 v0,v2,v4,…∈ X,v1,v3,v5,…∈ Y,k必為奇數(shù) ,不然 ,不存在邊 (vk,v0)。 C中共有 k+1條邊 ,故 C是偶數(shù)長度的回路 。 第 8章 圖論 充分性。設 G是連通圖 ,否則對 G的每個連通分圖進行證明。設 G=〈 V,E〉 只含有偶數(shù)長度的回路 ,定義互補結(jié)點子集 X和 Y如下 : 任取一個頂點 v0,v0∈ V,取 X={v｜從 v0到 v的距離是偶數(shù) } Y=VX 第 8章 圖論 定義 ―3 給定一個二部圖 G=〈 X,E,Y〉 ,如果 E 的子集 M中的邊無公共端點 ,則稱 M為二部圖 G的一個匹配。含有最多邊數(shù)的匹配稱為 G的最大匹配。 例如 ,圖 ― 2中 ,M={(x1,y5),(x3,y1),(x4,y3)}是 G的一個匹配 。 求最大匹配要應用交替鏈概念 ,其定義如下 。 第 8章 圖論 定義 ―4 如果二部圖 G中的一條鏈由不屬于匹 配 M的邊和屬于 M的邊交替組成 ,且鏈的兩端點不是 M中邊的端點 ,那么稱此鏈為 G中關于匹配 M的交替鏈。 例如 ,圖 ― 2中的 (x2,y1,x3,y4)是交替鏈 。 最短的交替鏈是由一條邊組成 ,該邊的兩端點不是 M中邊的端點 。 第 8章 圖論 圖 ―2 第 8章 圖論 交替鏈可用標記法找出 ,標記法的過程如下 : 首先把 X中所有不是 M的邊的端點用 ()加以標記 ,然后交替進行以下所述的過程 Ⅰ 和 Ⅱ 。 Ⅰ .選一個 X的新標記過的結(jié)點 ,比如說 xi,用 (xi)標記不通過在 M中的邊與 xi鄰接且未標記過的 Y的所有結(jié)點。對所有 X的新標記過的結(jié)點重復這一過程。 Ⅱ .選一個 Y的新標記過的結(jié)點 ,比如說 yi,用 (yi)標記通過 M的邊與 yi鄰接且未標記過的 X的所有結(jié)點。對所有 Y的新標記過結(jié)點重復這一過程。 第 8章 圖論 例如 ,在圖 ― 2中 ,可用如下標記過程 : (1) 把 x’2標記 (*)。 (2) 從 x2出發(fā) ,應用過程 Ⅰ ,把 y1和 y3標記 (x2)。 (3)從 y1出發(fā) ,應用過程 Ⅱ ,把 x3標記 (y1)。從 y3出發(fā) ,應用過程 Ⅱ ,把 x4標記 (y3)。 (4)從 x3出發(fā) ,應用過程 Ⅰ ,把 y4標記 (x3),因 y4不是 M中邊的端點 ,說明已找到了一條交替鏈 ,即 (x2,y1,x3,y4)。 第 8章 圖論 在二部圖 G中 ,如果能找出一條關于匹配 M的交替鏈 γ,則把 γ中屬于 M的邊從 M中刪去 ,而把 γ中不屬于 M的邊添到 M中 ,得到一新集合 M′,此 M′也是 G的匹配。這是因為添入的邊自身不相交 ,又不與 M中不屬于 γ的邊相交。例如在圖 ―2 中作這樣變換后 ,所得的 M′(用粗黑線標出 )如圖 ―3 所示。但 M′比 M多一條邊。因此 ,反復進行這樣的過程 ,直至找不出關于 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)}就是所求的最大匹配。 圖 ―4