【正文】 P(0,0) P(3, v1) P(17, v2) P(7, v3) P(9, v1) P(8, v1) P(14, v6) P(16, v6) 22 例 4 求圖 ， v1到其它各點(diǎn)的最短路。 若最小的 T標(biāo)號(hào)不止一個(gè)，則可任取一個(gè)改為 P標(biāo)號(hào)。當(dāng)終點(diǎn)得到 P標(biāo)號(hào)，算法結(jié)束。此算法的基本步驟是采用標(biāo)號(hào)法，給圖 G每一個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)。實(shí)際上，它可以求某一點(diǎn)到其它各點(diǎn)的最短路。許多優(yōu)化問(wèn)題都需要求圖的最短路，如選址、管道鋪設(shè)、設(shè)備更新、整數(shù)規(guī)劃等問(wèn)題。因此，求最小支撐樹(shù)方法也有相應(yīng)的 破圈法；避圈法 。根據(jù)實(shí)際問(wèn)題的需要，權(quán)可以有不同的實(shí)際含義，它可以表示距離、流量、時(shí)間、費(fèi)用等。特別地，若 V’ = V ，則稱(chēng) G’為 G的支撐子圖。 （ 4） T無(wú)圈且有 n－ 1條邊。 設(shè)圖 T=(V,E)，含有 n個(gè)頂點(diǎn)，則下列命題是等價(jià)的。 鏈： 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列 。 度為零的點(diǎn)稱(chēng)為 弧立點(diǎn) ，度為 1的點(diǎn)稱(chēng)為 懸掛點(diǎn) 。 一個(gè)不含環(huán)和多重邊的圖稱(chēng)為 簡(jiǎn)單圖 。若邊 ei,ej有一個(gè)公共的端點(diǎn) u，稱(chēng)邊 ei,ej相鄰 。而邊不帶方向的圖稱(chēng)為無(wú)向圖。 圖 2 第一節(jié) 圖的基本概念 所謂圖，就是頂點(diǎn)和邊的集合，點(diǎn)的集合記為V={v1, v2…, vn }，邊的集合記為 E ={e1, e2…, em } ， vi稱(chēng)為圖的頂點(diǎn)， ej稱(chēng)為圖的邊，若邊 ej聯(lián)結(jié) vs和 vt ，則記為 (vs,vt )，即 ej= (vs,vt ) 。問(wèn)題是一個(gè)人能否從一點(diǎn)出發(fā)，經(jīng)過(guò)每座橋一次且僅一次，回到原出發(fā)點(diǎn)。 3 ? ? ? ?1 2 3 4 5 1 2 3 4 5 6 71 1 5 2 1 5 3 1 2 4 2 25 2 4 6 4 5 7 3 4, , , , , , , , , , , ,( , ) , ( , ) , ( , ) , ( , ) ,( , ) , ( , ) , ( , )V v v v v v E e e e e e e ee v v e v v e v v e v ve v v e v v e v v??? ? ? ?? ? ?有些圖的邊帶有方向，這樣的圖稱(chēng)為有向圖。 v1 v5 v2 v3 v4 e1 e2 e3 e4 e6 e5 e7 圖 圖 4 在一個(gè)圖中，若 e=(u,v) ，則稱(chēng) u,v是邊 e的 端點(diǎn) ．并 u,v稱(chēng) 相鄰 ．稱(chēng) e是點(diǎn) u（ v及點(diǎn)）的 關(guān)聯(lián)邊 。如圖 ， e7是環(huán)， e1, e2是多重邊。 5 以點(diǎn) v為端點(diǎn)的邊的條數(shù)稱(chēng)為點(diǎn) v的 度 ，記作d(v),如圖 d(v1)=3, d(v3)=1。 不難證明：在一個(gè)圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)的２倍，奇頂點(diǎn)的個(gè)數(shù)必為偶數(shù)。一個(gè)不含圈的連通圖稱(chēng)為樹(shù)。 （ 3） T連通且有 n－ 1條邊。 7 給定圖 G=( V, E) ，若 V ’ ? V , E’? E，并且 E’中的邊的端點(diǎn)都屬于 V ’ ，則稱(chēng)G’=( V’ , E’)是 G的一個(gè)子圖。賦權(quán)圖在圖論的應(yīng)用中經(jīng)常出現(xiàn)。 求圖 G的最小支撐樹(shù)的方法是建立在求圖 G的支撐樹(shù)基礎(chǔ)上，只需在求圖 G的支撐樹(shù)的算法再加適當(dāng)限制。 圖 v1 v5 v2 v3 v4 2 v6 v7 v8 3 4 3 4 6 2 3 6 6 4 5 8 5 10 v1 v5 v2 v3 v4 2 v6 v7 v8 3 4 3 4 6 2 3 6 6 4 5 8 5 解 破圈法 11 v1 v5 v2 v3 v4 2 v6 v7 v8 3 4 3 4 6 2 3 6 6 4 5 8 5 避圈法： 12 第三節(jié) 最短路問(wèn)題 最短路問(wèn)題，一般來(lái)說(shuō)就是從給定的賦權(quán)圖中，尋找兩點(diǎn)之間權(quán)最小的鏈（鏈的權(quán)即鏈中所有邊的權(quán)之和）。 一、 Dijkstra算法 Dijkstra算法是求賦權(quán)有向圖中，某兩點(diǎn)之間最短路的算法。 13 Dijkstra算法的基本思想是基于以下原理：若 vs,vl,…, vj是 vs到 vj的最短路， vi是此路中某一點(diǎn)，則 vs,vl,…, vi必是從 vs到 vi的最短路。算法每一步都把某點(diǎn)的 T標(biāo)號(hào)改變?yōu)?P標(biāo)號(hào)。 （ 2）在所有 T標(biāo)號(hào)點(diǎn)中，若 vk的 T標(biāo)號(hào)最小，則把 vk的 T標(biāo)號(hào)改為 P標(biāo)號(hào) 。 15 例 3 求圖 ， v1到 v8的最短路。逐次逼近法可用于存在負(fù)權(quán)，但無(wú)負(fù)有向回路的賦權(quán)圖的最短路問(wèn)題。 因?yàn)閳D中，不含負(fù)有向回路，所以從 v1到 vj的最短路上最多有 n1條邊 。 }m in { )()1( ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L1jj ld ?)1(34 }m in { )()1( ijkikj ldd ??? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ 35 }m in { 1)1()2(1 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???36 }m in { 2)1()2(2 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 37 }m in { 3)1()2(3 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 38 }m in { 4)1()2(4 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L )1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }m in { )()1( ijkikj ldd ???2 5② 10② 39 }m in { 5)1()2(5 ii ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ??????????????????????????????????