數(shù)模培訓-圖論模型

圖論模型主講：費文龍Feiwl.wokufeiwl@數(shù)學建模培訓.圖論模型圖論根本概念最短途徑算法最小生成樹算法遍歷性問題二分圖與匹配網(wǎng)絡流問題關鍵途徑問題系統(tǒng)監(jiān)控模型著色模型.1、圖論的根本概念ABCD哥尼斯堡七橋表示圖問題1(哥尼斯堡七橋問題):能否從任一陸地出發(fā)經(jīng)過每座橋恰好一次而回到出發(fā)點？.ABDC七橋問題模擬圖歐拉指出：假設每塊陸地所銜接的橋都是偶數(shù)座，那么從任一陸地出發(fā)，必能經(jīng)過每座橋恰好一次而回到出發(fā)地..問題2(哈密頓環(huán)球游覽問題):十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圈〔環(huán)球游覽游戲〕.問題3(四色問題):對任何一張地圖進展著色，兩個共同邊境的國家染不同的顏色，那么只需求四種顏色就夠了.問題4(關鍵途徑問題):一項工程義務,大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束,只需在某些工序完成之后,一個工序才干開場.即它們之間存在完成的先后次序關系,普通以為這些關系是預知的,而且也可以估計完成每個工序所需求的時間.這時工程指點人員迫切希望了解最少需求多少時間才可以完成整個工程工程,影響工程進度的關鍵工序是哪幾個？.圖的定義圖論中的“圖〞并不是通常意義下的幾何圖形或物體的外形圖,而是以一種籠統(tǒng)的方式來表達一些確定的事物之間的聯(lián)絡的一個數(shù)學系統(tǒng).定義1一個有序二元組(V,E)稱為一個圖,記為G=(V,E),其中①V稱為G的頂點集,V≠,其元素稱為頂點或結點,簡稱點;②E稱為G的邊集,其元素稱為邊,它結合V中的兩個點,假設這兩個點是無序的,那么稱該邊為無向邊,否那么,稱為有向邊.假設V={v1,v2,…,vn}是有限非空點集,那么稱G為有限圖或n階圖..假設E的每一條邊都是無向邊,那么稱G為無向圖(如圖1);假設E的每一條邊都是有向邊,那么稱G為有向圖(如圖2);否那么,稱G為混合圖.圖1圖2并且常記V={v1,v2,…,vn},|V|=n;E={e1,e2,…,em}(ek=vivj),|E|=m.稱點vi,vj為邊vivj的端點.在有向圖中,稱點vi,vj分別為邊vivj的始點和終點.該圖稱為(n,m)圖.對于一個圖G=(V,E),人們常用圖形來表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標明其方向.例如,設V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},那么G=(V,E)是一個有4個頂點和6條邊的圖,G的圖解如以下圖所示..一個圖會有許多外形不同的圖解,下面兩個圖表示同一個圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.這兩個圖互為同構圖,今后將不計較這種外形上的差別,而用一個容易了解的、確定的圖解去表示一個圖..有邊結合的兩個點稱為相鄰的點,有一個公共端點的邊稱為相鄰邊.邊和它的端點稱為相互關聯(lián).常用d(v)表示圖G中與頂點v關聯(lián)的邊的數(shù)目,d(v)稱為頂點v的度數(shù).對于有向圖,還有出度和入度之分.用N(v)表示圖G中一切與頂點v相鄰的頂點的集合.d(v1)=d(v3)=d(v4)=4,d(v2)=2.握手定理：.我們今后只討論有限簡單圖：(1)頂點個數(shù)是有限的;(2)恣意一條邊有且只需兩個不同的點與它相互關聯(lián);(3)假設是無向圖,那么恣意兩個頂點最多只需一條邊與之相結合;(4)假設是有向圖,那么恣意兩個頂點最多只需兩條邊與之相結合.當兩個頂點有兩條邊與之相結合時，這兩條邊的方向相反.假設某個有限圖不滿足(2)(3)(4),可在某條邊上增設頂點使之滿足..定義2假設將圖G的每一條邊e都對應一個實數(shù)F(e),那么稱F(e)為該邊的權,并稱圖G為賦權圖(網(wǎng)絡),記為G=(V,E,F).定義3恣意兩點均有通路的圖稱為連通圖.定義4連通而無圈的圖稱為樹,常用T表示樹..例一擺渡人欲將一只狼,一頭羊,一籃菜從河西渡過河到河東.由于船小,一次只能帶一物過河，并且狼與羊,羊與菜不能獨處.給出渡河方法.解：用四維0-1向量表示(人,狼,羊,菜)在河西岸的形狀(在河西岸那么分量取1,否那么取0),共有24=16種形狀.在河東岸的形狀類似記作.由題設,形狀(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允許的,從而對應形狀(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允許的.以可允許的10個形狀向量作為頂點,將能夠相互轉移的形狀用線段銜接起來構成一個圖.根據(jù)此圖便可找到渡河方法..(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)河西=(人,狼,羊,菜)河東=(人,狼,羊,菜)將10個頂點分別記為A1,A2,…,A10,那么渡河問題化為在該圖中求一條從A1到A10的路.從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10..圖的矩陣表示⑴鄰接矩陣鄰接矩陣表示了點與點之間的鄰接關系.一個n階圖G的鄰接矩陣A=(aij)n×n,其中.無向圖G的鄰接矩陣A是一個對稱矩陣.⑵權矩陣一個n階賦權圖G=(V,E,F)的權矩陣A=(aij)n×n,其中有限簡單圖根本上可用權矩陣來表示..無向圖G的權矩陣A是一個對稱矩陣..⑶關聯(lián)矩陣〔略〕一個有m條邊的n階有向圖G的關聯(lián)矩陣A=(aij)n×m,其中假設vi是ej的始點;假設vi是ej的終點;假設vi與ej不關聯(lián).有向圖的關聯(lián)矩陣每列的元素中有且僅有一個1,有且僅有一個-1..一個有m條邊的n階無向圖G的關聯(lián)矩陣A=(aij)n×m,其中假設vi與ej關聯(lián);假設vi與ej不關聯(lián).無向圖的關聯(lián)矩陣每列的元素中有且僅有兩個1..2、最短途徑算法定義1設P(u,v)是賦權圖G=(V,E,F)中從點u到v的途徑,用E(P)表示途徑P(u,v)中全部邊的集合,記那么稱F(P)為途徑P(u,v)的權或長度(間隔).定義2假設P0(u,v)是G中銜接u,v的途徑,且對恣意在G中銜接u,v的途徑P(u,v)都有F(P0)≤F(P),那么稱P0(u,v)是G中銜接u,v的最短路..重要性質：假設v0v1…vm是圖G中從v0到vm的最短路,那么1≤k≤m,v0v1…vk必為G中從v0到vk的最短路.即：最短路是一條路，且最短路的任一段也是最短路.求非負賦權圖G中某一點到其它各點最短路，普通用Dijkstra標號算法；求非負賦權圖上恣意兩點間的最短路，普通用Floyd算法.這兩種算法均適用于有向非負賦權圖.下面分別引見兩種算法的根本過程..Dijkstra算法目的〔a為起點〕

設T為V的子集，P=V-T且a∈T，對一切t∈T，設l(t)表示從a到t的一切通路中間隔最短的一條的長度，且這條途徑中不包含T中其他的結點，那么稱l(t)為t關于集合P的目的，假設不存在這樣的途徑，這記l(t)=∞注：l(t)不一定是從a到t的最短途徑，由于最短途徑中能夠包含T中其他的節(jié)點。定理1

假設t是T中關于P由最小目的的結點，那么l(t)是a和t之間的最短間隔。定理2

設T為V的子集，P=V-T，設

(1)對P中的任一點p,存在一條從a到p的最短途徑,這條途徑僅有P中的點構成,

(2)對于每一點t,它關于P的目的為l(t),令x為最小目的所在的點,即:l(x)=min(l(t))(tT),

(3)令P'=P{x},T'=T-{x},l'(t)表示T'中結點t關于P'的目的,那么

l'(t)=min{l(t),l(x)+w(x,t)}.Dijkstra算法〔求a點到其他點的最短途徑〕1、初始化，P={a}，T=V-{a}，對每個結點t計算目的l(t)=w(a,t)2、設x為T中關于P有最小目的的點,

即:l(x)=min(l(t))(t∈T),3、假設T=Ф,那么算法終了;

否那么,令P'=PU{x},T'=T-{x}

按照公式l'(t)=min{l(t),l(x)+w(x,t)},

計算T'中每一個結點t'關于P'的目的.4、P'替代P,T'替代T,反復步驟2,3〔其中：w(x,y)為圖的權矩陣〕.改良Dijkstra算法〔求a點到其他點的最短途徑〕1、初始化，P={a}，T=V-{a}，對每個結點t計算目的l(t)=w(a,t),pro(t)=a;2、設x為T中關于P有最小目的的點,

即:l(x)=min(l(t))(t∈T);3、假設T=Ф,那么算法終了;

否那么,令P‘=PU{x},T’=T-{x}

按照公式l‘(t)=min{l(t),l(x)+w(x,t)},

計算T’中每一個結點t‘關于P’的目的.

假設l(x)+w(x,t)<l(t),pro(t)=x;4、P'替代P,T'替代T,反復步驟2,3〔其中：w(x,y)為圖的權矩陣〕.ABCDEFGHA02∞∞∞∞6∞B207∞∞13∞C∞7043∞∞∞D∞∞405∞∞2E∞∞3502∞2F∞1∞∞201∞G63∞∞∞104H∞∞∞22∞40例求以下圖中A點到其他點的最短路..Floyd算法〔求恣意兩點的最短途徑〕設A=(aij)n×n為賦權圖G=(V,E,F)的權矩陣,dij表示從vi到vj點的間隔,rij表示從vi到vj點的最短路中前一個點的編號.①賦初值.對一切i,j,dij=aij,rij=j.k=1.轉向②.②更新dij,rij.對一切i,j,假設dik+dkj＜dij,那么令dij=dik+dkj,rij=k,轉向③;③終止判別.假設k=n終止;否那么令k=k+1,轉向②.最短道路可由rij得到..0123456700281∞∞∞∞1206∞1∞∞∞28607512∞31∞70∞∞9∞4∞15∞03∞85∞∞1∞30466∞∞29∞4037∞∞∞∞8630例求以下圖中恣意兩點間的最短路..以下僅從圖上進展直觀操作.根據(jù)假設dik+dkj＜dij,那么令dij=dik+dkj.將原來的賦權值改動為|v2v4|=4,|v5v6|=3.再依次改動為|v1v2|=5,|v0v2|=7.接下來根據(jù)假設dij>dik+dkj,那么刪除vi到vj的連線.得到.從上圖中容易得到恣意兩點間的最短路.例如,v1到v6的路有三條：v1v0v3v2v6(長度為12),v1v4v5v2v6(長度為7),v1v4v7v6(長度為12)..例設備更新問題某企業(yè)每年年初,都要作出決議,假設繼續(xù)運用舊設備,要付維修費；假設購買一臺新設備,要付購買費.試制定一個5年更新方案,使總支出最少.知設備在每年年初的購買費分別為11,11,12,12,13.運用不同時間設備所需的維修費分別為5,6,8,11,18.解設bi表示設備在第i年年初的購買費,ci表示設備運用i年后的維修費,

V={v1,v2,…,v6},點vi表示第i年年初購進一臺新設備,虛設一個點v6表示第5年年底.

E={vivj|1≤i＜j≤6}..這樣上述設備更新問題就變?yōu)椋涸谟邢蛸x權圖G=(V,E,F)(圖解如下)中求v1到v6的最短路問題..由實踐問題可知,設備運用三年后該當更新,因此刪除該圖中v1到v5,v1到v6,v2到v6的連線；又設備運用一年后就更新那么不劃算,因此再刪除該圖中v1v2,v2v3,v3v4,v4v5,v5v6五條連線后得到從上圖中容易得到v1到v6只需兩條路：v1v3v6和v1v4v6.而這兩條路都是v1到v6的最短路..3、最小生成樹由樹的定義不難知道,恣意一個連通的(n,m)圖G適當去掉m-n+1條邊后,都可以變成樹,這棵樹稱為圖G的生成樹.設T是圖G的一棵生成樹,用F(T)表示樹T中一切邊的權數(shù)之和,F(T)稱為樹T的權.一個連通圖G的生成樹普通不止一棵,圖G的一切生成樹中權數(shù)最小的生成樹稱為圖G的最小生成樹.

求最小生成樹問題有很廣泛的實踐運用.例如,把n個鄉(xiāng)鎮(zhèn)用高壓電纜銜接起來建立一個電網(wǎng),使所用的電纜長度之和最短,即費用最小,就是一個求最小生成樹問題..Kruskal算法：從未選入樹中的邊中選取權重最小的且不構成回路的邊參與到樹中.〔判別回路比較費事〕Prim算法：把結點分成兩個集合，已參與樹中的(P)和未參與樹中的(Q)，然后每次選擇一個點在P中一個點在Q中的權重最小的邊，參與樹中，并把相應點參與P中。其最小生成樹如下：類似地,可定義連通圖G的最大生成樹..例選址問題現(xiàn)預備在n個居民點v1,v2,…,vn中設置一銀行.問設在哪個點,可使最大效力間隔最小?假設設置兩個銀行,問設在哪兩個點?模型假設假設各個居民點都有條件設置銀行,并有路相連,且路長知.模型建立與求解用Floyd算法求出恣意兩個居民點vi,vj之間的最短間隔,并用dij表示.⑴設置一個銀行,銀行設在vi點的最大效力間隔為.求k,使即假設設置一個銀行,那么銀行設在vk點,可使最大效力間隔最小.⑵設置兩個銀行,假設銀行設在vs,vt點使最大效力間隔最小.記那么s,t滿足：進一步,假設設置多個銀行呢？.4、遍歷性問題一、歐拉圖G=(V,E)為一連通無向圖經(jīng)過G中每條邊至少一次的回路稱為巡回；經(jīng)過G中每條邊正好一次的巡回稱為歐拉巡回；存在歐拉巡回的圖稱為歐拉圖。二、中國郵遞員問題〔CPP－chinesepostmanproblem〕一名郵遞員擔任投遞某個街區(qū)的郵件。如何為他〔她〕設計一條最短的投遞道路〔從郵局出發(fā)，經(jīng)過投遞區(qū)內每條街道至少一次，最后前往郵局〕？這一問題是我國管梅谷教授1962年首先提出，國際上稱之為中國郵遞員問題。.解法：假設本身就是歐拉圖，那么直接可以找到一條歐拉巡回就是本問題的解。假設不是歐拉圖，必定有偶數(shù)個奇度數(shù)結點，在這些奇度數(shù)點之間添加一些邊，使之變成歐拉圖，再找出一個歐拉巡回。詳細解法：Fleury算法+Edmonds最小對集算法.三、哈密爾頓圖G=(V,E)為一連通無向圖經(jīng)過G中每點一次且正好一次的途徑稱為哈密爾頓途徑；經(jīng)過G中每點一次且正好一次的回路稱為哈密爾頓回路；存在哈密爾頓回路的圖稱為哈密爾頓圖。四、游覽商問題〔TSP－travelingsalesmanproblem〕一名推銷員預備前往假設干城市推銷產(chǎn)品。如何為他〔她〕設計一條最短的游覽道路？即：從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后前往駐地〔最小哈密爾頓回路〕對于n個節(jié)點的游覽商問題，n個節(jié)點的恣意一個全陳列都是問題的一個能夠解〔假設恣意兩個點之間都有邊〕。G個節(jié)點的全陳列有(n-1)!個，因此間題歸結為在(n-1)!個回路中選取最小回路。TSP問題的解法屬于NP完全問題，普通只研討其近似解法.最臨近算法(1)選取恣意一個點作為起始點,找出與該點相關聯(lián)的權重最小的邊,構成一條初始途徑.

(2)找出與最新參與到途徑中的點相關聯(lián)的權重最小的邊參與到途徑中,且要求不再途徑中產(chǎn)生回路.

(3)反復(2)直到一切的結點都參與到途徑中.

(4)將起點和最后參與的結點之間的邊參與到途徑中,構成Hamilton回路.其他數(shù)值算法：

人工神經(jīng)元方法，

遺傳算法等等.5、二分圖與匹配定義1設X,Y都是非空有限集,且X∩Y=,

E{xy|x∈X,y∈Y},稱G=(X,Y,E)為二部圖.二部圖可以為是有限簡單無向圖.假設X中的每個點都與Y中的每個點鄰接,那么稱G=(X,Y,E)為完備二部圖.假設F：E→R+,那么稱G=(X,Y,E,F)為二部賦權圖.二部賦權圖的權矩陣普通記作A=(aij)|X|×|Y|,其中aij=F(xiyj)..定義2設G=(X,Y,E)為二部圖,且ME.假設M中恣意兩條邊在G中均不鄰接,那么稱M是二部圖G的一個匹配.定義3設M是二部圖G的一個匹配,假設G的每一個點都是M中邊的頂點,那么稱M是二部圖G的完美匹配；假設G中沒有另外的匹配M0,使|M0|＞|M|,那么稱M是二部圖G的最大匹配.在二部賦權圖G=(X,Y,E,F)中,權數(shù)最大的最大匹配M稱為二部賦權圖G的最正確匹配.顯然,每個完美匹配都是最大匹配,反之不一定成立..任務安排問題之一給n個任務人員x1,x2,…,xn安排n項任務y1,y2,…,yn.n個任務人員中每個人能勝任一項或幾項任務,但并不是一切任務人員都能從事任何一項任務.比如x1能做y1,y2任務,x2能做y2,y3,y4任務等.這樣便提出一個問題,對一切的任務人員能不能都分配一件他所能勝任的任務？我們構造一個二部圖G=(X,Y,E),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且當且僅當任務人員xi勝任任務yj時,xi與yj才相鄰.于是,問題轉化為求二部圖的一個完美匹配.由于|X|=|Y|,所以完美匹配即為最大匹配..求二部圖G=(X,Y,E)的最大匹配算法(匈牙利算法,交替鏈算法)迭代步驟:從G的恣意匹配M開場.①將X中M的一切非飽和點都給以標號0和標志*,轉向②.M的非飽和點即非M的某條邊的頂點.②假設X中一切有標號的點都已去掉了標志*,那么M是G的最大匹配.否那么任取X中一個既有標號又有標志*的點xi,去掉xi的標志*,轉向③.③找出在G中一切與xi鄰接的點yj,假設一切這樣的yj都已有標號,那么轉向②,否那么轉向④..④對與xi鄰接且尚未給標號的yj都給定標號i.假設一切的yj都是M的飽和點,那么轉向⑤,否那么逆向前往.即由其中M的任一個非飽和點yj的標號i找到xi,再由xi的標號k找到y(tǒng)k,…,最后由yt的標號s找到標號為0的xs時終了,獲得M-增廣路xsyt…xiyj,記P={xsyt,…,xiyj},重新記M為M⊕P,轉向①.不用理睬M-增廣路的定義.M⊕P=M∪P\M∩P,是對稱差.⑤將yj在M中與之鄰接的點xk,給以標號j和標志*,轉向②..例求以下圖所示二部圖G的最大匹配.解①取初始匹配M0={x2y2,x3y3,x5y5}(上圖粗線所示).②給X中M0的兩個非飽和點x1,x4都給以標號0和標志*(如以下圖所示).③去掉x1的標志*,將與x1鄰接的兩個點y2,y3都給以標號1.由于y2,y3都是M0的兩個飽和點,所以將它們在M0中鄰接的兩個點x2,x3都給以相應的標號和標志*(如以下圖所示)..④去掉x2的標志*,將與x2鄰接且尚未給標號的三個點y1,y4,y5都給以標號2(如以下圖所示).⑤由于y1是M0的非飽和點,所以順著標號逆向前往依次得到x2,y2,直到x1為0為止.于是得到M0的增廣路x1y2x2y1,記P={x1y2,y2x2,x2y1}.取M1=M0⊕P={x1y2,x2y1,x3y3,x5y5},那么M1是比M多一邊的匹配(如以下圖所示)..⑥再給X中M1的非飽和點x4給以標號0和標志*,然后去掉x4的標志*,將與x4鄰接的兩個點y2,y3都給以標號4.由于y2,y3都是M1的兩個飽和點,所以將它們在M1中鄰接的兩個點x1,x3都給以相應的標號和標志*(如以下圖所示).⑦去掉x1的標志*,由于與x1鄰接的兩個點y2,y3都有標號4,所以去掉x3的標志*.而與x3鄰接的兩個點y2,y3也都有標號4,此時X中一切有標號的點都已去掉了標志*(如以下圖所示),因此M1是G的最大匹配.G不存在飽和X的每個點的匹配,當然也不存在完美匹配..任務安排問題之二給n個任務人員x1,x2,…,xn安排n項任務y1,y2,…,yn.假設每個任務人員任務效率不同,要求任務分配的同時思索總效率最高.我們構造一個二部賦權圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xiyj)為任務人員xi勝任任務yj時的任務效率.那么問題轉化為：求二部賦權圖G的最正確匹配.在求G的最正確匹配時,總可以假設G為完備二部賦權圖.假設xi與yj不相鄰,可令F(xiyj)=0.同樣地,還可虛設點x或y,使|X|=|Y|.如此就將G轉化為完備二部賦權圖,而且不會影響結果..定義設G=(X,Y,E,F)為完備的二部賦權圖,

假設L：X∪Y→R+滿足：x∈X,y∈Y,L(x)+L(y)≥F(xy),那么稱L為G的一個可行點標志,

記相應的生成子圖為GL=(X,Y,EL,F),這里EL={xy∈E|L(x)+L(y)=F(xy)}.

求完備二部賦權圖G=(X,Y,E,F)的最正確匹配算法迭代步驟：設G=(X,Y,E,F)為完備的二部賦權圖,L是其一個初始可行點標志,通常取L(x)=max{F(xy)|y∈Y},x∈X,L(y)=0,y∈Y..M是GL的一個匹配.①假設X的每個點都是飽和的,那么M是最正確匹配.否那么取M的非飽和點u∈X,令S={u},T=,轉向②.②記NL(S)={v|u∈S,uv∈GL}.

假設NL(S)=T,那么GL沒有完美匹配,轉向③.否那么轉向④.③調整標志,計算aL=min{L(x)+L(y)-F(xy)|x∈S,y∈Y\T}.由此得新的可行點標志令L=H,GL=GH,重新給出GL的一個匹配M,轉向①.④取y∈NL(S)\T,假設y是M的飽和點,轉向⑤.否那么,轉向⑥.⑤設xy∈M,那么令S=S∪{x},T=T∪{y},轉向②.⑥在GL中的u-y路是M-增廣路,設為P,并令M=M⊕P,轉向①..6、網(wǎng)絡流問題定義1設G=(V,E)為有向圖,在V中指定一點稱為發(fā)點(記為vs),和另一點稱為收點(記為vt),其他點叫做中間點.對每一條邊vivj∈E,對應一個非負實數(shù)Cij,稱為它的容量.這樣的G稱為容量網(wǎng)絡,簡稱網(wǎng)絡,記作G=(V,E,C).定義2網(wǎng)絡G=(V,E,C)中任一條邊vivj有流量fij,稱集合f={fij}為網(wǎng)絡G上的一個流.滿足下述條件的流f稱為可行流：①(限制條件)對每一邊vivj,有0≤fij≤Cij;②(平衡條件)對于中間點vk有∑fik=∑fkj,即中間點vk的輸入量=輸出量..假設f是可行流,那么對收、發(fā)點vt、vs有∑fsi=∑fjt=Wf,即從vs點發(fā)出的物質總量=vt點輸入的量.Wf稱為網(wǎng)絡流f的總流量.上述概念可以這樣來了解,如G是一個運輸網(wǎng)絡,那么發(fā)點vs表示發(fā)送站,收點vt表示接納站,中間點vk表示中間轉運站,可行流fij表示某條運輸線上經(jīng)過的運輸量,容量Cij表示某條運輸線能承當?shù)淖畲筮\輸量,Wf表示運輸總量.可行流總是存在的.比如一切邊的流量fij=0就是一個可行流(稱為零流)..所謂最大流問題就是在容量網(wǎng)絡中,尋覓流量最大的可行流.實踐問題中,一個網(wǎng)絡會出現(xiàn)下面兩種情況：⑴發(fā)點和收點都不止一個.處理的方法是再虛設一個發(fā)點vs和一個收點vt,發(fā)點vs到一切原發(fā)點邊的容量都設為無窮大,一切原收點到收點vt邊的容量都設為無窮大.⑵網(wǎng)絡中除了邊有容量外,點也有容量.處理的方法是將一切有容量的點分成兩個點,如點v有容量Cv,將點v分成兩個點v'和v",令C(v'v")=Cv..最小費用流問題這里我們要進一步討論不僅要使網(wǎng)上的流到達最大,或者到達要求的預定值,而且還要使運輸流的費用是最小的,這就是最小費用流問題.最小費用流問題的普通提法：知網(wǎng)絡G=(V,E,C),每條邊vivj∈E除了已給容量Cij外,還給出了單位流量的費用bij(≥0).所謂最小費用流問題就是求一個總流量知的可行流f={fij}使得總費用最小..特別地,當要求f為最大流時,即為最小費用最大流問題.設網(wǎng)絡G=(V,E,C),取初始可行流f為零流,求解最小費用流問題的迭代步驟：①構造有向賦權圖Gf=(V,Ef,F),對于恣意的vivj∈E,Ef,F的定義如下：當fij=0時,vivj∈Ef,F(vivj)=bij;當fij=Cij時,vjvi∈Ef,F(vjvi)=-bij;當0＜fij＜Cij時,vivj∈Ef,F(vivj)=bij,vjvi∈Ef,F(vjvi)=-bij.然后轉向②..②求出含有負權的有向賦權圖Gf=(V,Ef,F)中發(fā)點vs到收點vt的最短路,假設最短路存在轉向③;否那么f是所求的最小費用最大流,停頓.③增流.vivj與一樣,vivj與相反.令=min{ij|vivj∈},重新定義流f={fij}為其它情況不變.假設Wf大于或等于預定的流量值,那么適當減少值,使Wf等于預定的流量值,那么f是所求的最小費用流,停頓;否那么轉向①..下面引見求解有向賦權圖G=(V,E,F)中含有負權的最短路的Ford算法.設邊的權vivj為wij,v1到vi的路長記為(i).Ford算法的迭代步驟：①賦初值(1)=0,(i)=∞,i=2,3,…,n.②更新(i),i=2,3,…,n.(i)=min{(i),min{(j)+wji|j≠i}}.③假設一切的(i)都無變化,停頓;否那么轉向②.在算法的每一步,(i)都是從v1到vi的最短路長度的上界.假設不存在負長回路,那么從v1到vi的最短路長度是(i)的下界,經(jīng)過n-1次迭代后(i)將堅持不變.假設在第n次迭代后(i)仍在變化時,闡明存在負長回路..7、關鍵途徑問題〔拓撲排序〕一項工程義務,大到建造一座大壩,一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束,只需在某些工序完成之后,一個工序才干開場.即它們之間存在完成的先后次序關系,普通以為這些關系是預知的,而且也可以估計完成每個工序所需求的時間.這時工程指點人員迫切希望了解最少需求多少時間才可以完成整個工程工程,影響工程進度的關鍵工序是哪幾個？.PT(Potentialtaskgraph)圖在PT(Potentialtaskgraph)圖中,用結點表示工序,假設工序i完成之后工序j才干啟動,那么圖中有一條有向邊(i,j),其長度wi表示工序i所需的時間.這種圖必定不存在有向回路,否那么某些工序將在本身完成之后才干開場,這顯然不符合實踐情況.在PT圖中添加兩個虛擬結點v0和vn,使一切僅為始點的結點都直接與v0結合,v0為新增邊的始點,這些新增邊的權都設為0;使一切僅為終點的結點都直接與vn結合,vn為新增邊的終點.這樣得到的圖G依然不存在有向回路..例一項工程由13道工序組成,所需時間(單位：天)及先行工序如下表所示(P172).工序序號ABCDEFGHI所需時間263243842先行工序—AABC,DDDDG,H工序序號JKLM所需時間3856先行工序GH,EJK試問這項工程至少需求多少天才干完成?那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?.先作出該工程的PT圖.由于除了工序A外，均有先行工序,因此不用虛設虛擬結點v0.AB22C6D3E2F2G2H2K4N3I8J8442L3M856在PT圖中,容易看出各工序先后完成的順序及時間.虛擬結點.AB22C6D3E2F2G2H2K4N3I8J8442L3M856這項工程至少需求多少天才干完成?就是要求A到N的最長路,此途徑稱為關鍵途徑.那些工程不能延誤?那些工程可以延誤?最多可延誤多少天?關鍵途徑上的那些工程不能延誤..關鍵途徑(最長途徑)算法定理假設有向圖G中不存在有向回路,那么可以將G的結點重新編號為u1,u2,…,un,使得對恣意的邊uiuj∈E(G),都有i＜j.各工序最早啟動時間算法步驟：①根據(jù)定理對結點重新編號為u1,u2,…,un.②賦初值(u1)=0.③依次更新(uj),j=2,3,…,n.(uj)=max{(ui)+(ui,uj)|uiuj∈E(G)}.④終了.其中(uj)表示工序uj最早啟動時間,而(un)即(vn)是整個工程完工所需的最短時間..AB22C6D3E2F2G2H2K4N3I8J8442L3M856此例不用重新編號，只需按字母順序即可.(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.關鍵途徑?.經(jīng)過以上計算闡明：這項工程至少需求28天才干完成.關鍵途徑(最長途徑):A→B→D→E→K→M→NA→B→D→H→K→M→N工序A,B,D,E,H,K,M不能延誤,否那么將影響工程的完成.但是對于不在關鍵途徑上的工序,能否允許延誤？假設允許,最多可以延誤多長時間呢？各工序允許延誤時間t(uj)等于各工序最晚啟動時間(uj)減去各工序最早啟動時間(uj).即t(uj)=(uj)-(uj)..最晚啟動時間算法步驟(知結點重新編號)：①賦初值(un)=(un).②更新(uj),j=n-1,n-2,…,1.(uj)=min{(ui)-(ui,uj)|uiuj∈E(G)}.③終了.順便提一句,根據(jù)工序uj允許延誤時間t(uj)能否為0,可判別該工序能否在關鍵途徑上..AB22C6D3E2F2G2H2K4N3I8J8442L3M856(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..各工序允許延誤時間如下：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圖在PERT(Programmeevaluationandreviewtechnique)圖中,采用有向邊表示工序,其權值表示該工序所需時間.假設工序ei完成后ej才干開場,那么令vk是ei的終點,ej的始點.根據(jù)這種商定,前例的PERT圖如下：ABCEFDDGGHHIJKLM對于PERT圖,一些算法與PT圖類似..PT圖要比PERT圖好一些.PT圖的結點數(shù)根本上是固定的,這是最重要的一點,容易編程計算.另外PT圖比PERT圖更加靈敏,它能順應一些額外的約束.例如以下圖中(i)/2vivj⑴(i)+tvivj⑵bjv0vj⑶⑴表示工序vi完成一半之后vj就可以開場.⑵表示工序vi完成后經(jīng)過t時辰vj才開場.⑶表示在時間bj之后工序vj才干開場,其中v0表示虛擬結點..8、系統(tǒng)監(jiān)控模型定義1設圖G=(V,E),KV假設圖G的每條邊都至少有一個頂點在K中,那么稱K是G的一個點覆蓋.假設G的一個點覆蓋中恣意去掉一個點后不再是點覆蓋,那么稱此點覆蓋是G的一個極小點覆蓋.頂點數(shù)最少的點覆蓋,稱為G的最小點覆蓋.例如,右圖中,{v0,v2,v3,v5,v6}等都是極小點覆蓋.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小點覆蓋..系統(tǒng)監(jiān)控問題之一假設v1,v2,…,v7是7個哨所,監(jiān)視著11條路段(如以下圖所示),為節(jié)省人力,問至少需求在幾個哨所派人站崗,就可以監(jiān)視全部路段?這就是要求最小點覆蓋問題.v2v1v3v7v6v5v4{v1,v3,v5,v6}和{v1,v3,v5,v7}都是最小點覆蓋,所以致少需求在4個哨所派人站崗來監(jiān)視全部路段.到目前為止,還沒有找到求最小點覆蓋的有效算法,即多項式時間算法(算法步數(shù)不超越nc,n為G的頂點數(shù),c為常數(shù)).有一些啟發(fā)式近似算法..最大獨立點集定義2設圖G=(V,E),IV假設I中恣意兩個頂點在G中都不相鄰,那么稱I是G的一個獨立點集.假設G的一個獨立點集中,恣意添加一個點后不再是獨立點集,那么稱此獨立點集是G的一個極大獨立點集.頂點數(shù)最多的獨立點集,稱為G的最大獨立點集.例如,右圖中,{v1,v4}等都是極大獨立點集.{v1,v3,v5},{v2,v2,v6}是最大獨立點集..最小控制集定義3設圖G=(V,E),DV假設v∈V,要么v∈D,要么v與D的某個點相鄰,那么稱D是G的一個控制集.假設G的一個控制集中恣意去掉一個點后不再是控制集,那么稱此控制集是G的一個極小控制集.頂點數(shù)最少的控制集,稱為G的最小控制集.例如,右圖中,{v1,v3,v5}是極小控制集,{v0}是最小控制集..系統(tǒng)監(jiān)控問題之二假設以下圖代表一指揮系統(tǒng),頂點v1,v2,…,v7表示被指揮的單位,邊表示可以直接下達命令的通訊線路.欲在某些單位建立指揮站,以便可以經(jīng)過指揮站直接給各單位下達命令,問至少需求建立幾個指揮站?這就是要求最小控制集問題.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以致少需求在2個單位建立指揮站.到目前為止,還沒有找到求最小控制集的有效算法...最小點覆蓋、最大獨立點集和最小控制集的關系定理1設無向圖G=(V,E)中無孤立點(不與任何邊關聯(lián)