【正文】 5 , x x x x x? ? ? ? ? ?容易算出 (x1,x2,x3) 的組合形式共 24種。 （ c） 取小圓點(diǎn)中標(biāo)號(hào) 最小者得 u1； u0 7 4 2 1 5 5 8 1 3 2 ∞ 4 ∞ 7 u1 （ d） 對(duì)與 u1相鄰的小圓點(diǎn)， 用 l (u1) + w (u1v) = 2+1 = 3 更新標(biāo)號(hào) 4； 2+5=7 更新兩個(gè) ∞； u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 （ e） 取小圓點(diǎn)中標(biāo)號(hào) 最小者得 u2。 終止后， u0 到 v 的距離由 l(v) 的終值給出。 二 . 最短路問題 問題： 給定簡單權(quán)圖 G = (V, E)， 并設(shè) G 有 n個(gè)頂點(diǎn)，求 G中點(diǎn) u0到其它各點(diǎn)的距離。子圖 H的各邊權(quán)之和稱為子圖 H 的權(quán)，記為 W(H)。所以（ X, Y）是 G的一個(gè)二分類?，F(xiàn)因 P和 Q的長都是偶數(shù)，所以 P的 （ u1, v）節(jié) P1和 Q的（ u1, w）節(jié) Q1必有相同的奇偶性。設(shè) G是不包含奇圈的連通圖。這樣， v2i ∈ X ，且 v2i +1∈ Y 。在另一個(gè)分支中取一點(diǎn) w，則在 中 u和 v均與 w鄰接，從而uwv是一條通道 , 故在 中它們鄰接。 有： ω(D) =3， ω(G) =1 易知： G 連通 ω(G)=1 G D ● 例 3. 有關(guān)定理 定理 7 若圖 G是不連通的，則 是連通圖。 連通圖 : G中任意兩個(gè)頂點(diǎn)均連通的圖。 圖 G的直徑 定義為 d(G) = max{ d(u, v) | u, v∈ V} 例 1 在下圖 G 中，取 w1 = v1v2v3 ， w2 = v1v2v3v4v2 ， w3 = v1v2v3v2v3v4 ( 注： 簡單圖可只用點(diǎn)序列表通路） v1 v4 v5 v3 v2 G 則 w1, w2, w3 依次為長 為 2,4,5的途徑 ； 由定義 1可看出 ,G中 v1 v2v5v1為長為 3的圈， v1v2 v3 v4v2 v5v1 為長為 6 的回路。 k（奇，偶）圈： 長為 k （奇，偶）的圈。顯然路必為 跡 。如果 Qn的兩個(gè)點(diǎn)的二進(jìn)制表示式中只有一處不同，則它們鄰接。 定義 3 設(shè) G1= (V1, E1)， G2 = (V2, E2)，對(duì)點(diǎn)集 V = V1 V2中的任意兩個(gè)點(diǎn) u = (u1,u2)和 v = (v1,v2)，當(dāng) (u1 = v1和 u2 adj v2) 或 (u2 = v2 和 u1 adj v1) 時(shí)就把 u 和 v 連接起來所得到的圖 G稱為 G1和 G2積圖，記為 G = G1 G2。 定理 8 簡單圖 G 中所有不同的生成子圖（包括 G和空圖）的個(gè)數(shù)是 2m個(gè) , 其中 m為 G 的邊數(shù)。若 V’={v}, 則把 G{v}簡記為 G–v。 G的 生成子圖 是指滿足 V(H) = V(G)的子圖 H。 167。 正整數(shù) k的劃分 : 是指將 k表示為若干正整數(shù)的和 ,或指一 個(gè)無序正整數(shù)組，組中正整數(shù)的和是 k。 推論 2 正則圖的階數(shù)和度數(shù)不同時(shí)為奇數(shù)。 由握手定理 ? ? V v v d ) ( ? ? 1 ) ( V v v d ? ? 2 ) ( V v v d 2m = = + （ 1） ? ? 2 ) ( V v v d （ 1）式中 2m為偶， 也為偶（因其中每個(gè) d(v)為偶）， 例 7 證明在任意一次集會(huì)中和奇數(shù)個(gè)人握手的人的個(gè)數(shù)為偶數(shù)個(gè)。 推論 1 任意圖中，奇點(diǎn)的個(gè)數(shù)為 偶數(shù)。 有 證明 因圖 G 的任一條邊均有兩個(gè)端點(diǎn) (可以相同 )，在計(jì)算度時(shí)恰被計(jì)算兩次 (每個(gè)端點(diǎn)各被計(jì)算了一次 )，所以各點(diǎn)的度數(shù)之和恰好為邊數(shù)的兩倍，即 () 式成立。 K1,3 , K3,3為完全偶圖 例 偶圖 不是偶圖 ? ?1 ,E u v u v u v V? ? ?簡單 圖 G 的 補(bǔ)圖 : 設(shè) G =（ V, E），則圖 H =（ V， E1\E）稱為 G 的補(bǔ)圖，記為 , 其中集合 HG?例如 , 下圖中的 (a)， (b)兩圖是互補(bǔ)的。 例如 K2, K3, K4分別為如下圖所示 。 u1 v1 解 兩圖不同構(gòu)。 例 證明下面兩圖同構(gòu)。 非標(biāo)定圖實(shí)際上是代表一類相互同構(gòu)的圖。 定義 設(shè) v為 G 的頂點(diǎn)， G 中與 v 為端點(diǎn)的邊的條數(shù)（環(huán)計(jì)算兩次）稱為點(diǎn) v 的度數(shù)，簡稱為點(diǎn) v的 度 ，記為 dG (v)，簡記為 d(v)。邊集為空的圖稱為 空圖 。 (4) 既沒有環(huán)也沒有重邊的圖稱為 簡單圖 。 點(diǎn) v1與 v2 相鄰， v1與 v3不相鄰；邊 e1與 e2相鄰， e1與e3 不相鄰；點(diǎn) v1與邊 e1相關(guān)聯(lián)。 v1 v2 v3 v4 e1 e2 e3 e4 e5 例 2 設(shè) V = {v1,v2,v3,v4}， E = {e1,e2,e3,e4,e5}， 其中 e1= v1v2， e2 = v2v3， e3 = v2v3， e4 = v3v4， e5 = v4v4 則 G = (V, E) 是一個(gè)圖。 第一章 圖的基本概念 符號(hào)說明 : 圖 G 的頂點(diǎn)集也記為 V(G), 邊集也記為 E(G)。 圖和簡單圖 一．圖的定義 定義 1 一個(gè)圖 G 定義為一個(gè)有序?qū)?(V, E)，記為 G = (V, E)，其中 （ 1） V是一個(gè)非空集合，稱為頂點(diǎn)集或點(diǎn)集，其元素稱為頂點(diǎn)或點(diǎn)； （ 2） E是由 V中的點(diǎn)組成的無序點(diǎn)對(duì)構(gòu)成的集合，稱為邊集，其元素稱為邊，且同一點(diǎn)對(duì)在 E 中可出現(xiàn)多次。 若用小圓點(diǎn)代表點(diǎn)，連線代表邊，則可將一個(gè)圖用“圖形”來表示 , 如 例 1 中的圖可表為 v1 v2 v3 v4 注 : 也可記邊 uv 為 e ，即 e = uv。若兩條邊有一個(gè)共同的端點(diǎn)，則稱這兩條 邊相鄰 。重?cái)?shù)大于 1的邊稱為重邊。只有一個(gè)頂點(diǎn)而無邊的圖稱為 平凡圖 。 （ 2） 圖同構(gòu)的幾個(gè)必要條件： ① 頂點(diǎn)數(shù)相同； ② 邊數(shù)相同； ③ 度數(shù) 相等的頂點(diǎn)個(gè)數(shù)相同。 （ 4） 在圖的圖形表示中我們可以不給圖的點(diǎn)和邊標(biāo)上符號(hào)，稱這樣的圖為 非標(biāo)定（號(hào)）圖 ，否則稱為 標(biāo)定（號(hào)）圖 。 不誤解時(shí)我們也不嚴(yán)格區(qū)分標(biāo)定圖與非標(biāo)定圖。 例 判斷下面兩圖是否同構(gòu)。 三、完全圖 ，偶圖 ，補(bǔ)圖 完全圖： 任意兩點(diǎn)均相鄰的簡單圖稱為完全圖，在同構(gòu)意義下， n 階完全圖只有一個(gè)，記為 Kn。 完全偶圖： 是指具有二分類（ X, Y）的簡單偶圖，其中 X的每個(gè)頂點(diǎn)與 Y 的每個(gè)頂點(diǎn)相連，若 |X|=m， |Y|=n，則這樣的偶圖記為 Km,n 例 K 3,3 K1,3 G1 G2 四個(gè)圖均為偶圖 。 圖中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2 v1 v2 v3 v4 v5 例如 注： 該圖中各點(diǎn)的度數(shù) 之和等于 14，恰好 是邊數(shù) 7的 兩 倍 對(duì)任意的有 m條邊的圖 G = (V, E)。 奇 (偶 )點(diǎn) : 奇 (偶 )數(shù)度的頂點(diǎn) 相關(guān)術(shù)語和記號(hào) ? ?G? 圖 G的頂點(diǎn)的最小度 ? ?G? 圖 G的頂點(diǎn)的最大度 k正則圖 : 每個(gè)點(diǎn)的度均為 k 的 簡單圖 例如 ,完全圖和完全偶圖 Kn,n均是正則圖。 ? ? 1 ) ( V v v d 證明 任給圖 G = (V, E)， 設(shè) G 有 m 條邊，令 V1={ v | v ??V ,d(v) 為奇數(shù) }, V2={ v | v ??V ,d(v) 為偶數(shù) } 顯然， V1 ∪ V2= V,V1∩ V2=Φ 。于是，問題轉(zhuǎn)化為證明“圖 G 中度數(shù)為奇的點(diǎn)的個(gè)數(shù)為偶數(shù)”，這正是 推論 1的結(jié)論。 它是刻畫圖的特 征的重要“拓?fù)洳蛔兞俊薄? 例 試判斷下列非負(fù)整數(shù)組 Π 是否可圖 ? ? ?5 5 3 3 2 2 2??? ?4 2 2 1 1 2???解 利用定理 5可得下列非負(fù)整數(shù)組 ? ?1 4 2 2 2 1 1??? ?1 1 1 1 0 1???? ?1 1 1 1 0 1???因 是可圖的 所以 也是可圖的 : ? ?5 5 3 3 2 2 2??v3 v4 v5 v1 v6 v2 v7 關(guān)于圖序列，主要研究的 3個(gè)問題 ：（ 1） 存在問題（什么樣的整數(shù)組是圖序列？）已 解決； (2) 計(jì)數(shù)問題（一個(gè)圖序列對(duì)應(yīng)多少不同構(gòu)的圖？） 解決得不好； (3) 構(gòu)造問題（如何畫出圖序列對(duì)應(yīng)的所有不同構(gòu)圖？） 沒有解決。 當(dāng) H ? G ，但 H ≠ G時(shí)，則記為 H ? G ，且稱 H為 G的真子圖 。以 V’