【正文】 1 引言 現(xiàn)實(shí)世界存在許多不同類型的模擬系統(tǒng)。 例如：交通流量就是其中一個(gè)實(shí)例。 頂點(diǎn)表示街道的十字路口，同時(shí)邊表示街道本身。 加權(quán)邊可以用來(lái)表示車速限制或者車道數(shù)量。 模型可以使用系統(tǒng)來(lái)確定最佳路線和可能遭受交通堵塞的街道。 例如：航空公司的飛行系統(tǒng)。 每一個(gè)飛機(jī)場(chǎng)就是一個(gè)頂點(diǎn)，而從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的航線就是一條邊。 加權(quán)的邊可以表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)飛行的費(fèi)用，或者表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)的大概距離，這取決于模擬的內(nèi)容。 由圖模擬真實(shí)世界系統(tǒng) 第八講 圖和圖的算法 主要內(nèi)容 圖的定義 圖的存儲(chǔ)表示 圖的第一個(gè)應(yīng)用：拓?fù)渑判? 圖的搜索 最小生成樹 查找最短路徑 圖的定義 5 圖的定義 ? 圖是由頂點(diǎn)集合 (vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph＝ ( V, E ) ? 其中： V = { vi | vi ? 某個(gè)數(shù)據(jù)對(duì)象 } 是頂點(diǎn)的有窮非空集合； E = {(vi, vj) | vi, vj ? V } 或 E = {vi, vj | vi, vj ? V amp。amp。 Path (vi, vj)} 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊 (edge)集合。 Path (vi, vj)表示從 vi 到 vj 的一條單向通路 , 它是有方向的。 0 2 1 3 圖是由一組頂點(diǎn)和一組邊構(gòu)成的 6 圖的定義 無(wú)向圖 : ( vi , vj ) = ( vj , vi ) 同一條邊 . 有向圖 : vi , vj ::= ? vj , vi 不同邊 vi vj tail head 7 圖的定義 vi vj vi 和 vj 是互為鄰接頂點(diǎn) 。 ( vi , vj ) 依附于 vi 和 vj vi vj vi 鄰接到 vj 。 vj 鄰接自 vi 。 vi , vj 相關(guān)聯(lián)于 vi and vj 子圖 G’ ? G : V( G’ ) ? V( G ) amp。amp。 E( G’ ) ? E( G ) 0 1 2 3 子圖 0 1 3 0 1 2 3 0 2 3 8 圖的定義 路徑（ path）： 圖中頂點(diǎn)的序列，所有的頂點(diǎn)由邊連接在一起。 在圖 G＝ (V, E) 中 , 若從頂點(diǎn) vi 出發(fā) , 沿一些邊經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, …, vpm，到達(dá)頂點(diǎn) vj。則稱頂點(diǎn)序列 (vi vp1 vp2 ... vpm vj) 為從頂點(diǎn) vi 到頂點(diǎn) vj 的路徑。 它經(jīng)過(guò)的邊 (vi, vp1)、 (vp1, vp2)、 ...、 (vpm, vj) 應(yīng)是屬于 E的邊。 9 圖的定義 路徑的長(zhǎng)度： 從路徑中第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)的邊的數(shù)量。 討論的圖對(duì)象的限制 : (1) 自身環(huán) 不討論 . (2) 與兩個(gè)特定頂點(diǎn)相關(guān)聯(lián)的邊不能多于一條，多重圖也不討論。 0 1 0 1 2 10 圖的定義 簡(jiǎn)單路徑： 若路徑上各頂點(diǎn) v1,v2,...,vm 均不互相重復(fù) , 則稱這樣的路徑為簡(jiǎn)單路徑。 回路： 若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn) vm 重合 , 則稱這樣的路徑為回路或 環(huán)（ loop） 。 環(huán)的長(zhǎng)度為 0。 在有向圖中路徑至少為 1以便于初始定點(diǎn)也是結(jié)束定點(diǎn)。 在有向圖中，邊可能是相同的，但是在無(wú)向圖中，邊必須是不同的 。 11 圖的定義 權(quán) ： 某些圖的 邊 具有與它相關(guān)的數(shù)值 , 稱之為權(quán) 。 這種帶權(quán)圖叫做 網(wǎng)絡(luò) 。 代價(jià)： 頂點(diǎn) 還可以有權(quán)值，被稱為代價(jià) 。 12 圖的定義 頂點(diǎn) v 的入度： 以 v 為終點(diǎn)的 有向邊 的條數(shù) , 記作 ID(v)。 頂點(diǎn) v 的出度： 以 v 為始點(diǎn)的 有向邊 的條數(shù) , 記作 OD(v)。 頂點(diǎn)的度： 一個(gè)頂點(diǎn) v的度是與它相關(guān)聯(lián)的邊的條數(shù)，記作 TD(v)。 在 有向圖 中 , 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度之和 。 13 圖的定義 v ID(v) = 3 OD(v) = 1 TD(v) = 4 注意 圖 G有 n 個(gè)頂點(diǎn)和 e條邊 , 那么 )( 210iinii vTDdde ???????? ???這里14 圖的定義 路徑長(zhǎng)度： 非帶權(quán)圖 的路徑長(zhǎng)度是 指此路徑上邊的條數(shù) 。 帶權(quán)圖 的路徑長(zhǎng)度是 指路徑上各邊的權(quán)之和 。 A B E C F 從 A到 F長(zhǎng)度為 3 的路徑 {A,B,C,F} 15 圖的定義 連通圖與連通分量： 在 無(wú)向圖 中 , 若從頂點(diǎn) v1到頂點(diǎn) v2有路徑 , 則稱 頂點(diǎn) v1與 v2是連通的 。 如果圖中任意一對(duì)頂點(diǎn)都是連通的 , 則稱此圖是 連通圖 。 非連通圖的極大連通子圖叫做 連通分量 。 強(qiáng)連通圖與強(qiáng)連通分量： 在有向圖中 , 若對(duì)于每一對(duì)頂點(diǎn) vi和 vj, 都存在一條從 vi到 vj和從 vj到 vi的路徑 , 則稱此圖是 強(qiáng)連通圖 。 非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做 強(qiáng)連通分量 。 16 圖的定義 無(wú)向圖， 若圖中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為 連通圖 。 若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱作此圖的 連通分量 。 B A C D F E B A C D F E 17 圖的定義 有向圖， 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為 強(qiáng)連通圖 。 否則，其各個(gè)強(qiáng)連通子圖稱作它的 強(qiáng)連通分量 。 A B E C F A B E C F 18 圖的定義 如果存在從任意頂點(diǎn)到其他任意頂點(diǎn)的路徑，就認(rèn)為無(wú)向圖是連通的（ connected） 在有向圖中，這個(gè)條件被稱為是強(qiáng)連通（ strongly connected） 如果有向圖不是強(qiáng)連通的，但是又認(rèn)為連通了，這就被稱為弱連通（ weakly connected） 19 圖的定義 完全圖 : 邊數(shù)最大的圖 0 2 1 3 2)1(2 E V ?????nnnCn0 2 1 3 )1( E V 2 ?????nnPnn每組頂點(diǎn)之間都有邊 20 圖的定義 生成樹： 一個(gè)連通圖的生成樹是其極小連通子圖 。 在 n個(gè)頂點(diǎn)的情形下，有 n1條邊。 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱該極小連通子圖為此 連通圖的生成樹 。 在極小連通子圖中增加一條邊，則一定有環(huán)。 在極小連通子圖中去掉一條邊，則成為非連通圖 。 21 圖的定義 有 n個(gè)頂點(diǎn)， n1條邊的圖必定是生成樹嗎？ 對(duì)非連通圖，