【文章內(nèi)容簡介】 2,3},{e1,e2,e3}〉 ,〈 {4},φ 〉 ,〈 {5},φ 〉 , 〈 ｛ 6｝ ,φ 〉 ,〈 ｛ 7,8｝ ,{e7,e8}〉 ｝ 第 8章 圖論 單向分圖集合是 : {〈 {1,2,3,4,5},{e1,e2,e3,e4,e5}〉 ,〈 {6,5},{e6}〉 , 〈 ｛ 7,8｝ ,{e7,e8}〉 ｝ 弱分圖集合是 : {〈 {1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉 , 〈 ｛ 7,8｝ ,{e7,e8}〉 ｝ 第 8章 圖論 賦權(quán)圖中的最短路徑 設(shè) G=〈 V,E,W〉 是個賦權(quán)圖 ,W是從 E到正實數(shù)集合的函 數(shù) ,邊［ i,j］的權(quán)記為 W(i,j),稱為邊的長度。若 i和 j 之間沒有邊 ,那么 W(i,j)=∞ 。路徑 P的長度定義為路徑 中邊的長度之和 ,記為 W(P)。圖 G中從結(jié)點 u到結(jié)點 v的 距離記為 d(u,v),定義為 ? min{W(P)|P為 G中從 u到 v的路徑 } ? ∞ 當(dāng)從 u到 v不可達時 ( , )du ? ?? ??第 8章 圖論 ? 本小節(jié)主要討論在一個賦權(quán)的簡單連通無向圖 ? G=〈 V,E,W〉 中 ,求一結(jié)點 a(稱為源點 )到其它結(jié)點 x的最短路徑的長度 ,通常稱它為單源問題。下面介紹 1959 年迪克斯特拉 ()提出的單源問題的算法 ,其要點如下 : ? (1) 把 V分成兩個子集 S和 T。 初始時 ,S={a},T=VS。 ? (2) 對 T中每一元素 t計算 D(t),根據(jù)D(t)值找出 T中距 a最短的一結(jié)點 x,寫出 a到 x的最短路徑的長度 D(x)。 ? (3)置 S為 S∪ {x},置 T為 T{x},若 T= ,則停止 ,否則再重復(fù) 2。 ?第 8章 圖論 ? 算法中步驟 (1)和 (3)是清楚的 ,現(xiàn)在對 2給以說明 。 ? D(t)表示從 a到 t的不包含 T中其它結(jié)點的最短通路的長度 ,但 D(t)不一定是從 a到 t的距離 ,因為從 a到 t可能有包含 T中另外結(jié)點的更短通路。 ? 首先我們證明 “ 若 x是 T中具有最小 D值的結(jié)點 ,則 D(x)是從 a到 x的距離 ” ,用反證法。若另有一條含有 T中另外結(jié)點的更短通路 ,不妨設(shè)這個通路中第一個屬于 T{x}的結(jié)點是 t1,于是 D(t1)＜ D(x),但這與題設(shè)矛盾?？梢娨陨蠑嘌猿闪?。 第 8章 圖論 ? 其次說明計算 D(t)的方法。初始時 ,D(t)=W(a,t),現(xiàn)在我們假設(shè)對 T中的每一個 t已計算了 D值。設(shè) x是 T中 D值最小的一個結(jié)點 ,記 S′=S∪ ｛ x},T′=T{x},令 D′(t)表示 T′中結(jié)點 t的 D值 ,則 ? D′(t)=min［ D(t),D(x)+W(x,t)］ ? 現(xiàn)分情況證明上式 。 第 8章 圖論 ? (a)如果從 a到 t有一條最短路徑 ,它不包含 T′中的其它結(jié)點 ,也不含 x點 ,則D′(t)=D(t)。 ? (b)如果從 a到 t有一條最短路徑 ,它從 a到 x不包含 T′中的結(jié)點 ,接著是邊 W(x,t),在此情況下 ,D′(t)是 D(x)+W(x,t)。 第 8章 圖論 ? 例 1 考慮圖 ―7 中的圖 ,起初 ? S={a},T={v1,v2,v3,v4},D(a)=0,D(v1)=2,D(v2)=+∞,D(v3)=+∞,D(v4)=10。 因為 D(v1)=2是 T中最小的 D值 ,所以選x=v1。 ? 置 S為 S∪ {x}={a,v1},置 T為 T{x}={v2,v3,v4}。然后計算 : ? D(v2)=min(+∞,2+3)=5 ? D(v3)=min(+∞,+∞)=+∞ ? D(v4)=min(10,2+7)=9 ? 如此類推 ,直至 T= 終止 。 整個過程概括于表 ― 1中 。 ?第 8章 圖論 圖 ―7 第 8章 圖論 表 ―1 第 8章 圖論 ? 歐拉路徑和歐拉回路 ? 哥尼斯堡 (Konigsberg,現(xiàn)加里寧格勒 )位于普雷格爾 (Pregel)河畔 ,河中有兩島。城市的各部分由 7座橋接通 ,如圖―8( a)所示。古時城中居民 熱衷于一個問題 :游人從任一地點出發(fā) ,怎樣才能做到穿過每座橋一次且僅一 次后又返回原出發(fā)地。 1736年歐拉用圖論方法解決了此問題 ,寫了第一篇圖論的論文 ,從而成為圖論的創(chuàng)始人。 第 8章 圖論 ? 不難看出 ,如果用結(jié)點代表陸地 ,用邊代表橋 ,哥尼斯堡七橋問題就等價在于圖 ―8( b)中找到這樣一條路徑 ,它穿程每條邊一次且僅一次。 ? 穿程于圖 G的每條邊一次且僅一次的路徑 ,稱為歐拉路徑。穿程于圖 G的每條邊一次且僅一次的回路 ,稱為歐拉回路 ,具有歐拉回路的圖稱為歐拉圖。 ? 顯然 ,具有歐拉路徑的圖除孤立結(jié)點外是連通的 ,而孤立結(jié)點不影響歐拉路徑 的討論。因此 ,下邊討論歐拉路徑有關(guān)問題時均假定圖是連通的。 第 8章 圖論 圖 ―8 第 8章 圖論 ? 定理 ―4 無向連通圖 G具有一條歐拉路徑當(dāng)且 僅當(dāng) G具有零個或兩個奇數(shù)次數(shù)的頂點。 ? 證必要性。如果圖具有歐拉路徑 ,那么順著這條路徑畫出的時候 ,每次碰到一個頂點 ,都需通過關(guān)聯(lián)于這個頂點的兩條邊 ,并且這兩條邊在以前未畫過。因此 ,除路徑的兩端點外 ,圖中任何頂點的次數(shù)必是偶數(shù)。如果歐拉路徑的兩端點不同 ,那么它們就是僅有的兩個奇數(shù)頂點 ,如果它們是重合的 ,那么所有頂點都有偶數(shù)次數(shù) ,并且這條歐拉路徑成為一條歐拉回路。因此必要性得證。 第 8章 圖論 ? 充分性。我們從兩個奇數(shù)次數(shù)的頂點之一開始 (若無奇數(shù)次數(shù)的頂點 ,可從任一點開始 ),構(gòu)造一條歐拉路徑。以每條邊最多畫一次的方式通過圖中的邊。對于偶數(shù)次數(shù)的頂點 ,通過一條邊進入這個頂點 ,總可通過一條未畫過的邊離開這個頂點。因此 ,這樣的構(gòu)造過程一定以到達另一個奇數(shù)次數(shù)頂點而告終 (若無奇數(shù)次數(shù)的頂點 ,則以回到原出發(fā)點而告終 )。如果圖中所有邊已用這種方法畫過 ,顯然 ,這就是所求的歐拉路徑。如果圖中不是所有邊被畫過 ,我們?nèi)サ粢旬嬤^ 的邊 ,得到由剩下邊組成的一個子圖 ,這個子圖的頂點次數(shù)全是偶數(shù)。 第 8章 圖論 ? 并且因為原來的圖是連通的 ,因此 ,這個子圖必與我們已畫過的路徑在一個點或多個點相接。由這些頂點中的一個開始 ,我們再通過邊構(gòu)造路徑 ,因為頂點次數(shù)全是偶數(shù) ,因此 ,這條路徑一定最終回到起點。我們將這條路徑已構(gòu)