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

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

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

假設(shè)t是T中關(guān)于P由最小目的的結(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的目的為l(t),令x為最小目的所在的點(diǎn),即:l(x)=min(l(t))(tT),

(3)令P'=P{x},T'=T-{x},l'(t)表示T'中結(jié)點(diǎn)t關(guān)于P'的目的,那么

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

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

否那么,令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'的目的.4、P'替代P,T'替代T,反復(fù)步驟2,3〔其中：w(x,y)為圖的權(quán)矩陣〕.改良Dijkstra算法〔求a點(diǎn)到其他點(diǎn)的最短途徑〕1、初始化，P={a}，T=V-{a}，對(duì)每個(gè)結(jié)點(diǎn)t計(jì)算目的l(t)=w(a,t),pro(t)=a;2、設(shè)x為T中關(guān)于P有最小目的的點(diǎn),

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

否那么,令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’的目的.

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

V={v1,v2,…,v6},點(diǎn)vi表示第i年年初購進(jìn)一臺(tái)新設(shè)備,虛設(shè)一個(gè)點(diǎn)v6表示第5年年底.

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

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

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

(3)反復(fù)(2)直到一切的結(jié)點(diǎn)都參與到途徑中.

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

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

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

E{xy|x∈X,y∈Y},稱G=(X,Y,E)為二部圖.二部圖可以為是有限簡單無向圖.假設(shè)X中的每個(gè)點(diǎn)都與Y中的每個(gè)點(diǎn)鄰接,那么稱G=(X,Y,E)為完備二部圖.假設(shè)F：E→R+,那么稱G=(X,Y,E,F)為二部賦權(quán)圖.二部賦權(quán)圖的權(quán)矩陣普通記作A=(aij)|X|×|Y|,其中aij=F(xiyj)..定義2設(shè)G=(X,Y,E)為二部圖,且ME.假設(shè)M中恣意兩條邊在G中均不鄰接,那么稱M是二部圖G的一個(gè)匹配.定義3設(shè)M是二部圖G的一個(gè)匹配,假設(shè)G的每一個(gè)點(diǎn)都是M中邊的頂點(diǎn),那么稱M是二部圖G的完美匹配；假設(shè)G中沒有另外的匹配M0,使|M0|＞|M|,那么稱M是二部圖G的最大匹配.在二部賦權(quán)圖G=(X,Y,E,F)中,權(quán)數(shù)最大的最大匹配M稱為二部賦權(quán)圖G的最正確匹配.顯然,每個(gè)完美匹配都是最大匹配,反之不一定成立..任務(wù)安排問題之一給n個(gè)任務(wù)人員x1,x2,…,xn安排n項(xiàng)任務(wù)y1,y2,…,yn.n個(gè)任務(wù)人員中每個(gè)人能勝任一項(xiàng)或幾項(xiàng)任務(wù),但并不是一切任務(wù)人員都能從事任何一項(xiàng)任務(wù).比如x1能做y1,y2任務(wù),x2能做y2,y3,y4任務(wù)等.這樣便提出一個(gè)問題,對(duì)一切的任務(wù)人員能不能都分配一件他所能勝任的任務(wù)？我們構(gòu)造一個(gè)二部圖G=(X,Y,E),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},并且當(dāng)且僅當(dāng)任務(wù)人員xi勝任任務(wù)yj時(shí),xi與yj才相鄰.于是,問題轉(zhuǎn)化為求二部圖的一個(gè)完美匹配.由于|X|=|Y|,所以完美匹配即為最大匹配..求二部圖G=(X,Y,E)的最大匹配算法(匈牙利算法,交替鏈算法)迭代步驟:從G的恣意匹配M開場(chǎng).①將X中M的一切非飽和點(diǎn)都給以標(biāo)號(hào)0和標(biāo)志*,轉(zhuǎn)向②.M的非飽和點(diǎn)即非M的某條邊的頂點(diǎn).②假設(shè)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,假設(shè)一切這樣的yj都已有標(biāo)號(hào),那么轉(zhuǎn)向②,否那么轉(zhuǎn)向④..④對(duì)與xi鄰接且尚未給標(biāo)號(hào)的yj都給定標(biāo)號(hào)i.假設(shè)一切的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í)終了,獲得M-增廣路xsyt…xiyj,記P={xsyt,…,xiyj},重新記M為M⊕P,轉(zhuǎn)向①.不用理睬M-增廣路的定義.M⊕P=M∪P\M∩P,是對(duì)稱差.⑤將yj在M中與之鄰接的點(diǎn)xk,給以標(biāo)號(hào)j和標(biāo)志*,轉(zhuǎn)向②..例求以下圖所示二部圖G的最大匹配.解①取初始匹配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.由于y2,y3都是M0的兩個(gè)飽和點(diǎn),所以將它們?cè)贛0中鄰接的兩個(gè)點(diǎn)x2,x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)志*(如以下圖所示)..④去掉x2的標(biāo)志*,將與x2鄰接且尚未給標(biāo)號(hào)的三個(gè)點(diǎn)y1,y4,y5都給以標(biāo)號(hào)2(如以下圖所示).⑤由于y1是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多一邊的匹配(如以下圖所示)..⑥再給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.由于y2,y3都是M1的兩個(gè)飽和點(diǎn),所以將它們?cè)贛1中鄰接的兩個(gè)點(diǎn)x1,x3都給以相應(yīng)的標(biāo)號(hào)和標(biāo)志*(如以下圖所示).⑦去掉x1的標(biāo)志*,由于與x1鄰接的兩個(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個(gè)任務(wù)人員x1,x2,…,xn安排n項(xiàng)任務(wù)y1,y2,…,yn.假設(shè)每個(gè)任務(wù)人員任務(wù)效率不同,要求任務(wù)分配的同時(shí)思索總效率最高.我們構(gòu)造一個(gè)二部賦權(quán)圖G=(X,Y,E,F),這里X={x1,x2,…,xn},Y={y1,y2,…,yn},F(xiyj)為任務(wù)人員xi勝任任務(wù)yj時(shí)的任務(wù)效率.那么問題轉(zhuǎn)化為：求二部賦權(quán)圖G的最正確匹配.在求G的最正確匹配時(shí),總可以假設(shè)G為完備二部賦權(quán)圖.假設(shè)xi與yj不相鄰,可令F(xiyj)=0.同樣地,還可虛設(shè)點(diǎn)x或y,使|X|=|Y|.如此就將G轉(zhuǎn)化為完備二部賦權(quán)圖,而且不會(huì)影響結(jié)果..定義設(shè)G=(X,Y,E,F)為完備的二部賦權(quán)圖,

假設(shè)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..M是GL的一個(gè)匹配.①假設(shè)X的每個(gè)點(diǎn)都是飽和的,那么M是最正確匹配.否那么取M的非飽和點(diǎn)u∈X,令S={u},T=,轉(zhuǎn)向②.②記NL(S)={v|u∈S,uv∈GL}.

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