數(shù)學(xué)建模圖論模型

圖論模型 圖論模型 圖論基本概念最短路徑算法最小生成樹(shù)算法遍歷性問(wèn)題二分圖與匹配 2 網(wǎng)絡(luò)流問(wèn)題關(guān)鍵路徑問(wèn)題系統(tǒng)監(jiān)控模型著色模型 1 圖論的基本概念 問(wèn)題1 哥尼斯堡七橋問(wèn)題 能否從任一陸地出發(fā)通過(guò)每座橋恰好一次而回到出發(fā)點(diǎn) 3 4 歐拉指出 如果每塊陸地所連接的橋都是偶數(shù)座 則從任一陸地出發(fā) 必能通過(guò)每座橋恰好一次而回到出發(fā)地 5 問(wèn)題2 哈密頓環(huán)球旅行問(wèn)題 十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市 能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn) 歐拉問(wèn)題是 邊遍歷 哈密爾頓問(wèn)題是 點(diǎn)遍歷 6 問(wèn)題3 四色問(wèn)題 對(duì)任何一張地圖進(jìn)行著色 兩個(gè)共同邊界的國(guó)家染不同的顏色 則只需要四種顏色就夠了 問(wèn)題4 關(guān)鍵路徑問(wèn)題 一項(xiàng)工程任務(wù) 大到建造一座大壩 一座體育中心 小至組裝一臺(tái)機(jī)床 一架電視機(jī) 都要包括許多工序 這些工序相互約束 只有在某些工序完成之后 一個(gè)工序才能開(kāi)始 即它們之間存在完成的先后次序關(guān)系 一般認(rèn)為這些關(guān)系是預(yù)知的 而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間 這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目 影響工程進(jìn)度的要害工序是哪幾個(gè) 圖的定義 圖論中的 圖 并不是通常意義下的幾何圖形或物體的形狀圖 而是以一種抽象的形式來(lái)表達(dá)一些確定的事物之間的聯(lián)系的一個(gè)數(shù)學(xué)系統(tǒng) 定義1一個(gè)有序二元組 V E 稱為一個(gè)圖 記為G V E 其中 V稱為G的頂點(diǎn)集 V 其元素稱為頂點(diǎn)或結(jié)點(diǎn) 簡(jiǎn)稱點(diǎn) E稱為G的邊集 其元素稱為邊 它聯(lián)結(jié)V中的兩個(gè)點(diǎn) 如果這兩個(gè)點(diǎn)是無(wú)序的 則稱該邊為無(wú)向邊 否則 稱為有向邊 如果V v1 v2 vn 是有限非空點(diǎn)集 則稱G為有限圖或n階圖 8 如果E的每一條邊都是無(wú)向邊 則稱G為無(wú)向圖 如圖1 如果E的每一條邊都是有向邊 則稱G為有向圖 如圖2 否則 稱G為混合圖 圖1圖2 并且常記 V v1 v2 vn V n E e1 e2 em ek vivj E m 稱點(diǎn)vi vj為邊vivj的端點(diǎn) 在有向圖中 稱點(diǎn)vi vj分別為邊vivj的始點(diǎn)和終點(diǎn) 該圖稱為 n m 圖 9 對(duì)于一個(gè)圖G V E 人們常用圖形來(lái)表示它 稱其為圖解 凡是有向邊 在圖解上都用箭頭標(biāo)明其方向 例如 設(shè)V v1 v2 v3 v4 E v1v2 v1v3 v1v4 v2v3 v2v4 v3v4 則G V E 是一個(gè)有4個(gè)頂點(diǎn)和6條邊的圖 G的圖解如下圖所示 10 一個(gè)圖會(huì)有許多外形不同的圖解 下面兩個(gè)圖表示同一個(gè)圖G V E 的圖解 這兩個(gè)圖互為同構(gòu)圖 今后將不計(jì)較這種外形上的差別 而用一個(gè)容易理解的 確定的圖解去表示一個(gè)圖 11 有邊聯(lián)結(jié)的兩個(gè)點(diǎn)稱為相鄰的點(diǎn) 有一個(gè)公共端點(diǎn)的邊稱為相鄰邊 邊和它的端點(diǎn)稱為互相關(guān)聯(lián) 常用d v 表示圖G中與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目 d v 稱為頂點(diǎn)v的度數(shù) 對(duì)于有向圖 還有出度和入度之分 用N v 表示圖G中所有與頂點(diǎn)v相鄰的頂點(diǎn)的集合 d v1 d v3 d v4 4 d v2 2 dout v1 dout v3 dout v4 2 dout v2 1din v1 din v3 din v4 2 din v2 1 12 握手定理 握手定理 無(wú)向圖中 所有結(jié)點(diǎn)的度數(shù)之和等于2m 右圖 推論1 無(wú)向圖中必有偶數(shù)個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn) 推論2 有向圖中所有結(jié)點(diǎn)的出度之和等于入度之和 d v1 d v3 d v4 4 d v2 2 我們今后只討論有限簡(jiǎn)單圖 1 頂點(diǎn)個(gè)數(shù)是有限的 2 任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián) 3 若是無(wú)向圖 則任意兩個(gè)頂點(diǎn)最多只有一條邊與之相聯(lián)結(jié) 4 若是有向圖 則任意兩個(gè)頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié) 當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí) 這兩條邊的方向相反 如果某個(gè)有限圖不滿足 2 3 4 可在某條邊上增設(shè)頂點(diǎn)使之滿足 14 定義2若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F e 則稱F e 為該邊的權(quán) 并稱圖G為賦權(quán)圖 網(wǎng)絡(luò) 記為G V E F 定義3任意兩點(diǎn)均有通路的圖稱為連通圖 定義4連通而無(wú)圈的圖稱為樹(shù) 常用T表示樹(shù) 常用的圖 給定圖G 和G 是兩個(gè)圖 如果有V V和E E 則稱圖G 是圖G的子圖 若V V稱圖G 是圖G的生成子圖 若將圖G的每一條邊e都對(duì)應(yīng)一個(gè)實(shí)數(shù)F e 則稱F e 為該邊的權(quán) 并稱圖G為賦權(quán)圖 網(wǎng)絡(luò) 記為G 任意兩點(diǎn)均有通路的圖稱為連通圖 連通而無(wú)圈的圖稱為樹(shù) 常用T 表示樹(shù) 若圖G 是圖G的生成子圖 且G 又是一棵樹(shù) 則稱G 是圖G的生成樹(shù) 例Ramsey問(wèn)題 問(wèn)題 任何6個(gè)人的聚會(huì) 其中總會(huì)有3個(gè)互相認(rèn)識(shí)或3人互相不認(rèn)識(shí) 圖論模型 用紅 藍(lán)兩種顏色對(duì)6個(gè)頂點(diǎn)的完全圖K6的邊進(jìn)行任意著色 則不論如何著色必然都存在一個(gè)紅色的K3或一個(gè)藍(lán)色的K3 對(duì)應(yīng)關(guān)系 每個(gè)人即為一個(gè)結(jié)點(diǎn) 人與人之間的關(guān)系即為一條邊 例Ramsey問(wèn)題 圖論證明 用紅 藍(lán)兩種顏色對(duì)K6的邊進(jìn)行著色 K6的任意一個(gè)頂點(diǎn)均有5條邊與之相連接 這5條邊必有3條邊的顏色是相同的 不妨設(shè)為藍(lán)色 如圖 與這3條邊相關(guān)聯(lián)的另外3個(gè)節(jié)點(diǎn)之間的3條邊 若都為紅色 則形成紅色的K3 若另外3個(gè)節(jié)點(diǎn)之間的3條邊有一條為藍(lán)色 則與上面的藍(lán)色邊形成藍(lán)色的K3 因此必然存在一個(gè)紅色的K3或一個(gè)藍(lán)色的K3 例Ramsey問(wèn)題 Ramsey數(shù) R 3 3 6 R 3 4 9 18 例過(guò)河問(wèn)題 問(wèn)題 一擺渡人欲將一只狼 一頭羊 一籃菜從河西渡過(guò)河到河?xùn)| 由于船小 一次只能帶一物過(guò)河 并且狼與羊 羊與菜不能獨(dú)處 給出渡河方法 這里顯然不能用一個(gè)節(jié)點(diǎn)表示一個(gè)物體 一個(gè)物體可能在河?xùn)| 也可能在河西 也可能在船上 狀態(tài)表示不清楚 另外 問(wèn)題也可以分成幾個(gè)小問(wèn)題 如 問(wèn)題是否能解 有幾種不同的解法 最快的解決方案是什么 例過(guò)河問(wèn)題 解 用四維0 1向量表示 人 狼 羊 菜 在河西岸的狀態(tài) 在河西岸則分量取1 否則取0 共有24 16種狀態(tài) 在河?xùn)|岸的狀態(tài)類似記作 由題設(shè) 狀態(tài) 0 1 1 0 0 0 1 1 0 1 1 1 是不允許的 其對(duì)應(yīng)狀態(tài) 1 0 0 1 1 1 0 0 1 0 0 0 也是不允許的 以可允許的10個(gè)狀態(tài)向量作為頂點(diǎn) 將可能互相轉(zhuǎn)移的狀態(tài)用邊連接起來(lái)構(gòu)成一個(gè)圖 利用圖論的相關(guān)知識(shí)即可回答原問(wèn)題 例過(guò)河問(wèn)題 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 河西 人 狼 羊 菜 河?xùn)| 人 狼 羊 菜 將10個(gè)頂點(diǎn)分別記為A1 A2 A10 從圖中易得到兩條路 A1A6A3A7A2A8A5A10 A1A6A3A9A4A8A5A10 問(wèn)題的轉(zhuǎn)換 過(guò)河問(wèn)題是否能解 即 圖中A1到A10是否連通 有幾種不同的解法 即 A1到A10之間有多少條不同的路徑 最快的解決方案是什么 即 A1到A10最短路徑有哪些 圖的矩陣表示 鄰接矩陣 鄰接矩陣表示了點(diǎn)與點(diǎn)之間的鄰接關(guān)系 一個(gè)n階圖G的鄰接矩陣A aij n n 其中 22 23 無(wú)向圖G的鄰接矩陣A是一個(gè)對(duì)稱矩陣 權(quán)矩陣一個(gè)n階賦權(quán)圖G V E F 的權(quán)矩陣A aij n n 其中 有限簡(jiǎn)單圖基本上可用權(quán)矩陣來(lái)表示 24 無(wú)向圖G的權(quán)矩陣A是一個(gè)對(duì)稱矩陣 25 關(guān)聯(lián)矩陣 一個(gè)有m條邊的n階有向圖G的關(guān)聯(lián)矩陣A aij n m 其中 若vi是ej的始點(diǎn) 若vi是ej的終點(diǎn) 若vi與ej不關(guān)聯(lián) 有向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有一個(gè)1 有且僅有一個(gè) 1 26 一個(gè)有m條邊的n階無(wú)向圖G的關(guān)聯(lián)矩陣A aij n m 其中 若vi與ej關(guān)聯(lián) 若vi與ej不關(guān)聯(lián) 無(wú)向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)1 2 最短路徑算法 定義1設(shè)P u v 是賦權(quán)圖G V E F 中從點(diǎn)u到v的路徑 用E P 表示路徑P u v 中全部邊的集合 記 則稱F P 為路徑P u v 的權(quán)或長(zhǎng)度 距離 定義2若P0 u v 是G中連接u v的路徑 且對(duì)任意在G中連接u v的路徑P u v 都有F P0 F P 則稱P0 u v 是G中連接u v的最短路 28 重要性質(zhì) 若v0v1 vm是圖G中從v0到vm的最短路 則 1 k m v0v1 vk必為G中從v0到vk的最短路 即 最短路是一條路 且最短路的任一段也是最短路 求非負(fù)賦權(quán)圖G中某一點(diǎn)到其它各點(diǎn)最短路 一般用Dijkstra標(biāo)號(hào)算法 求非負(fù)賦權(quán)圖上任意兩點(diǎn)間的最短路 一般用Floyd算法 這兩種算法均適用于有向非負(fù)賦權(quán)圖 下面分別介紹兩種算法的基本過(guò)程 Dijkstra算法 指標(biāo) a為起點(diǎn) 設(shè)T為V的子集 P V T且a T 對(duì)所有t T 設(shè)l t 表示從a到t的所有通路中距離最短的一條的長(zhǎng)度 且這條路徑中不包含T中其他的結(jié)點(diǎn) 則稱l t 為t關(guān)于集合P的指標(biāo) 若不存在這樣的路徑 這記l t 注 l t 不一定是從a到t的最短路徑 因?yàn)樽疃搪窂街锌赡馨琓中其他的節(jié)點(diǎn) 定理1若t是T中關(guān)于P由最小指標(biāo)的結(jié)點(diǎn) 則l t 是a和t之間的最短距離 定理2設(shè)T為V的子集 P V T 設(shè) 1 對(duì)P中的任一點(diǎn)p 存在一條從a到p的最短路徑 這條路徑僅有P中的點(diǎn)構(gòu)成 2 對(duì)于每一點(diǎn)t 它關(guān)于P的指標(biāo)為l t 令x為最小指標(biāo)所在的點(diǎn) 即 3 令P PU x T T x l t 表示T 中結(jié)點(diǎn)t關(guān)于P 的指標(biāo) 則 29 Dijkstra算法 求a點(diǎn)到其他點(diǎn)的最短路徑 1 初始化 P a T V a 對(duì)每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)l t w a t 2 設(shè)x為T(mén)中關(guān)于P有最小指標(biāo)的點(diǎn) 即 l x min l t t T 3 若T 則算法結(jié)束 否則 令P PU x T T x 按照公式l t min l t l x w x t 計(jì)算T 中每一個(gè)結(jié)點(diǎn)t 關(guān)于P 的指標(biāo) 4 P 代替P T 代替T 重復(fù)步驟2 3 其中 w x y 為圖的權(quán)矩陣 30 改進(jìn)Dijkstra算法 求a點(diǎn)到其他點(diǎn)的最短路徑 1 初始化 P a T V a 對(duì)每個(gè)結(jié)點(diǎn)t計(jì)算指標(biāo)l t w a t pro t a 2 設(shè)x為T(mén)中關(guān)于P有最小指標(biāo)的點(diǎn) 即 l x min l t t T 3 若T 則算法結(jié)束 否則 令P PU x T T x 按照公式l t min l t l x w x t 計(jì)算T 中每一個(gè)結(jié)點(diǎn)t 關(guān)于P 的指標(biāo) 若l x w x t l t pro t x 4 P 代替P T 代替T 重復(fù)步驟2 3 其中 w x y 為圖的權(quán)矩陣 31 例求下圖中A點(diǎn)到其他點(diǎn)的最短路 32 Floyd算法 求任意兩點(diǎn)的最短路徑 設(shè)A aij n n為賦權(quán)圖G V E F 的權(quán)矩陣 dij表示從vi到vj點(diǎn)的距離 rij表示從vi到vj點(diǎn)的最短路中前一個(gè)點(diǎn)的編號(hào) 賦初值 對(duì)所有i j dij aij rij j k 1 轉(zhuǎn)向 更新dij rij 對(duì)所有i j 若dik dkj dij 則令dij dik dkj rij k 轉(zhuǎn)向 終止判斷 若k n終止 否則令k k 1 轉(zhuǎn)向 最短路線可由rij得到 例求下圖中任意兩點(diǎn)間的最短路 34 例設(shè)備更新問(wèn)題 某企業(yè)每年年初 都要作出決定 如果繼續(xù)使用舊設(shè)備 要付維修費(fèi) 若購(gòu)買(mǎi)一臺(tái)新設(shè)備 要付購(gòu)買(mǎi)費(fèi) 試制定一個(gè)5年更新計(jì)劃 使總支出最少 已知設(shè)備在每年年初的購(gòu)買(mǎi)費(fèi)分別為11 11 12 12 13 使用不同時(shí)間設(shè)備所需的維修費(fèi)分別為5 6 8 11 18 解設(shè)bi表示設(shè)備在第i年年初的購(gòu)買(mǎi)費(fèi) ci表示設(shè)備使用i年后的維修費(fèi) V v1 v2 v6 點(diǎn)vi表示第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備 虛設(shè)一個(gè)點(diǎn)v6表示第5年年底 E vivj 1 i j 6 每條邊vivj表一臺(tái)設(shè)備 從第i年年初購(gòu)買(mǎi)使用到第j年年初報(bào)廢 36 這樣上述設(shè)備更新問(wèn)題就變?yōu)?在有向賦權(quán)圖G V E F 圖解如下 中求v1到v6的最短路問(wèn)題 37 由實(shí)際問(wèn)題可知 設(shè)備使用三年后應(yīng)當(dāng)更新 因此刪除該圖中v1到v5 v1到v6 v2到v6的連線 又設(shè)備使用一年后就更新則不劃算 因此再刪除該圖中v1v2 v2v3 v3v4 v4v5 v5v6五條連線后得到 從上圖中容易得到v1到v6只有兩條路 v1v3v6和v1v4v6 而這兩條路都是v1到v6的最短路 3 最小生成樹(shù) 由樹(shù)的定義不難知道 任意一個(gè)連通的 n m 圖G適當(dāng)去掉m n 1條邊后 都可以變成樹(shù) 這棵樹(shù)稱為圖G的生成樹(shù) 設(shè)T是圖G的一棵生成樹(shù) 用F T 表示樹(shù)T中所有邊的權(quán)數(shù)之和 F T 稱為樹(shù)T的權(quán) 一個(gè)連通圖G的生成樹(shù)一般不止一棵 圖G的所有生成樹(shù)中權(quán)數(shù)最小的生成樹(shù)稱為圖G的最小生成樹(shù) Minimum costSpanningTree MST 求最小生成樹(shù)問(wèn)題有很廣泛的實(shí)際應(yīng)用 例如 把n個(gè)鄉(xiāng)鎮(zhèn)用高壓電纜連接起來(lái)建立一個(gè)電網(wǎng) 使所用的電纜長(zhǎng)度之和最短 即費(fèi)用最小 就是一個(gè)求最小生成樹(shù)問(wèn)題 Kruskal算法 39 從未選入樹(shù)中的邊中選取權(quán)重最小的且不構(gòu)成回路的邊加入到樹(shù)中 判斷回路比較麻煩 算法過(guò)程 1 將各邊按權(quán)值從小到大進(jìn)行排序2 找出權(quán)值最小且不與已加入最小生成樹(shù)集合的邊構(gòu)成回路的邊 若符合條件 則加入最小生成樹(shù)的集合中 不符合條件則繼續(xù)遍歷圖 尋找下一個(gè)最小權(quán)值的邊 3 遞歸重復(fù)步驟1 直到找出n 1條邊為止 得到最小生成樹(shù) 時(shí)間復(fù)雜度只和邊有關(guān) 可以證明其時(shí)間復(fù)雜度為O mlogm 求最小生成樹(shù) 40 Prim算法 41 把結(jié)點(diǎn)分成兩個(gè)集合 已加入樹(shù)中的 P 和未加入樹(shù)中的 Q 然后每次選擇一個(gè)點(diǎn)在P中一個(gè)點(diǎn)在Q中的權(quán)重最小的邊 加入樹(shù)中 并把相應(yīng)點(diǎn)加入P中 類似地 可定義連通圖G的最大生成樹(shù) 算法過(guò)程 1 初始化 任取一個(gè)節(jié)點(diǎn)u加入生成樹(shù) P u0 Q V u0 生成樹(shù)的邊集TE 2 在所有u P v Q的邊 u v 稱為可選邊集 中 找一條權(quán)重最小的邊 u1 v1 將此邊加進(jìn)集合TE中 并將v加入P中 同時(shí)對(duì)與v關(guān)聯(lián)的邊 若另一個(gè)端點(diǎn)已經(jīng)在P中 則從可選邊集中刪除 否則加入可選邊集 3 如果P V 則算法結(jié)束 否則重復(fù)步驟2 我們可以算出當(dāng)U V時(shí) 步驟2共執(zhí)行了n 1次 TE中也增加了n 1條邊 這n 1條邊就是需要求出的最小生成樹(shù)的邊 例選址問(wèn)題 現(xiàn)準(zhǔn)備在n個(gè)居民點(diǎn)v1 v2 vn中設(shè)置一銀行 問(wèn)設(shè)在哪個(gè)點(diǎn) 可使最大服務(wù)距離最小 若設(shè)置兩個(gè)銀行 問(wèn)設(shè)在哪兩個(gè)點(diǎn) 模型假設(shè)假設(shè)各個(gè)居民點(diǎn)都有條件設(shè)置銀行 并有路相連 且路長(zhǎng)已知 模型建立與求解用Floyd算法求出任意兩個(gè)居民點(diǎn)vi vj之間的最短距離 并用dij表示 設(shè)置一個(gè)銀行 銀行設(shè)在vi點(diǎn)的最大服務(wù)距離為 43 求k 使 即若設(shè)置一個(gè)銀行 則銀行設(shè)在vk點(diǎn) 可使最大服務(wù)距離最小 設(shè)置兩個(gè)銀行 假設(shè)銀行設(shè)在vs vt點(diǎn)使最大服務(wù)距離最小 記 則s t滿足 進(jìn)一步 若設(shè)置多個(gè)銀行呢 4 遍歷性問(wèn)題 一 歐拉圖G V E 為一連通無(wú)向圖經(jīng)過(guò)G中每條邊至少一次的回路稱為巡回 經(jīng)過(guò)G中每條邊正好一次的巡回稱為歐拉巡回 存在歐拉巡回的圖稱為歐拉圖 二 中國(guó)郵遞員問(wèn)題 CPP chinesepostmanproblem 一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件 如何為他 她 設(shè)計(jì)一條最短的投遞路線 從郵局出發(fā) 經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次 最后返回郵局 這一問(wèn)題是我國(guó)管梅谷教授1962年首先提出 國(guó)際上稱之為中國(guó)郵遞員問(wèn)題 44 解法 若本身就是歐拉圖 則直接可以找到一條歐拉巡回就是本問(wèn)題的解 若不是歐拉圖 必定有偶數(shù)個(gè)奇度數(shù)結(jié)點(diǎn) 在這些奇度數(shù)點(diǎn)之間添加一些邊 使之變成歐拉圖 再找出一個(gè)歐拉巡回 具體解法 Fleury算法 Edmonds最小對(duì)集算法 45 三 哈密爾頓圖G V E 為一連通無(wú)向圖經(jīng)過(guò)G中每點(diǎn)一次且正好一次的路徑稱為哈密爾頓路徑 經(jīng)過(guò)G中每點(diǎn)一次且正好一次的回路稱為哈密爾頓回路 存在哈密爾頓回路的圖稱為哈密爾頓圖 四 旅行商問(wèn)題 TSP TravelingSalesmanProblem 一名推銷(xiāo)員準(zhǔn)備前往若干城市推銷(xiāo)產(chǎn)品 如何為他 她 設(shè)計(jì)一條最短的旅行路線 即 從駐地出發(fā) 經(jīng)過(guò)每個(gè)城市恰好一次 最后返回駐地 最小哈密爾頓回路 對(duì)于n個(gè)節(jié)點(diǎn)的旅行商問(wèn)題 n個(gè)節(jié)點(diǎn)的任意一個(gè)全排列都是問(wèn)題的一個(gè)可能解 假設(shè)任意兩個(gè)點(diǎn)之間都有邊 G個(gè)節(jié)點(diǎn)的全排列有 n 1 個(gè) 因此間題歸結(jié)為在 n 1 個(gè)回路中選取最小回路 TSP問(wèn)題的解法屬于NP完全問(wèn)題 一般只研究其近似解法 46 最鄰近算法 1 選取任意一個(gè)點(diǎn)作為起始點(diǎn) 找出與該點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊 形成一條初始路徑 2 找出與最新加入到路徑中的點(diǎn)相關(guān)聯(lián)的權(quán)重最小的邊加入到路徑中 且要求不再路徑中產(chǎn)生回路 3 重復(fù) 2 直到所有的結(jié)點(diǎn)都加入到路徑中 4 將起點(diǎn)和最后加入的結(jié)點(diǎn)之間的邊加入到路徑中 形成Hamilton回路 其他數(shù)值算法 人工神經(jīng)元方法 遺傳算法等等 47 5 二分圖與匹配 定義1設(shè)X Y都是非空有限集 且X Y E xy x X y Y 稱G X Y E 為二部圖 二部圖可認(rèn)為是有限簡(jiǎn)單無(wú)向圖 如果X中的每個(gè)點(diǎn)都與Y中的每個(gè)點(diǎn)鄰接 則稱G X Y E 為完備二部圖 若F E R 則稱G X Y E F 為二部賦權(quán)圖 二部賦權(quán)圖的權(quán)矩陣一般記作A aij X Y 其中aij F xiyj 49 定義2設(shè)G X Y E 為二部圖 且M E 若M中任意兩條邊在G中均不鄰接 則稱M是二部圖G的一個(gè)匹配 定義3設(shè)M是二部圖G的一個(gè)匹配 如果G的每一個(gè)點(diǎn)都是M中邊的頂點(diǎn) 則稱M是二部圖G的完美匹配 如果G中沒(méi)有另外的匹配M0 使 M0 M 則稱M是二部圖G的最大匹配 在二部賦權(quán)圖G X Y E F 中 權(quán)數(shù)最大的最大匹配M稱為二部賦權(quán)圖G的最佳匹配 顯然 每個(gè)完美匹配都是最大匹配 反之不一定成立 工作安排問(wèn)題之一 50 給n個(gè)工作人員x1 x2 xn安排n項(xiàng)工作y1 y2 yn n個(gè)工作人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)工作 但并不是所有工作人員都能從事任何一項(xiàng)工作 比如x1能做y1 y2工作 x2能做y2 y3 y4工作等 這樣便提出一個(gè)問(wèn)題 對(duì)所有的工作人員能不能都分配一件他所能勝任的工作 我們構(gòu)造一個(gè)二部圖G X Y E 這里X x1 x2 xn Y y1 y2 yn 并且當(dāng)且僅當(dāng)工作人員xi勝任工作yj時(shí) xi與yj才相鄰 于是 問(wèn)題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配 因?yàn)?X Y 所以完美匹配即為最大匹配 51 求二部圖G X Y E 的最大匹配算法 匈牙利算法 交替鏈算法 迭代步驟 從G的任意匹配M開(kāi)始 將X中M的所有非飽和點(diǎn)都給以標(biāo)號(hào)0和標(biāo)記 轉(zhuǎn)向 M的非飽和點(diǎn)即非M的某條邊的頂點(diǎn) 若X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記 則M是G的最大匹配 否則任取X中一個(gè)既有標(biāo)號(hào)又有標(biāo)記 的點(diǎn)xi 去掉xi的標(biāo)記 轉(zhuǎn)向 找出在G中所有與xi鄰接的點(diǎn)yj 若所有這樣的yj都已有標(biāo)號(hào) 則轉(zhuǎn)向 否則轉(zhuǎn)向 52 對(duì)與xi鄰接且尚未給標(biāo)號(hào)的yj都給定標(biāo)號(hào)i 若所有的yj都是M的飽和點(diǎn) 則轉(zhuǎn)向 否則逆向返回 即由其中M的任一個(gè)非飽和點(diǎn)yj的標(biāo)號(hào)i找到xi 再由xi的標(biāo)號(hào)k找到y(tǒng)k 最后由yt的標(biāo)號(hào)s找到標(biāo)號(hào)為0的xs時(shí)結(jié)束 獲得M 增廣路xsyt xiyj 記P xsyt xiyj 重新記M為M P 轉(zhuǎn)向 不必理會(huì)M 增廣路的定義 M P M P M P 是對(duì)稱差 將yj在M中與之鄰接的點(diǎn)xk 給以標(biāo)號(hào)j和標(biāo)記 轉(zhuǎn)向 例求下圖所示二部圖G的最大匹配 53 解 取初始匹配M0 x2y2 x3y3 x5y5 上圖粗線所示 給X中M0的兩個(gè)非飽和點(diǎn)x1 x4都給以標(biāo)號(hào)0和標(biāo)記 如下圖所示 去掉x1的標(biāo)記 將與x1鄰接的兩個(gè)點(diǎn)y2 y3都給以標(biāo)號(hào)1 因?yàn)閥2 y3都是M0的兩個(gè)飽和點(diǎn) 所以將它們?cè)贛0中鄰接的兩個(gè)點(diǎn)x2 x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記 如下圖所示 54 去掉x2的標(biāo)記 將與x2鄰接且尚未給標(biāo)號(hào)的三個(gè)點(diǎn)y1 y4 y5都給以標(biāo)號(hào)2 如下圖所示 因?yàn)閥1是M0的非飽和點(diǎn) 所以順著標(biāo)號(hào)逆向返回依次得到x2 y2 直到x1為0為止 于是得到M0的增廣路x1y2x2y1 記P x1y2 y2x2 x2y1 取M1 M0 P x1y2 x2y1 x3y3 x5y5 則M1是比M多一邊的匹配 如下圖所示 55 再給X中M1的非飽和點(diǎn)x4給以標(biāo)號(hào)0和標(biāo)記 然后去掉x4的標(biāo)記 將與x4鄰接的兩個(gè)點(diǎn)y2 y3都給以標(biāo)號(hào)4 因?yàn)閥2 y3都是M1的兩個(gè)飽和點(diǎn) 所以將它們?cè)贛1中鄰接的兩個(gè)點(diǎn)x1 x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)記 如下圖所示 去掉x1的標(biāo)記 因?yàn)榕cx1鄰接的兩個(gè)點(diǎn)y2 y3都有標(biāo)號(hào)4 所以去掉x3的標(biāo)記 而與x3鄰接的兩個(gè)點(diǎn)y2 y3也都有標(biāo)號(hào)4 此時(shí)X中所有有標(biāo)號(hào)的點(diǎn)都已去掉了標(biāo)記 如下圖所示 因此M1是G的最大匹配 G不存在飽和X的每個(gè)點(diǎn)的匹配 當(dāng)然也不存在完美匹配 工作安排問(wèn)題之二 56 給n個(gè)工作人員x1 x2 xn安排n項(xiàng)工作y1 y2 yn 如果每個(gè)工作人員工作效率不同 要求工作分配的同時(shí)考慮總效率最高 我們構(gòu)造一個(gè)二部賦權(quán)圖G X Y E F 這里X x1 x2 xn Y y1 y2 yn F xiyj 為工作人員xi勝任工作yj時(shí)的工作效率 則問(wèn)題轉(zhuǎn)化為 求二部賦權(quán)圖G的最佳匹配 在求G的最佳匹配時(shí) 總可以假設(shè)G為完備二部賦權(quán)圖 若xi與yj不相鄰 可令F xiyj 0 同樣地 還可虛設(shè)點(diǎn)x或y 使 X Y 如此就將G轉(zhuǎn)化為完備二部賦權(quán)圖 而且不會(huì)影響結(jié)果 57 定義設(shè)G X Y E F 為完備的二部賦權(quán)圖 若L X Y R 滿足 x X y Y L x L y F xy 則稱L為G的一個(gè)可行點(diǎn)標(biāo)記 記相應(yīng)的生成子圖為GL X Y EL F 這里EL xy E L x L y F xy 求完備二部賦權(quán)圖G X Y E F 的最佳匹配算法迭代步驟 設(shè)G X Y E F 為完備的二部賦權(quán)圖 L是其一個(gè)初始可行點(diǎn)標(biāo)記 通常取L x max F xy y Y x X L y 0 y Y 58 M是GL的一個(gè)匹配 若X的每個(gè)點(diǎn)都是飽和的 則M是最佳匹配 否則取M的非飽和點(diǎn)u X 令S u T 轉(zhuǎn)向 記NL S v u S uv GL 若NL S T 則GL沒(méi)有完美匹配 轉(zhuǎn)向 否則轉(zhuǎn)向 調(diào)整標(biāo)記 計(jì)算aL min L x L y F xy x S y Y T 由此得新的可行點(diǎn)標(biāo)記 令L H GL GH 重新給出GL的一個(gè)匹配M 轉(zhuǎn)向 取y NL S T 若y是M的飽和點(diǎn) 轉(zhuǎn)向 否則 轉(zhuǎn)向 設(shè)xy M 則令S S x T T y 轉(zhuǎn)向 在GL中的u y路是M 增廣路 設(shè)為P 并令M M P 轉(zhuǎn)向 6 網(wǎng)絡(luò)流問(wèn)題 59 定義1設(shè)G V E 為有向圖 在V中指定一點(diǎn)稱為發(fā)點(diǎn) 記為vs 和另一點(diǎn)稱為收點(diǎn) 記為vt 其余點(diǎn)叫做中間點(diǎn) 對(duì)每一條邊vivj E 對(duì)應(yīng)一個(gè)非負(fù)實(shí)數(shù)Cij 稱為它的容量 這樣的G稱為容量網(wǎng)絡(luò) 簡(jiǎn)稱網(wǎng)絡(luò) 記作G V E C 定義2網(wǎng)絡(luò)G V E C 中任一條邊vivj有流量fij 稱集合f fij 為網(wǎng)絡(luò)G上的一個(gè)流 滿足下述條件的流f稱為可行流 限制條件 對(duì)每一邊vivj 有0 fij Cij 平衡條件 對(duì)于中間點(diǎn)vk有 fik fkj 即中間點(diǎn)vk的輸入量 輸出量 60 如果f是可行流 則對(duì)收 發(fā)點(diǎn)vt vs有 fsi fjt Wf 即從vs點(diǎn)發(fā)出的物質(zhì)總量 vt點(diǎn)輸入的量 Wf稱為網(wǎng)絡(luò)流f的總流量 上述概念可以這樣來(lái)理解 如G是一個(gè)運(yùn)輸網(wǎng)絡(luò) 則發(fā)點(diǎn)vs表示發(fā)送站 收點(diǎn)vt表示接收站 中間點(diǎn)vk表示中間轉(zhuǎn)運(yùn)站 可行流fij表示某條運(yùn)輸線上通過(guò)的運(yùn)輸量 容量Cij表示某條運(yùn)輸線能承擔(dān)的最大運(yùn)輸量 Wf表示運(yùn)輸總量 可行流總是存在的 比如所有邊的流量fij 0就是一個(gè)可行流 稱為零流 61 所謂最大流問(wèn)題就是在容量網(wǎng)絡(luò)中 尋找流量最大的可行流 實(shí)際問(wèn)題中 一個(gè)網(wǎng)絡(luò)會(huì)出現(xiàn)下面兩種情況 發(fā)點(diǎn)和收點(diǎn)都不止一個(gè) 解決的方法是再虛設(shè)一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt 發(fā)點(diǎn)vs到所有原發(fā)點(diǎn)邊的容量都設(shè)為無(wú)窮大 所有原收點(diǎn)到收點(diǎn)vt邊的容量都設(shè)為無(wú)窮大 網(wǎng)絡(luò)中除了邊有容量外 點(diǎn)也有容量 解決的方法是將所有有容量的點(diǎn)分成兩個(gè)點(diǎn) 如點(diǎn)v有容量Cv 將點(diǎn)v分成兩個(gè)點(diǎn)v 和v 令C v v Cv 最小費(fèi)用流問(wèn)題 62 這里我們要進(jìn)一步探討不僅要使網(wǎng)上的流達(dá)到最大 或者達(dá)到要求的預(yù)定值 而且還要使運(yùn)輸流的費(fèi)用是最小的 這就是最小費(fèi)用流問(wèn)題 最小費(fèi)用流問(wèn)題的一般提法 已知網(wǎng)絡(luò)G V E C 每條邊vivj E除了已給容量Cij外 還給出了單位流量的費(fèi)用bij 0 所謂最小費(fèi)用流問(wèn)題就是求一個(gè)總流量已知的可行流f fij 使得總費(fèi)用 最小 63 特別地 當(dāng)要求f為最大流時(shí) 即為最小費(fèi)用最大流問(wèn)題 設(shè)網(wǎng)絡(luò)G V E C 取初始可行流f為零流 求解最小費(fèi)用流問(wèn)題的迭代步驟 構(gòu)造有向賦權(quán)圖Gf V Ef F 對(duì)于任意的vivj E Ef F的定義如下 當(dāng)fij 0時(shí) vivj Ef F vivj bij 當(dāng)fij Cij時(shí) vjvi Ef F vjvi bij 當(dāng)0 fij Cij時(shí) vivj Ef F vivj bij vjvi Ef F vjvi bij 然后轉(zhuǎn)向 64 求出含有負(fù)權(quán)的有向賦權(quán)圖Gf V Ef F 中發(fā)點(diǎn)vs到收點(diǎn)vt的最短路 若最短路 存在轉(zhuǎn)向 否則f是所求的最小費(fèi)用最大流 停止 增流 vivj與 相同 vivj與 相反 令 min ij vivj 重新定義流f fij 為 其它情況不變 如果Wf大于或等于預(yù)定的流量值 則適當(dāng)減少 值 使Wf等于預(yù)定的流量值 那么f是所求的最小費(fèi)用流 停止 否則轉(zhuǎn)向 65 下面介紹求解有向賦權(quán)圖G V E F 中含有負(fù)權(quán)的最短路的Ford算法 設(shè)邊的權(quán)vivj為wij v1到vi的路長(zhǎng)記為 i Ford算法的迭代步驟 賦初值 1 0 i i 2 3 n 更新 i i 2 3 n i min i min j wji j i 若所有的 i 都無(wú)變化 停止 否則轉(zhuǎn)向 在算法的每一步 i 都是從v1到vi的最短路長(zhǎng)度的上界 若不存在負(fù)長(zhǎng)回路 則從v1到vi的最短路長(zhǎng)度是 i 的下界 經(jīng)過(guò)n 1次迭代后 i 將保持不變 若在第n次迭代后 i 仍在變化時(shí) 說(shuō)明存在負(fù)長(zhǎng)回路 7 關(guān)鍵路徑問(wèn)題 拓?fù)渑判?66 一項(xiàng)工程任務(wù) 大到建造一座大壩 一座體育中心 小至組裝一臺(tái)機(jī)床 一架電視機(jī) 都要包括許多工序 這些工序相互約束 只有在某些工序完成之后 一個(gè)工序才能開(kāi)始 即它們之間存在完成的先后次序關(guān)系 一般認(rèn)為這些關(guān)系是預(yù)知的 而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間 這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目 影響工程進(jìn)度的要害工序是哪幾個(gè) PT Potentialtaskgraph 圖 67 在PT Potentialtaskgraph 圖中 用結(jié)點(diǎn)表示工序 如果工序i完成之后工序j才能啟動(dòng) 則圖中有一條有向邊 i j 其長(zhǎng)度wi表示工序i所需的時(shí)間 這種圖必定不存在有向回路 否則某些工序?qū)⒃谧陨硗瓿芍蟛拍荛_(kāi)始 這顯然不符合實(shí)際情況 在PT圖中增加兩個(gè)虛擬結(jié)點(diǎn)v0和vn 使所有僅為始點(diǎn)的結(jié)點(diǎn)都直接與v0聯(lián)結(jié) v0為新增邊的始點(diǎn) 這些新增邊的權(quán)都設(shè)為0 使所有僅為終點(diǎn)的結(jié)點(diǎn)都直接與vn聯(lián)結(jié) vn為新增邊的終點(diǎn) 這樣得到的圖G仍然不存在有向回路 68 例一項(xiàng)工程由13道工序組成 所需時(shí)間 單位 天 及先行工序如下表所示 P172 工序序號(hào)ABCDEFGHI所需時(shí)間263243842先行工序 AABC DDDDG H工序序號(hào)JKLM所需時(shí)間3856先行工序GH EJK 試問(wèn)這項(xiàng)工程至少需要多少天才能完成 那些工程不能延誤 那些工程可以延誤 最多可延誤多少天 69 先作出該工程的PT圖 由于除了工序A外 均有先行工序 因此不必虛設(shè)虛擬結(jié)點(diǎn)v0 在PT圖中 容易看出各工序先后完成的順序及時(shí)間 虛擬結(jié)點(diǎn) 70 這項(xiàng)工程至少需要多少天才能完成 就是要求A到N的最長(zhǎng)路 此路徑稱為關(guān)鍵路徑 那些工程不能延誤 那些工程可以延誤 最多可延誤多少天 關(guān)鍵路徑上的那些工程不能延誤 關(guān)鍵路徑 最長(zhǎng)路徑 算法 71 定理若有向圖G中不存在有向回路 則可以將G的結(jié)點(diǎn)重新編號(hào)為u1 u2 un 使得對(duì)任意的邊uiuj E G 都有i j 各工序最早啟動(dòng)時(shí)間算法步驟 根據(jù)定理對(duì)結(jié)點(diǎn)重新編號(hào)為u1 u2 un 賦初值 u1 0 依次更新 uj j 2 3 n uj max ui ui uj uiuj E G 結(jié)束 其中 uj 表示工序uj最早啟動(dòng)時(shí)間 而 un 即 vn 是整個(gè)工程完工所需的最短時(shí)間 72 此例不必重新編號(hào) 只要按字母順序即可 A 0 B C 2 D 8 E max 2 3 8 2 10 F G H D 2 10 I max G 8 H 4 18 J G 8 18 K max E 4 H 4 14 L J 3 21 M K 8 22 N max F 3 I 2 L 5 M 6 28 關(guān)鍵路徑 73 通過(guò)以上計(jì)算表明 這項(xiàng)工程至少需要28天才能完成 關(guān)鍵路徑 最長(zhǎng)路徑 A B D E K M NA B D H K M N 工序A B D E H K M不能延誤 否則將影響工程的完成 但是對(duì)于不在關(guān)鍵路徑上的工序 是否允許延誤 如果允許 最多能夠延誤多長(zhǎng)時(shí)間呢 各工序允許延誤時(shí)間t uj 等于各工序最晚啟動(dòng)時(shí)間 uj 減去各工序最早啟動(dòng)時(shí)間 uj 即t uj uj uj 74 最晚啟動(dòng)時(shí)間算法步驟 已知結(jié)點(diǎn)重新編號(hào) 賦初值 un un 更新 uj j n 1 n 2 1 uj min ui ui uj uiuj E G 結(jié)束 順便提一句 根據(jù)工序uj允許延誤時(shí)間t uj 是否為0 可判斷該工序是否在關(guān)鍵路徑上 75 N 28 M 28 6 22 L 28 5 23 K M 8 14 J L 3 20 I 28 2 26 H min K 4 I 4 10 G min J 8 I 8 12 F 28 3 25 E K 4 10 D min E 2 F 2 G 2 H 2 8 C E 3 7 B D 6 2 A 0 76 各工序允許延誤時(shí)間如下 t A t B t D t E t H t K t M 0 t C 5 t F 15 t G 2 t I 8 t J 2 t L 2 PERT圖 77 在PERT Programmeevaluationandreviewtechnique 圖中 采用有向邊表示工序 其權(quán)值表示該工序所需時(shí)間 如果工序ei完成后ej才能開(kāi)始 則令vk是ei的終點(diǎn) ej的始點(diǎn) 根據(jù)這種約定 前例的PERT圖如下 對(duì)于PERT圖 一些算法與PT圖類似 78 PT圖要比PERT圖好一些 PT圖的結(jié)點(diǎn)數(shù)基本上是固定的 這是最重要的一點(diǎn) 容易編程計(jì)算 另外PT圖比PERT圖更加靈活 它能適應(yīng)一些額外的約束 例如下圖中 表示工序vi完成一半之后vj就可以開(kāi)始 表示工序vi完成后經(jīng)過(guò)t時(shí)刻vj才開(kāi)始 表示在時(shí)間bj之后工序vj才能開(kāi)始 其中v0表示虛擬結(jié)點(diǎn) 8 系統(tǒng)監(jiān)控模型 79 定義1設(shè)圖G V E K V如果圖G的每條邊都至少有一個(gè)頂點(diǎn)在K中 則稱K是G的一個(gè)點(diǎn)覆蓋 若G的一個(gè)點(diǎn)覆蓋中任意去掉一個(gè)點(diǎn)后不再是點(diǎn)覆蓋 則稱此點(diǎn)覆蓋是G的一個(gè)極小點(diǎn)覆蓋 頂點(diǎn)數(shù)最少的點(diǎn)覆蓋 稱為G的最小點(diǎn)覆蓋 例如 右圖中 v0 v2 v3 v5 v6 等都是極小點(diǎn)覆蓋 v0 v1 v3 v5 v0 v2 v4 v6 都是最小點(diǎn)覆蓋 系統(tǒng)監(jiān)控問(wèn)題之一 80 假設(shè)v1 v2 v7是7個(gè)哨所 監(jiān)視著11條路段 如下圖所示 為節(jié)省人力 問(wèn)至少需要在幾個(gè)哨所派人站崗 就可以監(jiān)視全部路段 這就是要求最小點(diǎn)覆蓋問(wèn)題 v1 v3 v5 v6 和 v1 v3 v5 v7 都是最小點(diǎn)覆蓋 所以至少需要在4個(gè)哨所派人站崗來(lái)監(jiān)視全部路段 到目前為止 還沒(méi)有找到求最小點(diǎn)覆蓋的有效算法 即多項(xiàng)式時(shí)間算法 算法步數(shù)不超過(guò)nc n為G的頂點(diǎn)數(shù) c為常數(shù) 有一些啟發(fā)式近似算法 最大獨(dú)立點(diǎn)集 81 定義2設(shè)圖G V E I V如果I中任意兩個(gè)頂點(diǎn)在G中都不相鄰 則稱I是G的一個(gè)獨(dú)立點(diǎn)集 若G的一個(gè)獨(dú)立點(diǎn)集中 任意添加一個(gè)點(diǎn)后不再是獨(dú)立點(diǎn)集 則稱此獨(dú)立點(diǎn)集是G的一個(gè)極大獨(dú)立點(diǎn)集 頂點(diǎn)數(shù)最多的獨(dú)立點(diǎn)集 稱為G的最大獨(dú)立點(diǎn)集 例如 右圖中 v1 v4 等都是極大獨(dú)立點(diǎn)集 v1 v3 v5 v2 v2 v6 是最大獨(dú)立點(diǎn)集 最小控制集 82 定義3設(shè)圖G V E D V如果 v V 要么v D 要么v與D的某個(gè)點(diǎn)相鄰 則稱D是G的一個(gè)控制集 若G的一個(gè)控制集中任意去掉一個(gè)點(diǎn)后不再是控制集 則稱此控制集是G的一個(gè)極小控制集 頂點(diǎn)數(shù)最少的控制集 稱為G的最小控制集 例如 右圖中 v1 v3 v5 是極小控制集 v0 是最小控制集 系統(tǒng)監(jiān)控問(wèn)題之二 83 假設(shè)下圖代表一指揮系統(tǒng) 頂點(diǎn)v1 v2 v7表示被指揮的單位 邊表示可以直接下達(dá)命令的通信線路 欲在某些單位建立指揮站 以便可以通過(guò)指揮站直接給各單位下達(dá)命令 問(wèn)至少需要建立幾個(gè)指揮站 這就是要求最小控制集問(wèn)題 v1 v3 v3 v5 等都是最小控制集 所以至少需要在2個(gè)單