【正文】 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章 圖論 賦權圖中的最短路徑 設 G=〈 V,E,W〉 是個賦權圖 ,W是從 E到正實數(shù)集合的函數(shù) ,邊［ i,j］的權記為 W(i,j),稱為邊的長度。如果它的底圖是連通的 ,則稱圖 G是弱連通的。如果 G的子圖 G′是連通的 ,沒有包含 G′的更大的子圖 G″是連通的 ,則稱 G′是 G的連通分圖 (簡稱分圖 )。 第 8章 圖論 連通圖 定義 ―4 設 G=〈 V,E〉 是圖 ,且 vi、 vj∈ V。 若從 vi到 vj不存在路徑 ,則 d(vi,vj)=∞。此時 ,所得的就是基本路徑。長度為 0的路徑定義為單獨一個頂點。 (b)P2=(v2e2v3e3v3e4v1e1v2) 是一簡單回路 非基本回路 。在序列中 ,如果同一條邊不出現(xiàn)兩次 ,則稱此路徑是 簡單路徑 ,如果同一頂 點不出現(xiàn)兩次 ,則稱此路徑是 基本路徑 (或叫鏈 )。在 n個結點的無向圖G=〈 V,E〉 中 ,如果任何兩個不同結點間都恰有一條邊 ,則稱 G為 無向完全圖 ,記為 Kn。 ) (2) 如果 V′=V和 E′ E,則稱 G′為 G的 生成子圖 。 第 8章 圖論 子圖與補圖 定義 ―8 設 G=〈 V,E〉 和 G′=〈 V′,E′〉 是兩個圖。 (4)G1與 G2的環(huán)和 ,定義為圖 G3＝ 〈 V3,E3〉 , G3=(G1∪ G2)(G1∩G2),記為 G3=G1 G2。 第 8章 圖論 圖的運算 圖的常見運算有并、交、差、環(huán)和等 ,現(xiàn)分別定義于下 : 定義 ―7 設圖 G1=〈 V1,E1〉 和圖 G2=〈 V2,E2〉 (1)G1與 G2的并 ,定義為圖 G3＝ 〈 V3,E3〉 , 其中 V3=V1∪ V2,E3=E1∪ E2,記為 G3=G1∪ G2。 但這不是充分條件。在這映射下 ,邊 〈 1,3〉 ,〈 1,2〉 ,〈 2,4〉 和 〈 3,4〉 分別映射到 〈 v3,v4〉 ,〈 v3,v1〉 ,〈 v1,v2〉和 〈 v4,v2〉 ,而后面這些邊又是 (b)中僅有的邊。 第 8章 圖論 圖的同構 定義 G=〈 V,E〉 和 G′=〈 V′,E′〉 是兩個圖 ,若存在從 V到 V′的雙射函數(shù) Φ,使對任意 a、 b∈ V,［ a,b∈ E當且僅當［ Φ(a),Φ(b)］ ∈ E′,并且［ a,b］和［ Φ(a),Φ(b)］有相同的重數(shù) ,則稱 G和 G′是 同構的 。故 n2必為偶數(shù)。 次數(shù)為奇數(shù)的結點有 n2個 ,記為 (i=1,2,… ,n2)。孤立結點的次數(shù)為零。 V={v1,v2,v3} E={e1,e2}={(v1,v2),(v2,v3)} f(v1)=5,f(v2)=8,f(v3)=11 g(e1)=,g(e2)= 第 8章 圖論 結點的次數(shù) 定義 ―4 在 有向圖中 ,對于任何結點 v,以 v為始點的邊的條數(shù)稱為結點 v的 引出次數(shù) (或出度 ),記為 deg+(v)。無自回路的線圖稱為 簡單圖 。兩結點 a、 b間互相平行的邊的條數(shù)稱為 邊 ［ a,b］ 的重數(shù) 。關聯(lián)于同一結點的一條邊稱為 自回路 ；自回路的方向不定。例如 ,把無向圖中每一條邊都看作兩條方向不同的有向邊 ,這時無向圖就成為有向圖。 每一條邊都是無向邊的圖稱為 無向圖 ；如果在圖中一些邊是有向邊 ,而另一些邊是無向邊 ,則稱這個圖是 混合圖 。稱 e是關聯(lián)于結點 a和 b的 ,結點 a和結點 b是 鄰接的 。 例 1設 G=〈 V(G),E(G),ΦG〉 ,其中 V(G)={a,b,c,d},E(G)={e1,e2,e3,e4, e5,e6,e7},ΦG(e1)=(a,b),ΦG(e2)=(a,c),ΦG(e3)=(b,d), ΦG(e4)=(b,c),ΦG(e5)=(d,c),ΦG(e6)=(a,d),ΦG(e7)=(b,b) 則圖 G可用圖 ― 1表示 。 判定法則：如果通奇數(shù)座橋的地方不止兩個，那么滿足要求的路線便不存在了。 歐拉在 1736年解決了這個問題 。一個圖可以用一個圖形表示。有向邊簡稱弧 ,a叫弧 e的始點 ,b叫弧 e的終點 ,統(tǒng)稱為 e的端點。 每一條邊都是有向邊的圖稱為 有向圖 , 第三章中的關系圖都是有向圖的例子 。 有向圖和無向圖也 可互相轉(zhuǎn)化 。 在圖中 ,不與任何結點鄰接的結點稱為 弧立結點 ；全由孤立結點構成的圖稱為 零圖 。在無向圖中 ,兩結點間 (包括結點自身間 )若多于一條邊 ,則稱這幾條邊為平行邊。 非多重圖稱為 線圖 。 右圖給出一個賦權圖 。在無向圖中 ,結點 v的次數(shù)是與結點 v相關聯(lián)的邊的條數(shù) ,也記為 deg(v)。 證 設次數(shù)為偶數(shù)的結點有 n1個 ,記為 (i=1,2,…,n1)。若 n2為奇數(shù) ,則第二項為奇數(shù) ,兩項 之和將為奇數(shù) ,但這與上式矛盾。 下圖所示的稱為彼得森 (Petersen)圖 ,是 3― 正則圖。因為可作映射 :g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。 (3) 度數(shù)相同的結點數(shù)相等 。但 (a)中的 x與兩個次數(shù)為 1的點 u,v鄰接 ,而 (b)中的 y僅與一個次數(shù)為 1的點 w鄰接。 其中 E3=E1E2,V3=(V1V2)∪ {E3中邊所關聯(lián)的頂點 }。 它的實際意義是刪去結點 v和與 v關聯(lián)的所有邊 。 (注意 :“G′是圖 ” 已隱含著“ E′中的邊僅關聯(lián) V′中的結點 ” 的意義。 第 8章 圖論 第 8章 圖論 定義 ―9 在 n個結點的有向圖 G=〈 V,E〉 中 , 如果 E=V V,則稱 G為 有向完全圖 。 HG?GG?第 8章 圖論 路徑和回路 路徑和回路 定義 ―1 在有向圖中 ,從頂點 v0到頂點 vn的一 條 路徑 是圖的一個點邊交替序列（ v0e1v1e2v2…envn） ,其中 vi1和 vi分別是邊 ei的始點和終點 ,i=1,2,…,n。 (a)P1=(v1e1v2e7v5) 是一條基本路徑 。 第 8章 圖論 定義 ―2 路徑 P中所含邊的條數(shù)稱為路徑 P的 長度。 簡證 假定從 v1到 v2存在一條路徑 ,(v1,…,vi,…,v2)是所 經(jīng)的結點 ,如果其中有相同的結點 vk,例 (v1,…,vi,…