【正文】 ,v1},置 T為 T{x}={v2,v3,v4}。 第 8章 圖論 例 1 考慮圖 ―7 中的圖 ,起初 S={a},T={v1,v2,v3,v4},D(a)=0,D(v1)=2,D(v2)=+∞,D(v3)=+∞,D(v4)=10。 第 8章 圖論 (a)如果從 a到 t有一條最短路徑 ,它不包含 T′中的其它結(jié)點(diǎn) ,也不含 x點(diǎn) ,則 D′(t)=D(t)。初始時(shí) ,D(t)=W(a,t),現(xiàn)在我們假設(shè)對(duì) T中的每一個(gè) t已計(jì)算了 D值。可見以上斷言成立。 首先我們證明 “ 若 x是 T中具有最小 D值的結(jié)點(diǎn) ,則D(x)是從 a到 x的距離 ” ,用反證法。 ?第 8章 圖論 算法中步驟 (1)和 (3)是清楚的 ,現(xiàn)在對(duì) 2給以說明 。 (2) 對(duì) T中每一元素 t計(jì)算 D(t),根據(jù) D(t)值找出 T中距 a最短的一結(jié)點(diǎn) x,寫出 a到 x的最短路徑的長(zhǎng)度 D(x)。下面介紹 1959 年迪克斯特拉 ()提出的單源問題的算法 ,其要點(diǎn)如下 : (1) 把 V分成兩個(gè)子集 S和 T。路徑 P的長(zhǎng)度定義為路徑中邊的長(zhǎng)度之和 ,記為 W(P)。 在下圖中 ,強(qiáng)分圖集合是 : {〈 {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〉 是個(gè)賦權(quán)圖 ,W是從 E到正實(shí)數(shù)集合的函數(shù) ,邊［ i,j］的權(quán)記為 W(i,j),稱為邊的長(zhǎng)度。 在下圖中 ,(a)是強(qiáng)連通的 ,(b)是單向連通的 ,(c)是弱連通的 。如果它的底圖是連通的 ,則稱圖 G是弱連通的。 第 8章 圖論 定理 ―3 設(shè) G是任一 (n,m)無(wú)向簡(jiǎn)單圖 ,ω是 其分圖個(gè)數(shù) ,則 1 ( )( 1 )2n m n n? ? ?? ? ? ? ? ? 定義 ―6 在有向圖中 ,如果在任兩結(jié)點(diǎn)偶對(duì)中 ,至少?gòu)囊粋€(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)是可達(dá)的 ,則稱圖 G是單向連通的 。如果 G的子圖 G′是連通的 ,沒有包含 G′的更大的子圖 G″是連通的 ,則稱 G′是 G的連通分圖 (簡(jiǎn)稱分圖 )。 vi自身認(rèn) 為從 vi可達(dá)。 第 8章 圖論 連通圖 定義 ―4 設(shè) G=〈 V,E〉 是圖 ,且 vi、 vj∈ V。 (2) d(vi,vi)=0。 若從 vi到 vj不存在路徑 ,則 d(vi,vj)=∞。 第 8章 圖論 定理 ―2 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖 G=〈 V,E〉中 ,如果經(jīng) v1有一條簡(jiǎn)單回路 ,則經(jīng) v1有一條長(zhǎng)度不超過 n的基本回路。此時(shí) ,所得的就是基本路徑。 ) 定理 ―1 在一個(gè)具有 n個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖 G=〈 V,E〉中 ,如果從 v1到 v2有一條路徑 ,則從 v1到 v2有一條長(zhǎng)度不大于 n1的基本路徑。長(zhǎng)度為 0的路徑定義為單獨(dú)一個(gè)頂點(diǎn)。路徑和回路可僅用邊的序列表示 ,在非多重圖時(shí)也可用頂點(diǎn)序列表示 。 (b)P2=(v2e2v3e3v3e4v1e1v2) 是一簡(jiǎn)單回路 非基本回路 。 第 8章 圖論 如果路徑的始點(diǎn) v0和終點(diǎn) vn相重合 ,即 v0=vn,則此路徑稱為 回路 ,沒有相同邊的回路稱為簡(jiǎn)單回路 ,通過各頂點(diǎn)不超過一次的回路稱為基本回路。在序列中 ,如果同一條邊不出現(xiàn)兩次 ,則稱此路徑是 簡(jiǎn)單路徑 ,如果同一頂 點(diǎn)不出現(xiàn)兩次 ,則稱此路徑是 基本路徑 (或叫鏈 )。 定義 ―10 設(shè)線圖 G=〈 V,E〉 有 n個(gè)頂點(diǎn) ,線圖 H=〈 V,E′〉 也有同樣的頂點(diǎn) ,而 E′是由 n個(gè)頂點(diǎn)的完全圖的邊刪去 E所得 ,則圖 H稱為圖 G的 補(bǔ)圖 ,記為 ,顯然 , 。在 n個(gè)結(jié)點(diǎn)的無(wú)向圖G=〈 V,E〉 中 ,如果任何兩個(gè)不同結(jié)點(diǎn)間都恰有一條邊 ,則稱 G為 無(wú)向完全圖 ,記為 Kn。 ? ?? ? ?? (4)若在子圖 G′中 ,對(duì) V′中的任意二結(jié)點(diǎn) u、 v,當(dāng) ［ u,v］ ∈ E時(shí)有［ u,v］ ∈ E′,則 G′由 V′唯一確定 , 此時(shí)稱 G′為由結(jié)點(diǎn)集 V′導(dǎo)出的子圖。 ) (2) 如果 V′=V和 E′ E,則稱 G′為 G的 生成子圖 。如果 V′ V和 E′ E,則稱 G′ G的 真子圖 。 第 8章 圖論 子圖與補(bǔ)圖 定義 ―8 設(shè) G=〈 V,E〉 和 G′=〈 V′,E′〉 是兩個(gè)圖。 (2)刪去圖 G的一個(gè)結(jié)點(diǎn) v。 (4)G1與 G2的環(huán)和 ,定義為圖 G3＝ 〈 V3,E3〉 , G3=(G1∪ G2)(G1∩G2),記為 G3=G1 G2。 (3)G1與 G2的差 ,定義為圖 G3＝ 〈 V3,E3〉 ,記為 G3=G1G2。 第 8章 圖論 圖的運(yùn)算 圖的常見運(yùn)算有并、交、差、環(huán)和等 ,現(xiàn)分別定義于下 : 定義 ―7 設(shè)圖 G1=〈 V1,E1〉 和圖 G2=〈 V2,E2〉 (1)G1與 G2的并 ,定義為圖 G3＝ 〈 V3,E3〉 , 其中 V3=V1∪ V2,E3=E1∪ E2,記為 G3=G1∪ G2。 (a)中的 x應(yīng)與 (b)中的 y對(duì)應(yīng) ,因?yàn)榇螖?shù)都是 3。 但這不是充分條件。 (2) 邊數(shù)相等 。在這映射下 ,邊 〈 1,3〉 ,〈 1,2〉 ,〈 2,4〉 和 〈 3,4〉 分別映射到 〈 v3,v4〉 ,〈 v3,v1〉 ,〈 v1,v2〉和 〈 v4,v2〉 ,而后面這些邊又是 (b)中僅有的邊。 第 8章 圖論 例 2 (a)、 (b)兩圖是同構(gòu)的。 第 8章 圖論 圖的同構(gòu) 定義 G=〈 V,E〉 和 G′=〈 V′,E′〉 是兩個(gè)圖 ,若存在從 V到 V′的雙射函數(shù) Φ,使對(duì)任意 a、 b∈ V,［ a,b∈ E當(dāng)且僅當(dāng)［ Φ(a),Φ(b)］ ∈ E′,并且［ a,b］和［ Φ(a),Φ(b)］有