【文章內(nèi)容簡(jiǎn)介】 用中，經(jīng)常遇到的情況是，不僅需要畫(huà)出描述問(wèn)題的圖，而且需要指出圖中每一條邊的方向。這是因?yàn)?，在有些?wèn)題中，一對(duì)頂點(diǎn)之間的關(guān)系往往不是對(duì)稱(chēng)的。例如，城市道路系統(tǒng)中的單行道、直流電路等；另一方面，有些關(guān)系僅用無(wú)方向性的邊是反映不出來(lái)的，例如，一項(xiàng)工程中各工序之間的先后關(guān)系、競(jìng)賽中的勝負(fù)關(guān)系等。 我們將點(diǎn)與點(diǎn)之間有方向的邊稱(chēng)為弧，在圖上用前頭標(biāo)明方向。 定義 313 對(duì)于點(diǎn)集 V （非空）和弧集 A ，如果任一弧 Aa ? 對(duì)應(yīng)于一個(gè) 有序 點(diǎn)對(duì) ? ?vu ， ， 其中 u 、 v 分別為弧 a 的始點(diǎn)和終點(diǎn) ，則 點(diǎn)集 V 與弧集 A 的和集稱(chēng)為有向圖，記作? ?AVD ，? 。 基礎(chǔ)圖 從一個(gè)有向圖 D 中去掉弧的方向后所得到的無(wú)向圖稱(chēng)為原有向圖的基礎(chǔ)圖，記作 ? ?DG 。 42 167。 2 有向圖 有向圖的環(huán)、鏈、路 鏈、路圖示 環(huán) 鏈 路 若弧 ? ?ji vu ， 的始點(diǎn) iu 與終點(diǎn) jv 相同，即 iu = jv ，則此弧稱(chēng)為環(huán)。規(guī)定環(huán)不標(biāo)方向。 對(duì) 于 有 向 圖 D 的 一 個(gè) 點(diǎn) 弧 交 替 序 列? ?12211 ??nnn iiiiiiivavavav ，，，， ?? （下標(biāo)不一定是遞增的順序），如果與其基礎(chǔ)圖 ? ?DG 中的一條鏈相對(duì)應(yīng) ，則稱(chēng)這個(gè)點(diǎn)弧交替序列為有向圖 D 的一條鏈。 設(shè) ? ?12211 ??nnn iiiiiiivavavav ，，，， ?? 為有向圖 D 的一條鏈，如果滿(mǎn)足 ? ?1??ttt iiivva ，則稱(chēng)此鏈為從點(diǎn)1iv 到1?niv 的一條路。 注意鏈與路的區(qū)別。對(duì)于一條鏈，其各弧的方向與鏈的方向不一定一致；而對(duì)于路，其各弧的方向與路的方向一定是一致的。 回路 始點(diǎn)與終點(diǎn)相同的路稱(chēng)為回路。 43 167。 2 有向圖 有向圖的環(huán)、鏈、路 167。 3 圖的矩陣表示 v1 v2 v3 v4 v5 a1 a2 a3 a4 a6 a7 a5 鏈？ 路？ √ 鏈？ 路？ √ 鏈、路圖示 圖的矩陣表示的用途 （ 1）對(duì)于復(fù)雜的圖， 用矩陣描述簡(jiǎn)單；（ 2）將優(yōu)化算法在計(jì)算機(jī)上實(shí)現(xiàn)時(shí)，必須將圖用矩陣來(lái)表示（如前述中國(guó)郵路問(wèn)題）。 44 主要內(nèi)容 167。 3 圖的矩陣表示 第三章 圖與網(wǎng)絡(luò)分析 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫(huà)問(wèn)題 三、中國(guó)郵路問(wèn)題 四、子圖和樹(shù) 167。 2 有向圖 167。 4 最短路問(wèn)題 167。 3 圖的矩陣表示 45 167。 3 圖的矩陣表示 一、邊矩陣 二、鄰接矩陣 一、邊矩陣（弧矩陣） 167。 3 圖的矩陣表示 定義 314（邊矩陣、弧矩陣） 設(shè)矩陣的行數(shù)為圖的邊（弧）數(shù)，列數(shù)為 2，每行對(duì)應(yīng)于圖的一條邊（?。?，每行的兩個(gè)元素為邊（?。┑亩它c(diǎn)編號(hào)（對(duì)于有向圖 ，規(guī)定第一列元素為弧的始點(diǎn)編號(hào)，第二列元素為弧的終點(diǎn)編號(hào)），這樣的矩陣稱(chēng)為圖的邊（?。┚仃?。 v1 v2 v3 v4 a1 a2 a3 a4 a6 a5 ???????????????????324212143431Ba1 a2 a3 a4 a5 a6 始點(diǎn) 終點(diǎn) 鄰接矩陣：最基本矩陣表示，可表示頂點(diǎn)之間的連通關(guān)系。本章求含負(fù)權(quán)弧網(wǎng)絡(luò)最短路時(shí)須使用 （弧矩陣） 46 167。 3 圖的矩陣表示 二、鄰接矩陣 定義（續(xù)） 二、鄰接矩陣 定義 315（鄰接矩陣） 行、列數(shù)均等于圖的頂點(diǎn)數(shù)，且矩陣元素 aij符合下列規(guī)定的矩陣稱(chēng)為圖的鄰接矩陣： （ 1）對(duì)于有向圖 D： （ 2）對(duì)于無(wú)向圖 G： ? ?? ?????的一條弧不是若的一條弧是若Dv，vDv，vajijiij 01? ?? ?????的一條邊不是若的一條邊是若Dv，vDv，vajijiij 0147 167。 3 圖的矩陣表示 二、鄰接矩陣 鄰接矩陣（例） （ 3）對(duì)于賦權(quán)有向圖 D ： （ 4）對(duì)于賦權(quán)無(wú)向圖 G： ? ?? ?????? 的一條弧不是若的一條弧，且權(quán)值為是若Dv，vwDv，vwajiijjiijij? ?? ?????? 的一條邊不是若的一條邊，且權(quán)值為是若Dv，vwDv，vwajiijjiijij48 167。 3 圖的矩陣表示 二、鄰接矩陣 三、關(guān)聯(lián)矩陣 有向圖 D v1 v2 v3 v4 a1 a2 a3 a4 a6 a5 ? ?? ?????的一條弧不是若的一條弧是若Dv，vDv，vajijiij 01?????????????010100001101010043214321vvvvAvvvv關(guān)聯(lián)矩陣，也稱(chēng)連接矩陣，用來(lái)表示頂點(diǎn)與邊的連接關(guān)系。 鄰接矩陣 49 167。 3 圖的矩陣表示 三、關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣（例） 三、關(guān)聯(lián)矩陣 定義 316（關(guān)聯(lián)矩陣） （ 1）對(duì)于有向圖 D： （ 2）對(duì)于無(wú)向圖 G： 行、列數(shù)分別等于圖的頂點(diǎn)數(shù)和邊數(shù)，且矩陣元素 ijs 符合下列規(guī)定的矩陣稱(chēng)為圖的關(guān)聯(lián)矩陣： ? ????????的端點(diǎn)不是其它情況流入的矢量向頂點(diǎn)若弧流出的矢量從頂點(diǎn)若弧jiijijijavvavas011????不關(guān)聯(lián)與邊若頂點(diǎn)關(guān)聯(lián)與邊若頂點(diǎn)jijiij evevs0150 167。 3 圖的矩陣表示 三、關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣（無(wú)向圖 例） 有向圖 ? ????????的端點(diǎn)不是其它情況流入的矢量向頂點(diǎn)若弧流出的矢量從頂點(diǎn)若弧jiijijijavvavas011v1 v2 v3 v4 a1 a2 a3 a4 a6 a5 ???????????????????0101101000111110000011014321654321vvvvSaaaaaa有向圖的關(guān)聯(lián)矩陣 51 167。 3 圖的矩陣表示 三、關(guān)聯(lián)矩陣 167。 4 最短路問(wèn)題 無(wú)向圖 v1 v2 v3 v4 e1 e2 e3 e4 e6 e5 無(wú)向圖的關(guān)聯(lián)矩陣 ????不關(guān)聯(lián)與邊若頂點(diǎn)關(guān)聯(lián)與邊若頂點(diǎn)jijiij evevs01?????????????0101101000111110000011014321654321vvvvSeeeeee顯然，圖的邊（?。┚仃囆问缴献詈?jiǎn)單，但圖的鄰接矩陣和關(guān)聯(lián)矩陣在連通性判斷和某些優(yōu)化計(jì)算中更具實(shí)用價(jià)值。一般情況下，一個(gè)圖可由它的鄰接矩陣和關(guān)聯(lián)矩陣來(lái)完全決定。 52 主要內(nèi)容 167。 4 最短路問(wèn)題 第三章 圖與網(wǎng)絡(luò)分析 167。 1 圖的基本概念 一、圖、連通圖、賦權(quán)圖 二、一筆畫(huà)問(wèn)題 三、中國(guó)郵路問(wèn)題 四、子圖和樹(shù) 167。 2 有向圖 167。 4 最短路問(wèn)題 167。 3 圖的矩陣表示 53 167。 4 最短路問(wèn)題 一 、 定義 定義 167。 4 最短路問(wèn)題 一、最短路問(wèn)題的定義 v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 例 313 從油田 v1到煉油廠 v8鋪設(shè)管道，管道路線限定范圍如圖 3所示，弧的權(quán)代表路線長(zhǎng)度，求使鋪設(shè)路線長(zhǎng)度最短的方案。 分析： 顯然，在所給路線范圍之內(nèi)，從油田到煉油廠的鋪設(shè)方案不止一個(gè)，且鋪設(shè)路線長(zhǎng)度不同，問(wèn)題的要求是求鋪設(shè)路線長(zhǎng)度最短的方案。 （對(duì)于某些經(jīng)過(guò)變形，可化為多階段決策問(wèn)題的最短路問(wèn)題，可用動(dòng)態(tài)規(guī)劃方法求解） 54 167。 4 最短路問(wèn)題 一 、 定義 二、最短路算法 定義 317（最短路問(wèn)題） 在賦權(quán)有向圖中，求兩個(gè)頂點(diǎn) 1v 到 nv 之間的一條路 *? ，使得這條路上各弧的權(quán)值總和在從1v到nv之間的所有路中是最小的，即： ? ? ? ?? ?n* n Wm i nW 11 ?? ?這種問(wèn)題稱(chēng)為最短路問(wèn)題。 應(yīng)用舉例： 管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。 最短路問(wèn)題不總是與距離有關(guān)的，也可以與時(shí)間、成本、流量、效率等有關(guān)，所以應(yīng)用十分廣泛。 55 167。 4 最短路問(wèn)題 二、最短路算法 標(biāo)號(hào)介紹 二、最短路算法 兩種情況： 1. 所有弧權(quán)為正－狄克斯特拉（ Dijkstra）算法 2. 存在負(fù)弧權(quán)情況（自學(xué)） Dijkstra算法又稱(chēng)標(biāo)號(hào)法，由 E. W. Dijkstra于 1959年首先提出。目前公認(rèn)，在所有弧的權(quán)值均為非負(fù)（即）的情況下，這個(gè)算法是尋求最短路的最好算法。這個(gè)算法不僅能給出從始點(diǎn)到終點(diǎn)的最短路，而且在求解過(guò)程中，實(shí)際還給出了從始點(diǎn)到圖中任意一點(diǎn)的最短路。 1. 所有弧權(quán)為正－狄克斯特拉（ Dijkstra）算法 （ 1） Dijkstra算法 概述 從 v1開(kāi)始，給每一個(gè)頂點(diǎn)一個(gè)有值標(biāo)號(hào)，標(biāo)號(hào)分為 T標(biāo)號(hào)和 P標(biāo)號(hào)兩種。 56 其值表示從始點(diǎn) v1到 vj的最短路的總權(quán)值，稱(chēng)為固定標(biāo)號(hào)。 167。 4 最短路問(wèn)題 二、最短路算法 標(biāo)號(hào)介紹 算法依據(jù)圖示 T標(biāo)號(hào) T（ vj） : P標(biāo)號(hào) P（ vj） : 其值表示從始點(diǎn) v1到 vj的最短路總權(quán)值的上界，稱(chēng)為臨時(shí)標(biāo)號(hào)。 算法開(kāi)始時(shí)， T(v1)=0, 其余 T(vj)=+∞。 凡是得到 P標(biāo)號(hào)的頂點(diǎn)，說(shuō)明已經(jīng)求出 v1到該點(diǎn)的最短路及最短路權(quán)值，其標(biāo)號(hào)不再改變 。 算法目標(biāo) : 逐步求出始點(diǎn) v1到各 T標(biāo)號(hào)頂點(diǎn)的最短路，并將其改為 P標(biāo)號(hào)。當(dāng)所有頂點(diǎn)均為 P標(biāo)號(hào)時(shí)，算法結(jié)束。 算法依據(jù) : 若 1v ， 2v ， … ，nv是從 1v 到nv的最短路，則 1v ， 2v ， … ，1?nv必是從 1v 到1?nv的最短路。 57 167。 4 最短路問(wèn)題 二、最短路算法 算法依據(jù)圖示 （ 2） Dijkstra算法的求解步驟 若 ? ?8654118 vvvvv* ，，?? 是從 1v 到 8v 的最短路， 而 從 1v 到 1?nv 的最短路 不 是 ? ?654116 vvvv* ，，?? ，而是 ? ?6321(1)16 vvvv ，，?? ，則 ? ? ? ?*1686(1)16 )( ?? WvvwW ???， 反證法 : 說(shuō)明 : 8(1)16 v?? 是問(wèn)題的最短路，這與假設(shè)相反。 v6 v1 v2 v3 v4 v5 v7 v8 3 7 7 6 1 6 2 2 1 4 3 (1)16?58 ? 以 ? 標(biāo)出從始點(diǎn) 1v 到0jv的最短路上與0jv相鄰的點(diǎn)，用于反求最短路線。 167。 4 最短路問(wèn)題 二、最短路算法 （ 2） Dijkstra算法的求解步驟 最小 T標(biāo)號(hào)改 P標(biāo)號(hào)的解釋 （ i） （ 2） Dijkstra算法的求解步驟 為始點(diǎn) 1v 標(biāo) P 標(biāo)號(hào) ? ? 01 ?vP ，其余頂點(diǎn)均標(biāo) T 標(biāo)號(hào)? ? ???jvT 。 （ ii） （ iii） 設(shè) iv 為剛剛得到 P 標(biāo)號(hào)的頂點(diǎn)，考慮所有以 iv 為始點(diǎn)的弧的終點(diǎn) jv ，如果其標(biāo)號(hào)為 T 標(biāo)號(hào)，則將其標(biāo)號(hào)修改為： ? ? ? ? ? ?? ?ijijj wvPvTm i nvT ?? ，舊新即現(xiàn)在 vi到 vj的最短路總權(quán)值上限有兩個(gè)，選小者，向最短路總權(quán)值逼近 ? 從所有標(biāo)有 T 標(biāo)號(hào)的頂點(diǎn)中，選擇 T 標(biāo)號(hào)最小的頂點(diǎn)0jv； ?