【文章內(nèi)容簡介】 第 8章 圖論 圖 ―2 一個無向圖或者是一個連通圖 ,如圖 ―2( a)所示 ,或者是由若干個連通分圖組成 ,如圖 ―2( b)所示。 第 8章 圖論 定理 ―3 設(shè) G是任一 (n,m)無向簡單圖 ,ω是 其分圖個數(shù) ,則 1 ( )( 1 )2n m n n? ? ?? ? ? ? ? ? 定義 ―6 在有向圖中 ,如果在任兩結(jié)點偶對中 ,至少從一個結(jié)點到另一個結(jié)點是可達的 ,則稱圖 G是單向連通的 。如果在任兩結(jié)點偶對中 ,兩結(jié)點都互相可達 ,則稱圖 G是強連通的 。如果它的底圖是連通的 ,則稱圖 G是弱連通的。 第 8章 圖論 強連通的也一定是單向連通和弱連通的 ,單向連通的一定是弱連通的 ,但其逆均不真 。 在下圖中 ,(a)是強連通的 ,(b)是單向連通的 ,(c)是弱連通的 。 第 8章 圖論 定義 ―7 在有向圖 G=〈 V,E〉 中 ,G′是 G的子 圖 ,若 G′是強連通的 (單向連通的 ,弱連通的 ),沒有包含 G′的更大子圖 G″是強連通的 (單向連通的 ,弱連通的 ),則稱G′是 G的強分圖 (單向分圖 ,弱分圖 )。 在下圖中 ,強分圖集合是 : {〈 {1,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的路徑 } ∞ 當從 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章 圖論