【正文】 V3,E3〉 , 其中 V3=V1∩V2,E3=E1∩E2,記為 G3=G1∩G2。 其中 E3=E1E2,V3=(V1V2)∪ {E3中邊所關聯(lián)的頂點 }。 ?第 8章 圖論 除以上 4種運算外 ,還有以下兩種操作 : (1) 刪去圖 G的一條邊 e。 它的實際意義是刪去結點 v和與 v關聯(lián)的所有邊 。 (1) 如果 V′ V和 E′ E,則稱 G′是 G的 子圖 。 (注意 :“G′是圖 ” 已隱含著“ E′中的邊僅關聯(lián) V′中的結點 ” 的意義。 (3) 若子圖 G′中沒有孤立結點 ,G′由 E′唯一確定 ,則稱G′為由邊集 E′導出的子圖 。 第 8章 圖論 第 8章 圖論 定義 ―9 在 n個結點的有向圖 G=〈 V,E〉 中 , 如果 E=V V,則稱 G為 有向完全圖 。 圖 ― 11是 4個結點的有向完全圖和無向完全圖的圖示 。 HG?GG?第 8章 圖論 路徑和回路 路徑和回路 定義 ―1 在有向圖中 ,從頂點 v0到頂點 vn的一 條 路徑 是圖的一個點邊交替序列（ v0e1v1e2v2…envn） ,其中 vi1和 vi分別是邊 ei的始點和終點 ,i=1,2,…,n。 基本路徑也一定是簡單路徑。 (a)P1=(v1e1v2e7v5) 是一條基本路徑 。 第 8章 圖論 在無向圖上 ,以上各術語的定義完全類似 ,故不重復 。 第 8章 圖論 定義 ―2 路徑 P中所含邊的條數(shù)稱為路徑 P的 長度。 (但注意習慣上不定義長度為 0的回路。 簡證 假定從 v1到 v2存在一條路徑 ,(v1,…,vi,…,v2)是所 經(jīng)的結點 ,如果其中有相同的結點 vk,例 (v1,…,vi,…,vk,…,vk,…,v2),則刪去從 vk到 vk的這些邊 ,它仍是從 v1到 v2的路徑 ,如此反復地進行直至 (v1,…,vi,…,v2)中沒有重復結點為止。 基本路徑的長度比所經(jīng)結點數(shù)少 1,圖中共 n個結點 ,故基本路徑長度不超過 n1。 定義 ― 3在圖 G=〈 V,E〉 中 ,從結點 vi到 vj最短路徑的長度叫從 vi到 vj的距離 ,記為 d(vi,vj)。 注意 ,在有向圖中 ,d(vi,vj)不一定等于 d(vj,vi),但一般地滿足以下性質 : (1) d(vi,vj)≥0。 (3) d(vi,vj)+d(vj,vk)≥d(vi,vk)。 如果從 vi到 vj存在一條路徑 ,則稱 vj從 vi可達。 定義 ―5 在無向圖 G中 ,如果任兩結點可達 ,則稱圖G是連通的 。 第 8章 圖論 圖 ―2 一個無向圖或者是一個連通圖 ,如圖 ―2( a)所示 ,或者是由若干個連通分圖組成 ,如圖 ―2( b)所示。如果在任兩結點偶對中 ,兩結點都互相可達 ,則稱圖 G是強連通的 。 第 8章 圖論 強連通的也一定是單向連通和弱連通的 ,單向連通的一定是弱連通的 ,但其逆均不真 。 第 8章 圖論 定義 ―7 在有向圖 G=〈 V,E〉 中 ,G′是 G的子 圖 ,若 G′是強連通的 (單向連通的 ,弱連通的 ),沒有包含 G′的更大子圖 G″是強連通的 (單向連通的 ,弱連通的 ),則稱G′是 G的強分圖 (單向分圖 ,弱分圖 )。若 i和 j之間沒有邊 ,那么 W(i,j)=∞。圖 G中從結點 u到結點 v的距離記為 d(u,v),定義為 min{W(P)|P為 G中從 u到 v的路徑 } ∞ 當從 u到 v不可達時 ( , )du ? ?? ??第 8章 圖論 本小節(jié)主要討論在一個賦權的簡單連通無向圖 G=〈 V,E,W〉 中 ,求一結點 a(稱為源點 )到其它結點 x的最短路徑的長度 ,通常稱它為單源問題。 初始時 ,S={a},T=VS。 (3)置 S為 S∪ {x},置 T為 T{x},若 T= ,則停止 ,否則再重復 2。 D(t)表示從 a到 t的不包含 T中其它結點的最短通路的長度 ,但 D(t)不一定是從 a到 t的距離 ,因為從 a到 t可能有包含 T中另外結點的更短通路。若另有一條含有 T中另外結點的更短通路 ,不妨設這個通路中第一個屬于 T{x}的結點是 t1,于是 D(t1)＜ D(x),但這與題設矛盾。 第 8章 圖論 其次說明計算 D(t)的方法。設 x是 T中 D值最小的一個結點 ,記 S′=S∪ ｛ x},T′=T{x},令 D′(t)表示 T′中結點 t的 D值 ,則 D′(t)=min［ D(t),D(x)+W(x,t)］ 現(xiàn)分情況證明上式 。 (b)如果從 a到 t有一條最短路徑 ,它從 a到 x不包含 T′中的結點 ,接著是邊 W(x,t),在此情況下 ,D′(t)是D(x)+W(x,t)。 因為 D(v1)=2是 T中最小的 D值 ,所以選 x=v1。然后計算 : D(v2)=min(+∞,2+3)=5 D(v3)=min(+∞,+∞)=+∞ D(v4)=min(10,2+7)=9 如此類推 ,直至 T= 終止 。 ?第 8章 圖論 圖 ―7 第 8章 圖論 表 ―1 第 8章 圖論 歐拉路徑和歐拉回路 哥尼斯堡 (Konigsberg,現(xiàn)加里寧格勒 )位于普雷格爾(Pregel)河畔 ,河中有兩島。古時城中居民 熱衷于一個問題 :游人從任一地點出發(fā) ,怎樣才能做到穿過每座橋一次且僅一 次后又返回原出發(fā)地。 第 8章 圖論 不難看出 ,如果用結點代表陸地 ,用邊代表橋 ,哥尼斯堡七橋問題就等價在于圖 ―8( b)中找到這樣一條路徑 ,它穿程每條邊一次且僅一次。穿程于圖 G的每條邊一次且僅一次的回路 ,稱為歐拉回路 ,具有歐拉回路的圖稱為歐拉圖。因此 ,下邊討論歐拉路徑有關問題時均假定圖是連通的。 證必要性。因此 ,除路徑的兩端點外 ,圖中任何頂點的次數(shù)必是偶數(shù)。因此必要性得證。我們從兩個奇數(shù)次數(shù)的頂點之一開始 (若無奇數(shù)次數(shù)的頂點 ,可從任一點開始 ),構造一條歐拉路徑。對于偶數(shù)次數(shù)的頂點 ,通過一條邊進入這個頂點 ,總可通過一條未畫過的邊離開這個頂點。如果圖中所有邊已用這種方法畫過 ,顯然 ,這就是所求的歐拉路徑。 第 8章 圖論 并且因為原來的圖是連通的 ,因此 ,這個子圖必與我們已畫過的路徑在一個點或多個點相接。我們將這條路