【正文】 ,vk,…,vk,…,v2),則刪去從 vk到 vk的這些邊 ,它仍是從 v1到 v2的路徑 ,如此反復(fù)地進(jìn)行直至 (v1,…,vi,…,v2)中沒(méi)有重復(fù)結(jié)點(diǎn)為止。 定義 ― 3在圖 G=〈 V,E〉 中 ,從結(jié)點(diǎn) vi到 vj最短路徑的長(zhǎng)度叫從 vi到 vj的距離 ,記為 d(vi,vj)。 (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。 定義 ―5 在無(wú)向圖 G中 ,如果任兩結(jié)點(diǎn)可達(dá) ,則稱(chēng)圖G是連通的 。如果在任兩結(jié)點(diǎn)偶對(duì)中 ,兩結(jié)點(diǎn)都互相可達(dá) ,則稱(chēng)圖 G是強(qiáng)連通的 。 第 8章 圖論 定義 ―7 在有向圖 G=〈 V,E〉 中 ,G′是 G的子 圖 ,若 G′是強(qiáng)連通的 (單向連通的 ,弱連通的 ),沒(méi)有包含 G′的更大子圖 G″是強(qiáng)連通的 (單向連通的 ,弱連通的 ),則稱(chēng)G′是 G的強(qiáng)分圖 (單向分圖 ,弱分圖 )。圖 G中從結(jié)點(diǎn) u到結(jié)點(diǎn) v的距離記為 d(u,v),定義為 min{W(P)|P為 G中從 u到 v的路徑 } ∞ 當(dāng)從 u到 v不可達(dá)時(shí) ( , )du ? ?? ??第 8章 圖論 本小節(jié)主要討論在一個(gè)賦權(quán)的簡(jiǎn)單連通無(wú)向圖 G=〈 V,E,W〉 中 ,求一結(jié)點(diǎn) a(稱(chēng)為源點(diǎn) )到其它結(jié)點(diǎn) x的最短路徑的長(zhǎng)度 ,通常稱(chēng)它為單源問(wèn)題。 (3)置 S為 S∪ {x},置 T為 T{x},若 T= ,則停止 ,否則再重復(fù) 2。若另有一條含有 T中另外結(jié)點(diǎn)的更短通路 ,不妨設(shè)這個(gè)通路中第一個(gè)屬于 T{x}的結(jié)點(diǎn)是 t1,于是 D(t1)＜ D(x),但這與題設(shè)矛盾。設(shè) x是 T中 D值最小的一個(gè)結(jié)點(diǎn) ,記 S′=S∪ ｛ x},T′=T{x},令 D′(t)表示 T′中結(jié)點(diǎn) t的 D值 ,則 D′(t)=min［ D(t),D(x)+W(x,t)］ 現(xiàn)分情況證明上式 。 因?yàn)?D(v1)=2是 T中最小的 D值 ,所以選 x=v1。 ?第 8章 圖論 圖 ―7 第 8章 圖論 表 ―1 第 8章 圖論 歐拉路徑和歐拉回路 哥尼斯堡 (Konigsberg,現(xiàn)加里寧格勒 )位于普雷格爾(Pregel)河畔 ,河中有兩島。 第 8章 圖論 不難看出 ,如果用結(jié)點(diǎn)代表陸地 ,用邊代表橋 ,哥尼斯堡七橋問(wèn)題就等價(jià)在于圖 ―8( b)中找到這樣一條路徑 ,它穿程每條邊一次且僅一次。因此 ,下邊討論歐拉路徑有關(guān)問(wèn)題時(shí)均假定圖是連通的。因此 ,除路徑的兩端點(diǎn)外 ,圖中任何頂點(diǎn)的次數(shù)必是偶數(shù)。我們從兩個(gè)奇數(shù)次數(shù)的頂點(diǎn)之一開(kāi)始 (若無(wú)奇數(shù)次數(shù)的頂點(diǎn) ,可從任一點(diǎn)開(kāi)始 ),構(gòu)造一條歐拉路徑。如果圖中所有邊已用這種方法畫(huà)過(guò) ,顯然 ,這就是所求的歐拉路徑。我們將這條路徑已構(gòu)造好的路徑組合成一條路徑。就是判斷一個(gè)圖形能否一筆畫(huà)成 ,實(shí)質(zhì)上就是判斷圖形是否存在歐拉路徑和歐拉回路的問(wèn)題。 第 8章 圖論 圖 ―9 第 8章 圖論 定理 ―5 一個(gè)有向連通圖具有歐拉回路 ,當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的引入次數(shù)等于引出次數(shù)。現(xiàn)以旋轉(zhuǎn)鼓設(shè)計(jì)為 例說(shuō)明布魯英序列。試問(wèn)應(yīng)如何選取這 8個(gè)扇形的材料使每轉(zhuǎn)過(guò)一個(gè)扇形都得到一個(gè)不同的二進(jìn)制信號(hào) ,即每轉(zhuǎn)一周 ,能得到 000到 111的 8個(gè)數(shù)。 哈密爾頓 ,愛(ài)爾蘭數(shù)學(xué)家 ,1859年他首先提出這一類(lèi)問(wèn)題。但 G是由 C和一些不在 C中的邊構(gòu)成的 ,CS是 GS的生成子圖 ,所以 ω(GS)≤ω(CS)≤|S| 應(yīng)用本定理可以判定某些圖不是哈密爾頓圖 ,例如 ,圖 ―12 所示的圖 ,刪去其中 3個(gè)黑點(diǎn) ,即知此圖不符合必要條件 ,因而不是哈密爾頓圖。繼續(xù)不斷地用 A標(biāo)記所有鄰接于 B的頂點(diǎn) ,用 B標(biāo)記所有鄰接于 A的頂點(diǎn) ,直到所有頂點(diǎn)標(biāo)記完 ,得到如圖 ―13( b)所示的圖 ,圖中有 3個(gè)頂點(diǎn)標(biāo) A和 5個(gè)頂點(diǎn)標(biāo) B,標(biāo)號(hào) A和 B崐相差 2個(gè) ,因此不可能存在一條哈密爾頓路徑。設(shè) G是符合題設(shè)條件 ,但不是哈密爾頓圖 ,通過(guò)把不相鄰的頂點(diǎn)加邊 ,總可得到一個(gè)最大的非哈密爾頓圖 G′。 121 1 1, , ,ki i i? ? ?? ? ?12, ki i i? ? ?第 8章 圖論 圖 ―14 第 8章 圖論 v1與 vi相鄰 ,vn與 vi1相鄰 ,于是 G′存在一條哈密爾頓回路 (v1,v2,…,vi1,vn,vn1,…,vi+1,vi,v1),但這與 G ′是最大的非哈密爾頓圖矛盾。 第 8章 圖論 推論 ―7 在簡(jiǎn)單無(wú)向圖中 ,若每一頂點(diǎn)的度 數(shù) ,則該圖是哈密爾頓圖。 這個(gè)問(wèn)題用圖論術(shù)語(yǔ)敘述就是 :G=〈 V,E,W〉 是 n個(gè)頂點(diǎn)的無(wú)向完全圖 ,這里 W是從 E到正實(shí)數(shù)集的一個(gè)函數(shù) ,對(duì)在 V中任意三點(diǎn) vi,vj,vk滿(mǎn)足 W(i,j)+W(j,k)≥W(i,k) 試求出賦權(quán)圖上的最短哈密爾頓回路 。 (2)設(shè) x表示最新加到這條路徑上的點(diǎn) ,從不在路徑上的所有點(diǎn)中 ,選一個(gè)與 x最鄰近的點(diǎn) ,把連接 x與此點(diǎn)的邊加到這條路徑中。 第 8章 圖論 二部圖 定義 ― 1若無(wú)向圖 G=〈 V,E〉 的頂點(diǎn)集合 V可 以劃分成兩個(gè)子集 X和 Y,使 G中的 每一條邊 e的一個(gè)端點(diǎn)在 X中 ,另一個(gè)端點(diǎn)在 Y中 ,則稱(chēng) G為二部圖或偶圖 。 下圖給出 K2,4和 K3,3的圖示。 例如 ,下圖中 ,M={(x1,y5),(x3,y1),(x4,y3)}是 G的一個(gè)匹配 。 第 8章 圖論 交替鏈可用標(biāo)記法找出 ,標(biāo)記法的過(guò)程如下 : 首先把 X中所有不是 M的邊的端點(diǎn)用 ()加以標(biāo)記 ,然后交替進(jìn)行以下所述的過(guò)程 Ⅰ 和 Ⅱ 。對(duì)所有 Y的新標(biāo)記過(guò)結(jié)點(diǎn)重復(fù)這一過(guò)程。從 y3出發(fā) ,應(yīng)用過(guò)程 Ⅱ ,把 x4標(biāo)記 (y3)。例如在圖 ―2 中作這樣變換后 ,所得的 M′(用粗黑線(xiàn)標(biāo)出 )如圖 ―3 所示。 解步驟 、 操作內(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)}。