【正文】 3. 熟練掌握標(biāo)號(hào)法 。 例 下列圖哪些為哈密爾頓圖？哪些存在哈密爾頓通道？： (1) (2) (3) (4) 思考： 哈密爾頓圖與歐拉圖有聯(lián)系嗎？ 小結(jié)與學(xué)習(xí)要求 1. 本章圍繞圖中元素間的鄰接與關(guān)聯(lián)關(guān)系討論了圖論中幾個(gè)基本問(wèn)題：圖的連通性問(wèn)題 ，道路問(wèn)題 ， 可達(dá)性問(wèn)題 ， 最短路徑問(wèn)題 。 具有哈密爾頓回路的圖 稱為 哈密爾頓圖 。此兩個(gè)特殊頂點(diǎn)中，一個(gè)頂點(diǎn)的入度比出度大 1，而另一個(gè)頂點(diǎn)的出度比大入度 1。 如果 歐拉圖與哈密爾頓圖 思考： ?歐拉通路是簡(jiǎn)單通路？反之呢？歐拉通路是初級(jí)通路？ ?歐拉圖是否一定存在歐拉通路？ ?有向歐拉圖是強(qiáng)連通圖？反之呢？ 例 下列圖哪些為歐拉圖？哪些存在歐拉通道？： (1) (2) (3) (4) 歐拉圖 的判定定理 （ 必須掌握！ 說(shuō)明理由） (1) 無(wú)向圖 G具有一條歐拉回路 ， 當(dāng)且僅當(dāng) G是 連通 的 ， 并且所有頂點(diǎn)的 度數(shù)全為偶數(shù) ； (2) 有向圖 D具有單向歐拉回路 ， 當(dāng)且僅當(dāng) D是 連通 的 ， 并且每個(gè)頂點(diǎn)的 入度等于出度 。 如果存在一條通路，它經(jīng)過(guò) G的 每條 邊一次且僅一次 ， 并且行遍圖中 每個(gè) 頂點(diǎn) ， 則稱該通路為 歐拉通路 ； 具有 歐拉回路 的圖 ––– 歐拉圖 。 TL(vn) =TE (vn) vi點(diǎn)緩沖時(shí)間 TS(vi)= TL(vi) TE(vi) ：。 vj? ?D (vi) TE(vi) = max ( TE(vj) +wji) i=2,3…n vi點(diǎn)最早完成時(shí)間 TE(vi)：自發(fā)點(diǎn)（記 v1）開(kāi)始沿最長(zhǎng)路徑到 vi點(diǎn)所需的時(shí)間。 關(guān)鍵路徑 就是指從發(fā)點(diǎn)到收點(diǎn)的的一條最長(zhǎng)路徑 。 關(guān)鍵路徑問(wèn)題 實(shí)施一個(gè)工程計(jì)劃時(shí)，若將整個(gè)工程分成若干個(gè)工序，有些工序可同時(shí)實(shí)施，有些工序必須在完成另外一些工序后才能實(shí)施，工序之間的次序可用有向圖表示，該圖稱為 PERT圖 （計(jì)劃評(píng)審圖），特點(diǎn)： ① 有向連通圖； ② 簡(jiǎn)單圖； ③ 無(wú)回路； ④ 一個(gè)頂點(diǎn)入度為 0（ 發(fā)點(diǎn) ），一個(gè)頂點(diǎn)出度為 0 （ 收點(diǎn) ） ⑤ 帶權(quán)（非負(fù)）圖。 AAAAA例 求下圖中頂點(diǎn) v0與 v5之間的最短路徑 v0 v2 v1 v4 v3 v5 1 2 1 4 7 5 3 2 6 例 : 求下圖中頂點(diǎn) v0與 v5之間的最短路徑 v1 v3 1 v0 v2 v4 v5 1 2 1 4 5 1 2 6 Dijkstra算法（又稱標(biāo)號(hào)） 說(shuō)明： (1) 可求任何頂點(diǎn) Vs到其它任一頂點(diǎn)之間的最短路徑 ， 只是算法的 “ 開(kāi)始 ” 步中 ,頂點(diǎn) Vs加 入A， ， 然后算法往下計(jì)算 。 求最短路徑的戴克斯德拉 (Dijkstra)算法 基本思想 ： 思考 ：從始點(diǎn)到終點(diǎn)的 最短路徑，必然是 始點(diǎn)到該路徑上各點(diǎn)的 最短路徑 ？ 也必然是 該路徑上各點(diǎn)到終點(diǎn) 的 最短路徑 ？ 最短路徑 唯一 ？ G = V, E,W , V={v1,v2,…..v n},W=(wij)nxn是距離矩陣 二、求最短路徑的戴克斯德拉 (Dijkstra)算法 求 v1點(diǎn)到其他各點(diǎn)的距離的 Dijkstra算法 ： [ l(vi)表示 vi點(diǎn)到 v1的最短距離， A? V ] (1) 初始化： A= {v1}， = V–{v1} ， l (v1)=0， l (vi)= ? ， i為 2,3,…n 。 如果 G1是帶權(quán)圖 G的子圖，稱 )()( 1)E ( Ge11GwGew ，記作：的權(quán)為??w(e) 為邊 e上的權(quán) (當(dāng) e = vi,vj 時(shí)，權(quán)記作 wij)， 記作： G = V, E,W 一、帶權(quán)圖及其最短路徑問(wèn)題 最短路徑問(wèn)題 G = V,E,W 為帶權(quán)圖，且 G中各邊帶的權(quán)均大于等于 0，從 頂點(diǎn) u到頂點(diǎn) v的所有通路中求帶權(quán)最小的通路問(wèn)題 ，稱為 最短路徑問(wèn)題（ 一般為簡(jiǎn)單圖 ） 。 vi 可達(dá) vj 否則 (3). 求可達(dá)矩陣 可達(dá)矩陣的求法 ：由鄰接矩陣 A計(jì)算 A2,A+A2,…… A+A2+…+ A(r) = B = (bij(r))n?n pij = 1 bij(r) ? 0 0 bij(r) = 0 則 i ? j pii = 1 即得可達(dá)矩陣 P(D) = (pij)nxn 說(shuō)明 : 求通路 r|v| 。 二、鄰接矩陣及其性質(zhì) v1 v4 v3 v2 e1 e2 e3 e4 e5 e6 強(qiáng)調(diào)： 頂點(diǎn)與頂點(diǎn)的關(guān)系 ， (aij)n n行 n為 ？ v4 e1 e2 e3 e4 e5 v1 v2 v3 無(wú)向圖鄰接矩陣的特性 ： (1) 鄰接陣是對(duì)稱陣； (2) 同一行或者同一列的元素和為對(duì)應(yīng)頂點(diǎn)的度數(shù) ；或即 )()( jn1iijin1jij vdavda ?? ????(3) 矩陣中所有元素的和為邊數(shù)的 2倍 )(2n1jn1iij 握手定理即 ma ?? ?? ? 0 2 1 0 2 0 1 0 1 1 2 0 0 0 0 0 v4 e1 e2 e3 e4 e5 v1 v2 v3 (?圖與矩陣 ) 有向圖鄰接矩陣的特性 (1) 同一行的元素和為對(duì)應(yīng)頂點(diǎn)的出度 (2) 同一列的元素和為對(duì)應(yīng)頂點(diǎn)的入度 )( in1jij vda????即)( jn1iij vda????即(3) ? ? aij= ？ v1 v4 v3 v2 e1 e2 e3 e4 e5 e6 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 1 (?圖與矩陣 ) 強(qiáng)調(diào) ： 對(duì) 無(wú)向圖環(huán)計(jì) 2次，對(duì)有向圖環(huán)計(jì) 1次 ？ 三、應(yīng)用 v4 v1 v2 v3 問(wèn)： 1） 求此圖中長(zhǎng)度為 1通路總數(shù)與回路總數(shù)？ 2） 求此圖中長(zhǎng)度為 2通路總數(shù)與回路總數(shù)？ 3）求此圖中長(zhǎng)度為 3通路總數(shù)與回路總數(shù)？ n? 4） 求此圖中長(zhǎng)度小于 4的通路總數(shù)與回路總數(shù)？ 1 2 1 0 0 0 1 0 0 0 0 1 0 0 1 0 v4 v1 v2 v3 A= A2= 1 2 3 1 0 0 0 1 0 0 1 0 0 0 0 1 1 2 4 3 0 0 1 0 0 0 0 1 0 0 1 0 1 2 6 4 0 0 0 1 0 0 1 0 0 0 0 1 A3= A4= 求此圖中長(zhǎng)度為 n通路總數(shù)與回路總數(shù)？