離散數學—圖論128版-資料下載頁

　　

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