第六章圖與網(wǎng)絡分析 6 1圖的基本概念與數(shù)學模型6 2樹圖和圖的最小部分樹6 3最短路問題6 4中國郵路問題6 5網(wǎng)絡最大流問題6 6網(wǎng)絡模型的實際應用 第六章圖與網(wǎng)絡分析 圖是一種模型 如公路 鐵路交通圖 通訊網(wǎng)絡圖等 圖是對現(xiàn)實的抽象 以點和線段的連接組合表示 6 1圖的基本概念和模型 一 概念 1 圖 點V和邊E的集合 用以表示對某種現(xiàn)實事物的抽象 記作G V E V v1 v2 vn E e1 e2 em 點 表示所研究的事物對象 邊 表示事物之間的聯(lián)系 v1 v2 v3 v4 v0 e1 e2 e3 e4 e5 e6 e7 e0 2 若邊e的兩個端點重合 則稱e為環(huán) 3 多重邊 若某兩端點之間多于一條邊 則稱為多重邊 4 簡單圖 無環(huán) 無多重邊的圖稱為簡單圖 5 鏈 點和邊的交替序列 其中點可重復 但邊不能重復 6 路 點和邊的交替序列 但點和邊均不能重復 7 圈 始點和終點重合的鏈 8 回路 始點和終點重合的路 9 連通圖 若一個圖中 任意兩點之間至少存在一條鏈 稱這樣的圖為連通圖 10 子圖 部分圖 設圖G1 V1 E1 G2 V2 E2 如果有V1 V2 E1 E2 則稱G1是G2的一個子圖 若V1 V2 E1 E2 則稱G1是G2的一個部分圖 11 次 某點的關聯(lián)邊的個數(shù)稱為該點的次 以d vi 表示 二 圖的模型 例 有甲 乙 丙 丁 戊 己六名運動員報名參加A B C D E F六個項目的比賽 如表中所示 打 的項目是各運動員報名參加比賽的項目 問 六個項目的比賽順序應如何安排 才能做到使每名運動員不連續(xù)地參加兩項比賽 甲乙丙丁戊己 項目 人 ABCDEF 建立模型 解 項目作為研究對象 排序 設點 表示運動項目 邊 若兩個項目之間無同一名運動員參加 A B C D E F A C D E F B A F E D C B A C B F E D A F B C D E 順序 6 2樹圖和圖的最小部分樹 1 樹 無圈的連通圖稱為樹圖 簡稱為樹 一 樹圖的概念 2 樹的特性 樹是邊數(shù)最多的無圈連通圖 在樹中任加一條邊 就會形成圈 樹是邊數(shù)最少的連通圖 在樹中任減一條邊 則不連通 3 圖的最小部分樹 定義 若G1是G2的一個部分圖 且為樹圖 則稱G1是G2的一個部分樹 G2 A B C D 5 4 7 3 6 5 5 7 6 G1 A C B D 定義 樹枝總長為最短的部分樹稱為圖的最小部分樹 二 最小部分樹的求法 例 要在下圖所示的各個位置之間建立起通信網(wǎng)絡 試確定使總距離最佳的方案 樹枝 樹圖中的邊稱為樹枝 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分樹長Lmin 14 1 避圈法 1 避圈法 將圖中所有的點分V為V兩部分 V 最小部分樹內(nèi)點的集合V 非最小部分樹內(nèi)點的集合 任取一點vi加粗 令vi V 取V中與V相連的邊中一條最短的邊 vi vj 加粗 vi vj 令vj V 重復 至所有的點均在V之內(nèi) 2 破圈法 任取一圈 去掉其中一條最長的邊 重復 至圖中不存在任何的圈為止 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 最小部分樹長Lmin 14 2 破圈法 6 3最短路問題 在圖示的網(wǎng)絡圖中 從給定的點S出發(fā) 要到達目的地T 問 選擇怎樣的行走路線 可使總行程最短 方法 Dijkstra D氏 標號法 按離出發(fā)點的距離由近至遠逐漸標出最短距離和最佳行進路線 S 1 求某兩點間最短距離的D Dijkstra 氏標號法 2 4 7 S A B C D E T 2 5 2 4 1 4 3 1 7 5 5 7 0 2 4 4 7 8 9 14 13 5 9 4 最短路線 S A B E D T最短距離 Lmin 13 2 求任意兩點間最短距離的矩陣算法 構(gòu)造任意兩點間直接到達的最短距離矩陣D 0 dij 0 SABCDETS0254 A202 7 B520153 C4 10 4 D 75 015E 34107T 570 D 0 構(gòu)造任意兩點間直接到達 或者最多經(jīng)過1個中間點到達的最短距離矩陣D 1 dij 1 其中dij 1 min dir 0 drj 0 SABCDETS024498 A20237512B42014310C43105411D9745015E8534106T 121011570 D 1 i r j dir 0 drj 0 r dSE 1 min dSS 0 dSE 0 dSA 0 dAE 0 dSB 0 dBE 0 dSC 0 dCE 0 dSD 0 dDE 0 dSE 0 dEE 0 dST 0 dTE 0 8 例如 其中dij 2 min dir 1 drj 1 SABCDETS02448714A20236511B4201439C43105410D8645015E7534106T1411910560 D 2 i r j dir 1 drj 1 r 構(gòu)造任意兩點間最多可經(jīng)過3個中間點到達的最短距離矩陣D 2 dij 2 其中dij 3 min dir 2 drj 2 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 D 3 i r j dir 2 drj 2 r 構(gòu)造任意兩點間最多可經(jīng)過7個中間點到達的最短距離矩陣D 3 dij 3 說明 一般 對于D k dij k 其中dij k min dir k 1 drj k 1 k 0 1 2 3 最多可經(jīng)過2k 1個中間點 其數(shù)列為 0 1 3 7 15 31 2k 1 收斂條件 當D k 1 D k 時 計算結(jié)束 設網(wǎng)絡中有p個點 即有p 2個中間點 則2k 1 1 p 2 2k 1 k 1 log2 p 1 k K log2 p 1 1 計算到k lg p 1 lg2 1時 收斂 計算結(jié)束 例 有7個村鎮(zhèn)要聯(lián)合建立一所小學 已知各村鎮(zhèn)小學生的人數(shù)大致為S 30人 A 40人 B 20人 C 15人 D 35人 E 25人 T 50人 問 學校應建在那一個地點 可使學生總行程最少 SABCDETS02448713A20236511B4201439C43105410D8645015E7534106T1311910560 L 30402015352550 人數(shù) 1325103088010359108651485 T 解 6 4中國郵路問題 問題 一名郵遞員從郵局出發(fā) 試選擇一條最短的投遞路線 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 郵局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 奇點 圖中次為奇數(shù)的點稱為奇點 偶點 圖中次為偶數(shù)的點稱為偶點 結(jié)論 最短投遞路線應具有下述特征 若圖中所有的點均為偶點 則可不重復走遍所有街道 重復走的路線長度應不超過所在回路總長度的一半 步驟 兩兩連接所有的奇點 使之均成為偶點 2 檢查重復走的路線長度 是否不超過其所在回路總長的一半 若超過 則調(diào)整連線 改走另一半 v1 v2 v3 v4 v5 v6 v8 v7 v9 v10 v11 v12 v13 郵局 4 4 4 5 5 1 2 4 1 2 5 4 4 7 4 2 2 投遞距離 L 60 18 78 6 5網(wǎng)絡最大流問題 一 網(wǎng)絡最大流中有關概念 有向圖 含有以箭頭指示方向的邊的網(wǎng)絡圖 弧 有向圖上的邊稱為弧 用 vi vj 表示 弧的容量 弧上通過負載的最大能力 簡稱容量 以cij表示 流 加在網(wǎng)絡每條弧上的一組負載量 以fij表示 可行流 能夠通過網(wǎng)絡的負載量 通常應滿足兩個條件 容量限制條件 對所有的弧 0 fij cij 中間點平衡條件 對任何一個中間點 流入量 流出量 發(fā)點 收點 中間點 流的起源點稱發(fā)點 終到點稱收點 其余的點稱中間點 最大流 能夠通過網(wǎng)絡的最大流量 割集 一組弧的集合 割斷這些弧 能使流中斷 簡稱割 8 8 v1 vs v2 v3 v4 vt 7 5 9 4 9 9 2 0 6 1 5 5 10 8 0 vs 2 v2 2 v1 2 v3 1 v4 1 5 4 cij fij 割的容量 割集中各弧的容量之和 最小割 所有割集中容量之和為最小的一個割集 前向弧 一條發(fā)點到收點鏈中 由發(fā)點指向收點的弧 又稱正向弧 后向弧 一條發(fā)點到收點鏈中 由收點指向發(fā)點的弧 又稱逆向弧 增廣鏈 由發(fā)點到收點之間的一條鏈 如果在前向弧上滿足流量小于容量 即fij0 則稱這樣的鏈為增廣鏈 二 兩個定理定理 網(wǎng)絡的最大流量等于它的最小割集的容量 定理 當網(wǎng)絡中不存在任何增廣鏈時 則網(wǎng)絡達到最大流狀態(tài) s t 6 4 5 3 4 4 8 7 設有如下增廣鏈 f 1 該網(wǎng)絡沒有達到最大流狀態(tài) 三 網(wǎng)絡最大流的標號算法 Ford Fulkerson標號算法 基本思想 尋找增廣鏈 改善流量分布 再重復 直到不存在任何增廣鏈為止 步驟 給始點標號 0 從已標號點i出發(fā) 看與其相關聯(lián)的未標號點j上的弧 對 若有0 fij cij 則可對j點標號 記 i j 其中 j min i cij fij 對 若有0 fji cij 也可對j點標號 記 i j 其中 j min i fji 注 若有多個可標號點 可任選其中之一 若標號中斷 則得到最大流狀態(tài) 否則 重復 繼續(xù)標號 至收點得到標號 轉(zhuǎn) 當收點得到標號 則沿標號得到的增廣鏈進行流量調(diào)整 對 f ij fij t 對 f ij fij t 其余弧上的流量不變 重復上述過程 最小割集 已標號點集合與未標號點集合相連接的弧中 流量 容量的弧 8 8 v1 vs v2 v3 v4 vt 7 6 9 5 9 9 2 0 6 0 5 5 10 9 5 3 0 vs 1 v2 1 v1 1 最大流量 fmax 14 最小割集 v3 vt v2 v4 6 6網(wǎng)絡模型的實際應用 例1 王經(jīng)理花費12000元購買了一臺微型車 以后年度的維護費用取決于年初時汽車的役齡 如表示 為避免使用舊車帶來較高的維護費用 王經(jīng)理可選擇賣掉舊車 購買新車使用的方案 舊車的預計收入如表示 為簡化計算 假定任何時刻購買新車都需花費12000元 王經(jīng)理的目標是使凈費用最小 購置費 維護費 賣舊車收入 役齡 年 年維護費 預計收入 單位 元 012345 200040005000900012000 70006000200010000 解 用網(wǎng)絡圖模型描述 歸結(jié)為最短路問題 7 7 7 7 7 1 2 3 4 5 6 12 12 12 12 21 21 21 31 31 44 1年初 5年末 例2 圖示島嶼與河岸有數(shù)座橋相聯(lián) 問至少需要炸毀幾座橋 可中斷兩岸的交通 A B C D E F A B C F E D 2 2 2 1 3 1 1 1 1 例3 有3根相同的軸A1 A2 A3 另有三根相同的齒輪B1 B2 B3 因為精度不高 不能做到任意的互相配合 其中A1能與B1 B2配合 A2能與B2 B3配合 A3能與B1 B3配合 要求確定合適的配合方案 以得到最多的配合數(shù) 將此問題歸為網(wǎng)絡最大流問題 A1 A2 A3 B1 B2 B3 1 1 1 1 1 1 S T 1 1 1 1 1 1