【正文】 ） 有邊聯(lián)結(jié)的兩個頂點稱為 相鄰的頂點 ，有一個公共端點的邊 稱為 相鄰的邊 ． （４） 邊和它的端點稱為互相 關聯(lián) 的． （５） 既沒有環(huán)也沒有平行邊的圖，稱為 簡單圖 ． （６） 任意兩頂點都相鄰的簡單圖，稱為 完備圖 ，記為 Kn，其中 n 為頂點的數(shù)目． ( 7) 若 V = X ? Y ， X ? Y = ? ， 且 X 中任兩頂點不相鄰， Y 中任兩頂 點不相鄰， 則 稱 G 為 二元圖 （或二分圖） ；若 X 中每一頂點皆與 Y 中一切頂點 相鄰， 則 G 稱為 完備二元圖 ，記為 Km , n，其中 m , n 分別為 X 與 Y 的頂 點數(shù)目． 返回 頂點的次數(shù) 定義 （１）在無向圖中，與頂點 v 關聯(lián)的邊的數(shù)目（環(huán)算兩次）稱為 v 的 次數(shù) （或度數(shù)） ，記為 ()dv ． （２）在有向圖中，從頂點 v 引出的邊的數(shù)目稱為 v 的 出度 ， 記為 ()dv＋ ，從頂點 v 引入的邊的數(shù)目稱為 v 的 入度 ，記為 ()dv－ ， ()dv = ()dv＋ + ()dv－ 稱為 v 的次數(shù)． 4( ) 4dv ?5)(3)(2)(444?????vdvdvd定理１ )(2)()( GvdGVv ???? 推論１ 任何圖中奇次頂點的總數(shù)必為偶數(shù)． 例 在一次聚會中，認識奇數(shù)個人的人數(shù)一定是偶數(shù) . 返回 子圖 定義 設圖 G =( V , E , ? ), G 1 =( V 1 , E 1 , 1? ) ( 1 ) 若 V 1 ? V ， E 1 ? E , 且當 e ? E 1 時， 1? ( e ) = ? ( e ), 則稱 G 1 是 G 的 子圖 ． 特別的，若 V 1 = V ，則 G 1 稱為 G 的 生成子圖 ． ( 2 ) 設 V 1 ? V ，且 V 1 ?? ，以 V 1 為頂點集、兩個端點都在 V 1 中的 圖 G 的邊為邊集的圖 G 的子圖，稱為 G 的 由 V 1 導出的子圖 ，記為 G [ V 1 ]. ( 3 ) 設 E 1 ? E , 且 E 1 ?? , 以 E 1 為邊集 , E 1 的端點集為頂點集的圖 G 的子圖 , 稱為 G 的 由 E 1 導出的子圖 , 記為 G [ E 1 ]. G G [{ v 1 ,v 4 ,v 5 }] G [{ e1 ,e 2 ,e 3 }] 返回 關聯(lián)矩陣 對無向圖 Ｇ ，其關聯(lián)矩陣 Ｍ ＝?? ?)( ijm，其中： 10ijijijvemve?? ??若 與 相 關 聯(lián)若 與 不 關 聯(lián) M =43215432110110011000101110001vvvveeeee?????????????? 對有向圖Ｇ，其關聯(lián)矩陣 Ｍ ＝?? ?)( ijm，其中： ???????不關聯(lián)與若的終點是若的起點是若jijijiijevevevm011 注：假設圖為無向簡單圖 返回 鄰接矩陣 對無向圖 Ｇ ，其鄰接矩陣?? ?? )( ijaA，其中： 不相鄰與若相鄰與若jijiij vvvva???? 01 注：假設圖為簡單無向圖 A =432143210111101011011010vvvvvvvv?????????????? 對有向圖 Ｇ ＝（ Ｖ ， Ｅ ），其鄰接矩陣?? ?? )( ijaA，其中： EvvEvvajijiij ?????? ），若（），若（01 對有向賦權圖 Ｇ ，其鄰接矩陣?? ?? )( ijaA，其中： ??????????EvvjiwEvvwajiijjiijij),(0,),(若若為其權且若 無向賦權圖的鄰接矩陣可類似定義．A =4321432105375083802720vvvvvvvv???????????????? 返回 最 短 路 問 題 及 其 算 法 一、 基 本 概 念 二、固 定 起 點 的 最 短 路 三、每 對 頂 點 之 間 的 最 短 路 返回 基 本 概 念 通路 44112544141vevevevevW vv ?道路 4332264521141vevevevevevT vv ?路徑 4521141vevevP vv ?定義１ 在無向圖 G =( V , E , ? ) 中： （１） 頂點與邊相互交錯且iii vve 1)( ??? ( i =1,2 , … , k ) 的有限非空序列 )( 12110 kkk vevevevw ?? ? 稱為一條從 0v 到 kv 的 通路 ，記為kvvW 0 （２）邊不重復但頂點可重復的通路稱為 道路 ，記為kvvT 0 （３）邊與頂點均不重復的通路稱為 路徑 ，記為kvvP 0 定義２ 　 （１）任意兩點均有路徑的圖稱為 連通圖 ．　　　　 （２）起點與終點重合的路徑稱為 圈 ．　　　　 （３）連通而無圈的圖稱為 樹 ．定義３ （１）設( , )P u v是賦權圖 G 中從 u 到 v 的路徑， 則稱???)()()(PEeewPw為路徑 P 的 權 ． ( 2) 在賦權圖 G 中，從頂點 u 到頂點 v 的具有最小權的路 ( , )P u v?，稱為 u 到 v 的 最短路 ． 返回 固 定 起 點 的 最 短 路 最短路是一條路徑，且最短路的任一段也是最短路． 假設在 u0v0的最短路中只取一條，則從 u0到其余頂點的最短路將構成一棵以 u0為根的樹． 因此 , 可采用樹生長的過程來求指定頂點到其余頂點的最短路． 6 2 3 4 1 5 8 7 Di j k s t r a 算法 ：求 G 中從頂點 0u 到其余頂點的最短路 . 設 G 為賦權有向圖或無向圖， G 邊上的權均非負． 對每個頂點，定義兩個標記（ l v( ) ， z v( ) ），其中 : l v( ) ：表從頂點0u到 v 的一條路的權． z v( ) ： v 的父親點，用以確定最短路的路線 算法的過程就是在每一步改進這兩個標記，使最終 l v( ) 為從頂點0u 到 v 的最短路的權． S ：具有永久標號的頂點集 輸入 : G 的帶權鄰接矩陣 ),( vuw 算法步驟： （１）賦初值：令 S ＝ { u 0 } , l u( )0=0 ? ? ?v S V S\ , 令 l v( ) = W u v( , )0 , z v( ) = u 0 u ? u 0 （ 3 ） 設 v * 是使 l v( ) 取最小值的 S 中的頂點，則令 S =S ∪ { v * } ， u ? v * （ 4 ） 若 S ? φ ，轉(zhuǎn) 2 ，否則，停止 . 用上述算法求出的 l v( ) 就是 u 0 到 v 的最短路的權，從 v 的父親標記)( vz 追溯到 u 0 , 就得到 u 0 到 v 的最短路的路線 . （ 2 ）更新 l v( ) 、 z v( ) ： ? ? ?v S V S\ , 若 l v( ) l u W u v( ) ( , )? 則令 l v( ) = l u W u v( ) ( , )? , z v( ) = u 例 求下圖從頂點 u 1 到其余頂點的最短路． 先寫出帶權鄰接矩陣： ??????????????????????????????????03064093021509701608120W 因 G 是無向圖，故 W 是對稱 矩 陣． TO MATLAB(road1) )( iul 迭代 次數(shù) 1u 2u 3u 4u 5u 6u 7u 8u １ 2 3