【文章內(nèi)容簡介】 2i ∈ X ，且 v2i +1∈ Y 。又因為 v0 ∈ X ，所以 vk ∈ Y 。由此即得 C是偶圈。 顯然僅對連通圖證明其逆命題就夠了。設(shè) G是不包含奇圈的連通圖。任選一個頂點 u且定義 V的一個分類（ X, Y）如下： X = {x | d (u, x) 是偶數(shù)， x∈ V(G)} Y = {y | d (u, y) 是奇數(shù)， y∈ V(G)} 現(xiàn)在證明（ X, Y）是 G的一個二分類。 假設(shè) v和 w是 X的兩個頂點， P是最短的（ u, v）路，Q是最短的（ u, w）路，以 u1記 P和 Q的最后一個公共頂點。因 P和 Q是最短路， P和 Q二者的 （ u1, u） 節(jié)也是最短的路，故長相同?，F(xiàn)因 P和 Q的長都是偶數(shù)，所以 P的 （ u1, v）節(jié) P1和 Q的（ u1, w）節(jié) Q1必有相同的奇偶性。由此推出路（ v, w）長為偶數(shù)。若 v和 w相連，則 就是一個奇圈，與假設(shè)矛盾，故 X中任意兩個頂點均不相鄰。 111P Q wv?類似地， Y中任意兩個頂點也不相鄰。所以（ X, Y）是 G的一個二分類。 167。 最短路及其算法 一 . 賦權(quán)圖 定義 若圖 G的每一條邊 e 都附有一個實數(shù) w(e)， 則 G連同它邊上的權(quán)稱為 賦權(quán)圖 。實數(shù) w(e) 稱為 e的權(quán)。子圖 H的各邊權(quán)之和稱為子圖 H 的權(quán)，記為 W(H)。 例 右圖 G 為 賦 權(quán)圖 v1 v3 v2 v4 G 1 3 5 6 5 其中 w(v1v2) = 1， w(v1v3) = 5， W(G) = 20 設(shè) Γ是權(quán)圖 G 中的一條路，稱 Γ 的各邊權(quán)之和為路 Γ的長。賦 權(quán)圖中點 u 到 v 的距離仍定義為點 u 到 v 的最短路的長，仍記為 d(u,v)。 例 2 右圖中， d(v2, v4) = 5 相應(yīng)的最短路為 Γ： v2v1 v3v4 v1 v3 v2 v4 G 1 3 1 6 3 易知，各邊的權(quán)均為 1的權(quán)圖中的路長與非權(quán)圖中的路長是一致的。 二 . 最短路問題 問題： 給定簡單權(quán)圖 G = (V, E)， 并設(shè) G 有 n個頂點，求 G中點 u0到其它各點的距離。 Dijkstra算法 (Edmonds, 1965) (2) 若 i = n1， 則停；否則令 = V \Si , iS iSiS 對每個 v∈ ， 令 l(v) = min {l(v)， l(ui) + w(uiv)} (1) 置 l(u0) = 0；對所有 v∈ V \{u0}，令 l(v) = ∞； S0 = {u0}， i = 0。 并用 ui+1記達到最小值的某點。置 S i+1= Si∪ {u i+1}， i = i+1（ 表示賦值語句，以后的算法中相同），轉(zhuǎn)（ 2）。 終止后， u0 到 v 的距離由 l(v) 的終值給出。 )} ( { min v l i S v ? (3) 計算 說明： （ 1） 算法中 w(uiv) 表示邊 uiv 的權(quán)； （ 2） 若只想確定 u0到某頂點 v0的距離， 則當(dāng)某 uj 等于 v0 時即停； （ 3） 算法稍加改進可同時得出 u0到其它點的最短路。 例 3 求圖 G 中 u0 到其它點的距離。 u0 7 4 2 1 5 5 8 1 3 G : 解 u0 7 4 2 1 5 5 8 1 3 ∞ ∞ ∞ ∞ ∞ （ a） 初始標(biāo)號 u0 7 4 2 1 5 5 8 1 3 2 ∞ 4 ∞ 7 （ b） 用與 u0關(guān)聯(lián)的邊的權(quán) 2,4,7分別更新與 u0相鄰的三個點的標(biāo)號 。 （ c） 取小圓點中標(biāo)號 最小者得 u1； u0 7 4 2 1 5 5 8 1 3 2 ∞ 4 ∞ 7 u1 （ d） 對與 u1相鄰的小圓點， 用 l (u1) + w (u1v) = 2+1 = 3 更新標(biāo)號 4； 2+5=7 更新兩個 ∞； u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 （ e） 取小圓點中標(biāo)號 最小者得 u2。 u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 u2 u4 u0 7 4 2 1 5 5 8 1 3 2 7 3 4 6 （ h） u1 u2 0 u3 u5 u0 7 4 2 1 5 5 8 1 3 2 7 3 7 7 u1 u2 4 （ f） u0 7 4 2 1 5 5 8 1 3 2 7 3 6 u1 u2 （ g） u0 7 4 2 1 5 5 8 1 3 2 7 3 4 6 u1 u2 u3 三 . 算法分析 好算法 一個 圖論算法如果在任何一個具有 m條邊的 n階圖 G上施行這個算法所需要的計算步數(shù)都可由 n和 m的一個多項式（例如 3n2m）為其上界 , 則稱該算法 是好的 . Dijkstra算法總共需作 n(n1)/2 次加法和 n(n1)/2 次比較 , 確定一個點是否屬于或不屬于 S, 按 1969年 Dreyfus 報告的技巧 , 需作 (n1)2 次比較 , 若把一次比較和一次加法作為一個基本計算單位 , 則該算法的總計算量大約是5n2/ . 例 某兩人有一只 8升的酒壺裝滿了酒，還有兩只空壺，分別為 5升和 3升?，F(xiàn)要將酒平分，求最少的操作次數(shù)。 解 設(shè) x1,x2,x3分別表示 8,5,3升酒壺中的酒量。則 1 2 3 1 2 38 , 8 , 5 , x x x x x? ? ? ? ? ?容易算出 (x1,x2,x3) 的組合形式共 24種。 每種組合用一個點表示，若點 u能通過倒酒的方式變換為 v,則 u向 v 連有向邊，并將各邊賦權(quán) 1，得一個有向權(quán)圖。 于是問題轉(zhuǎn)化為在該圖中求 (8,0,0)到 (4,4,0)的一條最短路 (求最短路的算法在有向圖中仍適用 )。結(jié)果如下： ( 8 , 0 , 0 ) ( 3 , 5 , 0 ) ( 3 , 2 , 3 ) ( 6 , 2 , 0 ) ( 6 , 0 , 2 ) ( 1 , 5 , 2)( 1 , 4 , 3 ) ( 4 , 4 , 0 ) .? ? ? ? ???167。 圖的代數(shù)表示及特征 一 . 鄰接矩陣 定義： 設(shè) n 階標(biāo)定圖 G = (V,E)， V = {v1,v2,…, vn}， 則 G 的鄰接矩陣是一個 n n 矩陣 A(G) = [ aij] (簡記為 A)，其中若 vi鄰接 vj，則 aij =1。否則 aij =0。 注 : 若 aij 取為連接 vi與 vj 的邊的數(shù)目 , 則稱 A為推廣的鄰接矩陣 例e5v2v3v1e1e3e2e4v4鄰接矩陣 A = 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 1 0 2 0 0 2 0 1 0 0 1 1 推廣的 鄰接矩陣 A’ = 說明 : (1) 鄰接矩陣是一個對稱方陣。 (2) 簡單標(biāo)定圖的鄰接矩陣的各行 (列 ) 元素之和是該行 (列 ) 對應(yīng)的點的度。 （ 3） 若 A1和 A2是對應(yīng)于同一個 G的兩種不同的標(biāo)定的鄰接矩陣，則 A1和 A2 是相似的。即 存在一個可逆矩陣P有 112A P A P??（ 4） G是連通的當(dāng)且僅當(dāng)沒有 G的點的一種標(biāo)定法使 它的鄰接矩陣有約化的形式 112200AAA???????考察v2v3v1v40 1 0 0 1 0 2 0 0 2 0 1 0 0 1 1 推廣的 鄰接矩陣 A = 我們有： 1 0 2 0 0 5 0 2 2 0 5 1 0 2 1 2 A 2= 圖中 v1到 v1 的長為 2的的通道的數(shù)目為 1 v1到 v2 的長為 2的的通道的數(shù)目為 0 v1到 v3 的長為 2的的通道的數(shù)目為 2 v1到 v4的長為 2的的通道的數(shù)目為 0 v2到 v2 的長為 2的的通道的數(shù)目為 5 定理 10 令 G是一個有推廣鄰接矩陣 A的 p階標(biāo)定圖，則 An的 i 行 j 列元素 等于由 vi到 vj的長度為 n的通道的數(shù)目。 ? ?nija證明 n = 0時， A0 = In (n階單位矩陣 )，從任一點到自身有一條長度為零的通道，任何不同的兩點間沒有長度為零的通道，從而命題對 n = 0時成立。 由于 aik是聯(lián)結(jié) vi和 vk的長度為 1的通道的數(shù)目， akj(n)是聯(lián)結(jié) vk和 vj的長度為 n的通道的數(shù)目，所以 aikakj(n) 表示由 vi經(jīng)過 vk到 vj的長度為 n+1的通道 數(shù)目。 今設(shè)命題對 n 成立，由 An+1=AAn，故 ??? ? pknkjiknij aaa1)()1(（ *） 于是對所有的 k求和即（ *）式右邊 表示了由 vi 到 vj 的長度為 n+1的通道 數(shù)目。也即 aij(n+1) 為由 vi 到 vj 的長度為 n+1的通道 數(shù)目。 這表明命題對 n+1成立。 推論 設(shè) A為簡單圖 G的鄰接矩陣，則 （ 1） A2 的元素 aii(2) 是 vi 的度數(shù)。 A3 的元素 aii(3) 是含 vi 的三角形的數(shù)目的兩倍。 （ 2） 若 G是連通的，對于 i≠j， vi 與 vj 之間的距離是使An 的 aij(n) ≠0 的最小整數(shù) n。 二 . 關(guān)聯(lián)矩陣 定義 1 無環(huán)圖 G的關(guān)聯(lián)矩陣 B(G) = [ bij] (簡記為 B)是一個 n m 矩陣，當(dāng)點 vi 與邊 ej 關(guān)聯(lián)時 bij =1，否則 bij =0。 v1 e1 e5 v2 v5 e6 e7 e2 e4 v3 e3 v4 例 B = e1 e2 e3 e4 e5 e6 e7 v1 v2 v3 v4 v5 ????????????????00110001001100010011000000111110001說明： 定義中“無 環(huán)”的條件可去掉，此時 bij =點 vi 與邊 ej 關(guān)聯(lián)的次數(shù)（ 0, 1, 2(環(huán) )). 性質(zhì)： 關(guān)聯(lián)矩陣的每列和為 2；其行和為對應(yīng)頂點的度數(shù) . 例如： e1 v4 v3 v2 v1 e7 e5 e4 e3 e2 e6 1 1 0 0 1 0 11 1 1 0 0 0 0()0 0 1 1 0 0 10 0 0 1 1 2 0MG?????????三、鄰接代數(shù) 給定圖 G , 容易驗證 G 的鄰接矩陣的全體復(fù)系數(shù)多項式在通常的矩陣運算下構(gòu)成一個有限維的線性空間，它也是一個代數(shù)，稱為圖 G的鄰接代數(shù)，記為 Λ(G)。 用圖 G的點數(shù)和