圖與網(wǎng)絡(luò)模型及方法

圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法PPT1圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法PPT1圖與子圖圖的連通與割集樹與支撐樹最小樹最短有向路最大流最小費(fèi)用流最大對集圖與網(wǎng)絡(luò)模型及方法圖與子圖圖與網(wǎng)絡(luò)模型及方法2圖與網(wǎng)絡(luò)

無向圖的基本概念網(wǎng)絡(luò)的基本概念關(guān)聯(lián)矩陣和鄰接矩陣

關(guān)聯(lián)矩陣鄰接矩陣主要結(jié)論子圖圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)圖與網(wǎng)絡(luò)模型及方法3緒論圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。1847年，克?；舴驗榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了“樹”的概念。1857年，凱萊在計數(shù)烷n2n+2CH的同分異構(gòu)物時，也發(fā)現(xiàn)了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術(shù)語，就是如何找出一個連通圖中的生成圈圖與網(wǎng)絡(luò)模型及方法緒論圖論起源于18世紀(jì)。圖與網(wǎng)絡(luò)模型及方法4緒論近幾十年來，由于計算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用，圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、運(yùn)籌學(xué)，生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會學(xué)等學(xué)科中。圖與網(wǎng)絡(luò)模型及方法緒論近幾十年來，由于計算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了5緒論圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。圖與網(wǎng)絡(luò)模型及方法緒論圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。6哥尼斯堡七橋問題這個圖是連通的，且每個點(diǎn)都與偶數(shù)線相關(guān)聯(lián)圖與網(wǎng)絡(luò)模型及方法哥尼斯堡七橋問題這個圖是連通的，且每個點(diǎn)都與偶數(shù)線相關(guān)聯(lián)圖與7緒論圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（OperationsResearch）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域的最短路問題、最大流問題、最小費(fèi)用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。圖與網(wǎng)絡(luò)模型及方法緒論圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（OperationsResearch8圖------由若干個點(diǎn)和連接這些點(diǎn)的連線所組成的圖形vi——圖中的點(diǎn)，稱為頂點(diǎn)（代表具體事物，研究對象。ei——圖中的連線，稱為邊（對象之間的聯(lián)系）m(G)=|E|——G的邊數(shù)，簡記為mn(G)=|V|——G的頂點(diǎn)數(shù)，簡記為n一.圖的概念記V={vi}——點(diǎn)的集合，E={ei}——邊的集合G={V，E}G——一個圖m=6,n=5圖的基本概念圖與網(wǎng)絡(luò)模型及方法圖------由若干個點(diǎn)和連接這些點(diǎn)的連線所組成的圖形vi—9有向圖無向圖——邊e=(vi,vj)有方向vi為始點(diǎn)，vj為終點(diǎn)——邊e=(vi,vj)無方向，此時(vi,vj)=(vj,vi)e4=(v3，v4）=(v4，v3）e4=(v3，v4)≠(v4，v3）e5=(v3，v4）=(v4，v3）此時(vi,vj)≠(vj,vi)e5=(v4，v3)≠(v3，v4)圖有向圖無向圖圖與網(wǎng)絡(luò)模型及方法有向圖無向圖——邊e=(vi,vj)有方向vi為始點(diǎn)，vj10二.常用名詞：1、端點(diǎn)和關(guān)聯(lián)邊：2、相鄰點(diǎn)和相鄰邊：3、多重邊與環(huán)：4、多重圖和簡單圖：無環(huán)也無多重邊的圖稱為簡單圖。含有多重邊的圖稱為多重圖；圖與網(wǎng)絡(luò)模型及方法二.常用名詞：1、端點(diǎn)和關(guān)聯(lián)邊：2、相鄰點(diǎn)和相鄰邊：3、多重115、次：6、懸掛點(diǎn)和懸掛邊：次為1的點(diǎn)稱為懸掛點(diǎn)，與懸掛點(diǎn)相聯(lián)的邊稱為懸掛邊。7、孤立點(diǎn)：8、奇點(diǎn)與偶點(diǎn)：，G的邊數(shù)m=6圖與網(wǎng)絡(luò)模型及方法5、次：6、懸掛點(diǎn)和懸掛邊：7、孤立點(diǎn)：8、奇點(diǎn)與偶點(diǎn)：，G12性質(zhì)1：在圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)m的兩倍。證明：由于每條邊均與兩個頂點(diǎn)關(guān)聯(lián)，因此在計算頂點(diǎn)的次時每條邊都計算了兩遍，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的二倍。三.次（度）的性質(zhì)性質(zhì)2：在任何圖G=(V,E)中，奇點(diǎn)的個數(shù)為偶數(shù)證明：設(shè)V1，V2分別是圖G中奇點(diǎn)和偶點(diǎn)的集合，則V1∪V2=V,

V1∩V2=Φ,有性質(zhì)1，，因為V2是偶點(diǎn)的集合，d(vi)(i∈V2)均為偶數(shù)，所以只有偶數(shù)個奇數(shù)相加才能得到偶數(shù)，所以V1中的點(diǎn)，即奇點(diǎn)的個數(shù)為偶數(shù)。圖與網(wǎng)絡(luò)模型及方法性質(zhì)1：在圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)m的兩倍。13四.鏈、路、連通圖1.鏈：對于無向圖G=(V，E)，若圖G中有一個點(diǎn)與邊的交替序列 μ={vi0,ei1,vi1,ei2,

,vik-1,eik,vik}，且eit=(vit-1,vit)(t=1,2,…,k), 則稱該交替序列

μ為連結(jié)vi0和vik的一條鏈。簡單鏈：μ中只有重復(fù)的點(diǎn)而無重復(fù)邊者為簡單鏈。初等鏈：μ中沒有重復(fù)的點(diǎn)和重復(fù)邊者為初等鏈。圈：無向圖G中，連結(jié)vi0與vik的一條鏈，當(dāng)vi0與vik是同一個點(diǎn)時，稱此鏈為圈。圈中只有重復(fù)點(diǎn)而無重復(fù)邊者為簡單圈，既（除起點(diǎn)、終點(diǎn)重復(fù)外）無重復(fù)點(diǎn)也無重復(fù)邊者為初等圈不是鏈初等鏈簡單鏈圖與網(wǎng)絡(luò)模型及方法四.鏈、路、連通圖1.鏈：對于無向圖G=(V，E)，若圖G14（簡單圈）（初等圈）2路：在有向圖D=(V，A)中，若有從vi0到vik不考慮方向的鏈，且各邊方向一致，則稱之為從vi0到vik的一條路。

對于有向圖可以類似于無向圖定義鏈和圈，初等鏈、圈，簡單鏈、圈．此時不考慮邊的方向。而當(dāng)鏈(圈)上的邊方向相同時，稱為道路(回路)。對于無向圖來說，道路與鏈、回路與圈意義相同圖與網(wǎng)絡(luò)模型及方法（簡單圈）（初等圈）2路：在有向圖D=(V，A)中，若有從153連通圖：一個圖中任意兩點(diǎn)間至少有一條鏈(或路)相連的圖。連通圖非連通圖五．網(wǎng)絡(luò)在實際問題中，往往只用圖來描述所研究對象之間的關(guān)系還不夠，與圖聯(lián)系在—起的，通常還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，通常稱之為“權(quán)”，權(quán)可以代表如距離、費(fèi)用、通過能力(容量)等等。這種帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò)(賦權(quán)圖)。圖與網(wǎng)絡(luò)模型及方法3連通圖：一個圖中任意兩點(diǎn)間至少有一條鏈(或路)相連的圖。16如公路交通圖：vi表示城市,ei表示公路w(ei)表示公路ei的長度如w(e2)=50表示城市v2與城市v3之間的距離是50千米六.完全圖、偶圖1．完全圖：一個簡單圖，若任意兩個頂點(diǎn)之間均有一條邊相連，則稱這樣的圖為完全圖。對于完全圖，由于每個頂點(diǎn)與所有其余頂點(diǎn)都有一條邊相連，所以在有n個頂點(diǎn)的完全圖中，各個頂點(diǎn)的次均為（n-1）。圖與網(wǎng)絡(luò)模型及方法如公路交通圖：vi表示城市,ei表示公路w(ei)表示公路e172.偶圖：若圖G的頂點(diǎn)能分成兩個互不相交的非空集合V1和V2，使在同一集合中的任意兩個頂點(diǎn)均不相鄰，稱這樣的圖為偶圖，也稱為二部圖。若偶圖的頂點(diǎn)集合V1，V2之間的每一對不同頂點(diǎn)都有一條邊相連，稱這樣的圖為完全偶圖。v2v3v4v5v2v3v4v5??????????v1v1完全圖(完全)偶圖定理一個圖為偶圖的充分必要條件該圖無奇圈圖與網(wǎng)絡(luò)模型及方法2.偶圖：若圖G的頂點(diǎn)能分成兩個互不相交的非空集合V1和V218七.子圖、部分圖對于圖G1={V1,E1}和圖G2={V2,E2},若有，稱G1是G2的一個子圖。若有，稱G1是G2的一個部分圖（生成子圖）。*部分圖也是子圖，但子圖不一定是部分圖。生成子圖圖與網(wǎng)絡(luò)模型及方法七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生19七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生成子圖對于圖G1={V1,E1}和圖G2={V2,E2},若有，稱G1是G2的一個子圖。若有，稱G1是G2的一個部分圖（生成子圖）。圖與網(wǎng)絡(luò)模型及方法七.子圖、部分圖*部分圖也是子圖，但子圖不一定是部分圖。生20八.前向弧與后向弧設(shè)μ是一條從vs到vt的鏈，則鏈μ上與鏈的方向一致的弧稱為前向弧，記這些弧為μ+；鏈μ上與鏈的方向相反的弧稱為后向弧，記這些弧為μ-。???????vsv1v2v3v4v5vt前向弧與后向弧圖與網(wǎng)絡(luò)模型及方法八.前向弧與后向弧???????vsv1v2v3v4v5vt21子圖設(shè)G1=[V1,E1],G2=[V2,E2]子圖定義：如果V2

V1,E2

E1

稱G2

是G1

的子圖；真子圖：如果V2

V1,E2

E1

稱G2

是G1

的真子圖；部分圖：如果V2=V1,E2

E1

稱G2

是G1

的部分圖；導(dǎo)出子圖：如果V2

V1,E2={[vi,vj]∣vi,vj

V2}，稱G2

是G1

中由V2

導(dǎo)出的導(dǎo)出子圖。圖與網(wǎng)絡(luò)模型及方法子圖設(shè)G1=[V1,E1],G222九、圖的矩陣表示用矩陣表示圖對研究圖的性質(zhì)及應(yīng)用常常是比較方便的．定義：網(wǎng)絡(luò)(賦權(quán)圖)G＝(V，E)，其邊(vi,vj)有權(quán)ωij,構(gòu)造矩陣A=(aij)n×n,其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。例、寫出下圖的權(quán)矩陣v1v2v3v4?????v5765424938圖與網(wǎng)絡(luò)模型及方法九、圖的矩陣表示定義：網(wǎng)絡(luò)(賦權(quán)圖)G＝(V，E)，其邊(v23定義：對于圖G＝(V，E)，|V|=n,構(gòu)造一個矩陣A=(aij)n×n,其中：稱矩陣A為圖G的鄰接矩陣。例、寫出下圖的鄰接矩陣v1v3v5??????v2v4v6當(dāng)G為無向圖時，鄰接矩陣為對稱矩陣圖與網(wǎng)絡(luò)模型及方法定義：對于圖G＝(V，E)，|V|=n,構(gòu)造一個矩陣A=(a24最短軌道問題給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點(diǎn)間的邊，得圖G。對G的每一邊e，賦以一個實數(shù)w(e)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G中指定的兩個頂點(diǎn)u0,v0間的具最小權(quán)的軌。這條軌叫做u0

,v0間的最短路，它的權(quán)叫做u0

,v0間的距離，亦記作d(u0

,v0)圖與網(wǎng)絡(luò)模型及方法最短軌道問題給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的25最短軌道問題求法---Dijkstra算法基本思想是按距

u0從近到遠(yuǎn)為順序，依次求得u0到G的各頂點(diǎn)的最短路和距離，直至v0（或直至G的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計算信息，采用了標(biāo)號算法。圖與網(wǎng)絡(luò)模型及方法最短軌道問題求法---Dijkstra算法基本思想圖與網(wǎng)26最短軌道問題求法---Dijkstra算法圖與網(wǎng)絡(luò)模型及方法最短軌道問題求法---Dijkstra算法圖與網(wǎng)絡(luò)模型及27定義：連通且不含圈的無向圖稱為樹。記作T(V，E)二、樹樹可以有很多等價的定義,以下定理中的各命題都體現(xiàn)樹的特征.定理設(shè)G={V,E}是一無向圖，|V|=n，|E|=m。則以下命題是等價的.(1)G是樹;(2)G的每對頂點(diǎn)之間有唯一的一條路;(3)G連通且m=n-1;(4)G無圈且m=n-1;(5)G無圈,在G的任一對頂點(diǎn)上加一新邊后產(chǎn)生圈;(6)G連通，但刪去任何一邊后不再連通。圖與網(wǎng)絡(luò)模型及方法定義：連通且不含圈的無向圖稱為樹。記作T(V，E)二、樹樹28定理：無向圖G有生成樹當(dāng)且僅當(dāng)G連通。證明:必要性顯然,只證充分性。若G無圈，則G本身就是G的生成樹。若G有圈C，則在G中刪去C的一條邊，所得的圖是連通的，繼續(xù)這個過程，直到所得的圖T無圈為止，則T就是G的一棵生成樹。定義：若圖G的生成子圖是一棵樹，則稱該樹為G的生成樹(支撐樹)。或簡稱為圖G的樹(b)為(a)圖的生成樹圖與網(wǎng)絡(luò)模型及方法定理：無向圖G有生成樹當(dāng)且僅當(dāng)G連通。定義：若圖G的生成子29最小生成樹的求法：避圈法與破圈法定義：樹的各條邊稱為樹枝。一般圖G的生成樹有多個，稱其中樹枝總長度最小的生成樹為最小樹。避圈法：在圖G中，每步選出一條邊e，使它與已選邊不構(gòu)成圈，且e是未選邊中長度最小的邊，直到選夠n-1邊為止。?????????v1v2v3v8v7v6v5v4v04112131444523552?????????v1v2v3v8v7v6v5v4v011211232圖與網(wǎng)絡(luò)模型及方法最小生成樹的求法：避圈法與破圈法定義：樹的各條邊稱為樹枝。30?????????v1v2v3v8v7v6v5v4v04112131444523552?????????v1v2v3v8v7v6v5v4v011211232破圈法：從網(wǎng)絡(luò)圖N中任取一回路，去掉該回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N1。在N1中再任取一回路，去掉該回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N2。如此繼續(xù)下去，直到剩下的子圖中不再含回路為止。該子圖就是N的最小生成樹。?????????v1v2v3v8v7v6v5v4v04112131444523552圖與網(wǎng)絡(luò)模型及方法?????????v1v2v3v8v7v6v5v4v041131筑路選線問題欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵路造價為wij，設(shè)計一個線路圖使總造價最低連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具最小權(quán)的生成樹叫做最小生成樹造最小生成樹的兩種常用算法---prim算法與Kruskal算法。圖與網(wǎng)絡(luò)模型及方法筑路選線問題欲修筑連接n個城市的鐵路，已知i城與j城之間的鐵32prim算法構(gòu)造最小生成樹設(shè)置兩個集合P和Q,其中P用于存放G的最小生成樹中的頂點(diǎn)，集合Q存放G的最小生成樹中的邊。令集合P的初值為{}1P=v（假設(shè)構(gòu)造最小生成樹時，從頂點(diǎn)

v1出發(fā)），集合Q的初值為Q=Φ。prim算法的思想是：從所有p∈P，v∈V?P的邊中，選取具有最小權(quán)值的邊pv，將頂點(diǎn)v加入集合P中，將邊pv加入集合Q中，如此不斷重復(fù)，直到P=V時，最小生成樹構(gòu)造完畢，這時集合Q中包含了最小生成樹的所有邊。圖與網(wǎng)絡(luò)模型及方法prim算法構(gòu)造最小生成樹設(shè)置兩個集合P和Q,其中P用33圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法34Kruskal算法構(gòu)造最小生成樹圖與網(wǎng)絡(luò)模型及方法Kruskal算法構(gòu)造最小生成樹圖與網(wǎng)絡(luò)模型及方法35可行遍問題定義1：經(jīng)過G的每條邊的跡叫做G的Euler跡；閉的Euler跡叫做Euler回路或E回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點(diǎn)出發(fā)每邊恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的邊再回到出發(fā)點(diǎn)。圖與網(wǎng)絡(luò)模型及方法可行遍問題定義1：經(jīng)過G的每條邊的跡叫做G的Eule36定理6（i）G是Euler圖的充分必要條件是G連通且每頂點(diǎn)皆偶次。（ii）G是Euler圖的充分必要條件是G連通且（iii）G中有Euler跡的充要條件是G連通且至多有兩個奇次點(diǎn)。圖與網(wǎng)絡(luò)模型及方法定理6（i）G是Euler圖的充分必要條件是G連通且37定義包含G的每個頂點(diǎn)的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或H圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點(diǎn)出發(fā)每頂點(diǎn)恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的頂點(diǎn)再回到出發(fā)點(diǎn)。圖與網(wǎng)絡(luò)模型及方法定義包含G的每個頂點(diǎn)的軌叫做Hamilton(哈密頓)軌38圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法39圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法40圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法41Euler回路的Fleury算法圖與網(wǎng)絡(luò)模型及方法Euler回路的Fleury算法圖與網(wǎng)絡(luò)模型及方法42可行遍問題的應(yīng)用中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當(dāng)然他必須經(jīng)過他負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計一條投遞路線，使得他行程最短。中國郵遞員問題的數(shù)學(xué)模型：在一個賦權(quán)連通圖上求一個含所有邊的回路，且使此回路的權(quán)最小。圖與網(wǎng)絡(luò)模型及方法可行遍問題的應(yīng)用中國郵遞員問題圖與網(wǎng)絡(luò)模型及方法43若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。對于非Euler圖，1973年，Edmonds和Johnson給出下面的解法：圖與網(wǎng)絡(luò)模型及方法若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求44多郵遞員問題郵局有k(k≥2)位投遞員，同時投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時間最早？我們把這一問題記成kPP。kPP的數(shù)學(xué)模型如下：圖與網(wǎng)絡(luò)模型及方法多郵遞員問題郵局有k(k≥2)位投遞員，同時投遞信件，全45旅行商（TSP）問題一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？是在一個賦權(quán)完全圖中，找出一個有最小權(quán)的Hamilton圈。稱這種圈為最優(yōu)圈與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。圖與網(wǎng)絡(luò)模型及方法旅行商（TSP）問題一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后46改良圈算法。圖與網(wǎng)絡(luò)模型及方法改良圈算法。圖與網(wǎng)絡(luò)模型及方法47旅行商問題的數(shù)學(xué)表達(dá)式圖與網(wǎng)絡(luò)模型及方法旅行商問題的數(shù)學(xué)表達(dá)式圖與網(wǎng)絡(luò)模型及方法48對集圖與網(wǎng)絡(luò)模型及方法對集圖與網(wǎng)絡(luò)模型及方法49圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法50圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法51圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法521957年，貝爾熱(Berge)得到最大對集的充要條件：定理2M是圖G中的最大對集當(dāng)且僅當(dāng)G中無M可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3G為二分圖，X與Y是頂點(diǎn)集的劃分，G中存在把X中頂點(diǎn)皆許配的對集的充要條件是，，?S?X，則|N(S)|≥|S|，其中N(S)是S中頂點(diǎn)的鄰集。圖與網(wǎng)絡(luò)模型及方法1957年，貝爾熱(Berge)得到最大對集的充要條件：圖53推論1：若G是k次（k>0)正則2分圖，則G有完美對集。所謂k次正則圖，即每頂點(diǎn)皆k度的圖。由此推論得出下面的婚配定理：定理4每個姑娘都結(jié)識k(k≥1)位小伙子，每個小伙子都結(jié)識k位姑娘，則每位姑娘都能和她認(rèn)識的一個小伙子結(jié)婚，并且每位小伙子也能和他認(rèn)識的一個姑娘結(jié)婚。圖與網(wǎng)絡(luò)模型及方法推論1：若G是k次（k>0)正則2分圖，則G有完54人員分派問題工作人員x1,x2,…,xn

去做n件工作y1,y2,…,yn

，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個問題的數(shù)學(xué)模型是：G是二分圖，頂點(diǎn)集劃分為V(G)=XUY，X={x1,…,xn}，Y={y1,…,yn}，當(dāng)且僅當(dāng)xi適合做工作yj時，xiyj

∈E(G)，求G中的最大對集。圖與網(wǎng)絡(luò)模型及方法人員分派問題工作人員x1,x2,…,xn去做55人員分派問題匈牙利算法1965年埃德門茲(Edmonds)提出匈牙利算法。匈牙利算法：（i）從G中任意取定一個初始對集M。（ii）若M把X中的頂點(diǎn)皆許配，停止，M即完美對集；否則取X中未被M許配的一頂點(diǎn)u，記S={u}，T=Φ。（iii）若N(S)=T，停止，無完美對集；否則取y∈N(S)?T。（iv）若y是被M許配的，設(shè)yz∈M，S=SU{z}，T=TU{y}，轉(zhuǎn)（iii）；否則，取可增廣軌P(u,y)，令M=(M?E(P))U(E(P)?M)，轉(zhuǎn)（ii）。圖與網(wǎng)絡(luò)模型及方法人員分派問題匈牙利算法1965年埃德門茲(Edmonds)56最優(yōu)分派問題在人員分派問題中，工作人員適合做的各項工作當(dāng)中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖G的每邊加了權(quán)w(xi

，

yj)≥0表示xi干yj工作的效益，求加權(quán)圖G上的權(quán)最大的完美對集。解決這個問題可以用庫恩—曼克萊斯（Kuhn-Munkres）算法圖與網(wǎng)絡(luò)模型及方法最優(yōu)分派問題在人員分派問題中，工作人員適合做的各項工作當(dāng)中，57定義若映射l:V(G)→R，滿足?x∈X,y∈Y，l(x)+l(y)≥w(x,y)，則稱l是二分圖G的可行頂點(diǎn)標(biāo)號。令El

={xy|xy∈E(G),l(x)+l(y)=w(xy)}，稱以lE為邊集的G的生成子圖為相等子圖，記作Gl?？尚许旤c(diǎn)標(biāo)號是存在的。例如定理5G

l的完美對集即為G的權(quán)最大的完美對集。圖與網(wǎng)絡(luò)模型及方法定義若映射l:V(G)→R，滿足?x∈X,y∈Y58Kuhn-Munkres算法圖與網(wǎng)絡(luò)模型及方法Kuhn-Munkres算法圖與網(wǎng)絡(luò)模型及方法59最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以便用這個模型．如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。最短路問題的一般提法：設(shè)G={V，E}為連通圖，圖中各邊(vi,vj)有權(quán)l(xiāng)ij(lij=∞表示vi,vj間無邊)。vs,vt為圖中任意兩點(diǎn)，求一條路μ，使它是從vs到vt的所有路中總權(quán)最小的路。即最小有些最短路問題是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有點(diǎn)的最短路，或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。下面介紹三種算法，可分別用于求解這幾種最短路問題。圖與網(wǎng)絡(luò)模型及方法最短路問題最小有些最短路問題是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有點(diǎn)的60(2)使用條件——網(wǎng)絡(luò)中所有的弧(邊)權(quán)均非負(fù)，即：(1)基本思路基于以下原理：若序列{vs,v1,…,vn-1,vn}是從vs到vn的最短路，則序列{vs,v1,…,vn-1}必為從vs到vn-1的最短路。

1、Dijkstra算法本算法由Dijkstra于1959年提出，可用于求解指定兩點(diǎn)vs、vt間的最短路，或從指定點(diǎn)vs到其余各點(diǎn)的最短路。下面給出Dijkstra算法基本步驟，采用標(biāo)號法。圖與網(wǎng)絡(luò)模型及方法(2)使用條件——網(wǎng)絡(luò)中所有的弧(邊)權(quán)均非負(fù)，即：(1)61可用兩種標(biāo)號：T標(biāo)號與P標(biāo)號，T標(biāo)號為試探性標(biāo)號，P為永久性標(biāo)號，給vi點(diǎn)一個P標(biāo)號時，表示從vs到點(diǎn)vi的最短路權(quán),vi點(diǎn)的標(biāo)號不再改變。給vi點(diǎn)一個T標(biāo)號時．表示從vs到點(diǎn)vi的估計最短路權(quán)的上界，是一種臨時標(biāo)號．凡沒有得到P標(biāo)號的點(diǎn)都有T標(biāo)號。算法每一步都把某一點(diǎn)的T標(biāo)號改為P標(biāo)號，當(dāng)終點(diǎn)vt得到P標(biāo)號時，全部計算結(jié)束。對于有n個頂點(diǎn)的圖，最多經(jīng)n一1步就可以得到從始點(diǎn)到終點(diǎn)的最短路。標(biāo)號的意義：①標(biāo)號P(永久性標(biāo)號)—從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。②標(biāo)號T(臨時性標(biāo)號—從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)上界。圖與網(wǎng)絡(luò)模型及方法可用兩種標(biāo)號：T標(biāo)號與P標(biāo)號，T標(biāo)號為試探性標(biāo)號，P為永久性62計算步驟：第二步：若vi為剛得到P標(biāo)號的點(diǎn)，考慮這樣的點(diǎn)vj：(vi,vj)屬于E，且vj為T標(biāo)號。對vj的T標(biāo)號進(jìn)行如下的更改：T(vj)=min{T(vj),P(vi)+lij}第三步：比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號，即

第一步：給始點(diǎn)vs標(biāo)上永久性標(biāo)號P(vs)=0，其余各點(diǎn)標(biāo)臨時性標(biāo)號T(vj)=+,當(dāng)存在兩個以上最小者時，可同時改為P標(biāo)號。若全部點(diǎn)均為P標(biāo)號則停止。否則用代vi轉(zhuǎn)回第二步。圖與網(wǎng)絡(luò)模型及方法計算步驟：第二步：若vi為剛得到P標(biāo)號的點(diǎn)，考慮這樣的點(diǎn)vj63例、用Dijkstar算法求下圖中v1到v7點(diǎn)的最短路。???????v1v3v2v7v5v4v6171344452572(1)首先給v1以P標(biāo)號,P(v1)=0,其余所有點(diǎn)給T標(biāo)號,T(vi)=+∞（圖中()內(nèi)的數(shù)表示P標(biāo)號；[]內(nèi)的數(shù)表示T標(biāo)號）???????v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7圖與網(wǎng)絡(luò)模型及方法例、用Dijkstar算法求下圖中v1到v7點(diǎn)的最短路。??64???????v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞](2)由于邊(v1,v2)、(v1,v3)、(v1,v4)屬于E，且v2,v3,v4為T標(biāo)號，所以修改這三個點(diǎn)的標(biāo)號：

T(v2)=min{T(v2),P(v1)+l12}=min{∞,0+4}=4 T(v3)=min{T(v3),P(v1)+l13}=min{∞,0+2}=2

T(v4)=min{T(v4),P(v1)+l14}=min{∞,0+5}=57(3)比較所有T標(biāo)號，T(v3)最小，所以令P(v3)=2圖與網(wǎng)絡(luò)模型及方法???????v1v2v7v5v411344452572v365???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]7???????v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]7(4)v3為剛得到P標(biāo)號的點(diǎn)，考察邊(v3,v4),(v3,v6)的端點(diǎn)v4,v6。

T(v4)=min{T(v4),P(v3)+l34}=min{5,2+2}=4 T(v6)=min{T(v6),P(v3)+l36}=min{∞,2+7}=9(5)比較所有T標(biāo)號，T(v2),T(v4)最小，所以令P(v2)=P(v4)=4圖與網(wǎng)絡(luò)模型及方法???????v1v2v7v5v411344452572v366???????v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]7(6)v2,v4為剛得到P標(biāo)號的點(diǎn),考察邊(v2,v5),),(v4,v5),(v4,v6)的端點(diǎn)v5,v6。

T(v5)=min{T(v5),P(v4)+l45,P(v2)+l25}=min{∞,4+3,4+4}=7 T(v6)=min{T(v6),P(v4)+l46}=min{9,4+4}=8???????v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v6圖與網(wǎng)絡(luò)模型及方法???????v1v2v7v5v411344452572v367(7)比較所有T標(biāo)號，T(v5)所以令P(v5)=7???????v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v6???????v1(0)v2v7v5v411344452572(4)(4)(7)[14][8]v3(2)v6(8)v5為剛得到P標(biāo)號的點(diǎn)，考察邊(v5,v6),(v5,v7)的端點(diǎn)v6,v7。

T(v6)=min{T(v6),P(v5)+l56}=min{8,7+1}=8 T(v7)=min{T(v7),P(v5)+l57}=min{∞,7+7}=1477圖與網(wǎng)絡(luò)模型及方法(7)比較所有T標(biāo)號，T(v5)所以令P(v5)=7??68(9)比較所有T標(biāo)號，T(v6)最小，所以令P(v6)=8???????v1(0)v2v7v5v411344452572(4)(4)(7)[14](8)v3(2)v6(10)v6為剛得到P標(biāo)號的點(diǎn)，考察邊(v6,v7)的端點(diǎn)v7。

T(v7)=min{T(v7),P(v6)+l67}=min{14,8+5}=13???????v1(0)v2v7v5v411344452572(4)(4)(7)[13](8)v3(2)v677圖與網(wǎng)絡(luò)模型及方法(9)比較所有T標(biāo)號，T(v6)最小，所以令P(v6)=869(11)只有一個T標(biāo)號T(v7)，令P(v7)=13，停止。???????v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67計算結(jié)果見上圖，v1到v7的最短路為：同時得到v1到其余各點(diǎn)的最短路*這個算法只適用于全部權(quán)為非負(fù)情況．如果某邊的權(quán)為負(fù)，算法失效。圖與網(wǎng)絡(luò)模型及方法(11)只有一個T標(biāo)號T(v7)，令P(v7)=13，70上面的例題是針對無向圖求最短路的問題，對有向圖最短路的求法類似。下面以設(shè)備更新問題為例說明有向圖最短路的計算方法。例(設(shè)備更新問題)某企業(yè)在四年內(nèi)都要使用某種設(shè)備，在每年年初作出是購買新設(shè)備還是繼續(xù)使用舊設(shè)備的決策。若購買新設(shè)備就要支付購置費(fèi)；若繼續(xù)使用舊設(shè)備，則需支付維修費(fèi)用。這種設(shè)備在四年之內(nèi)每年年初的價格以及使用不同時間（年）的設(shè)備的維修費(fèi)用估計為：年份1234年初購價10111213維修費(fèi)用24714問題：制定一個四年之內(nèi)的設(shè)備更新計劃，使得四年之內(nèi)的設(shè)備購置費(fèi)和維修費(fèi)用之和最小。圖與網(wǎng)絡(luò)模型及方法上面的例題是針對無向圖求最短路的問題，對有向圖最短路的求法類71可以用求最短路問題的方法來解決總費(fèi)用最少的設(shè)備更新計劃問題。符號的含義：vi—第i年年初購進(jìn)一臺新設(shè)備(v5表示第四年年底)弧(vi,vj)—表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初(即第j-1年年底)弧(vi,vj)的權(quán)數(shù)表示從第i年年初購進(jìn)的設(shè)備一直使用到第j年年初所花費(fèi)的購置費(fèi)和維修費(fèi)用的總和。如何制定使得總費(fèi)用最少的設(shè)備更新計劃問題可以轉(zhuǎn)化最短路問題。此最短路問題如圖所示。圖與網(wǎng)絡(luò)模型及方法可以用求最短路問題的方法來解決總費(fèi)用最少的設(shè)備更新計劃問題。72圖中權(quán)數(shù)

ij的確定：

12=10+2=12；13=10+2+4=16；14=10+2+4+7=23；15=10+2+4+7+14=37；23=11+2=13；24=11+2+4=17；25=11+2+4+7=24；34=12+2=14；35=12+2+4=18；45=13+2=15下面用Dijkstra算法求v1到v5的最短路。給v1以P標(biāo)號，P(v1)=0,其余各點(diǎn)給以T標(biāo)號，T(vi)=+∞(i=2,3,4,5)。（圖中()內(nèi)的數(shù)表示P標(biāo)號；[]內(nèi)的數(shù)表示T標(biāo)號）圖與網(wǎng)絡(luò)模型及方法圖中權(quán)數(shù)ij的確定：下面用Dijkstra算法求v1到v573(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）∈A，且v2,v3,v4,v5為T標(biāo)號，所以修改這四個點(diǎn)的標(biāo)號：T(v2)=min{T(v2),P(v1)+

12}=min{+∞,0+12}=12T(v3)=min{T(v3),P(v1)+13}=min{+∞,0+16}=16T(v4)=min{T(v4),P(v1)+14}=min{+∞,0+23}=23T(v5)=min{T(v5),P(v1)+15}=min{+∞,0+37}=37(3)比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號。T(v2)最小，令P(v2)=12。圖與網(wǎng)絡(luò)模型及方法(2)由于（v1,v2）,(v1,v3),（v1,v4）,（74(4)v2為剛得到P標(biāo)號的點(diǎn)，考察弧(v2,v3),(v2,v4),(v2,v5)的端點(diǎn)v3,v4,v5。T(v3)=min{T(v3),P(v2)+

23}=min{16,12+13}=16T(v4)=min{T(v4),P(v2)+24}=min{23,12+17}=23T(v5)=min{T(v5),P(v2)+25}=min{37,12+24}=36(5)比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號。T(v3)最小，令P(v3)=16。圖與網(wǎng)絡(luò)模型及方法(4)v2為剛得到P標(biāo)號的點(diǎn)，考察弧(v2,v3),(v275(6)考察點(diǎn)v3

T(v4)=min{T(v4),P(v3)+

34}=min{23,16+14}=23T(v5)=min{T(v5),P(v3)+35}=min{36,16+18}=34(7)所有T標(biāo)號中，T(v4)最小，令P(v4)=23圖與網(wǎng)絡(luò)模型及方法(6)考察點(diǎn)v3圖與網(wǎng)絡(luò)模型及方法76(8)考察點(diǎn)v4T(v5)=min{T(v5),P(v4)+

45}=min{34,23+15}=34(9)只有一個T標(biāo)號T(v5)，令P(v5)=34，計算結(jié)束。由上可知：v1到v5的最短路為v1→v3→v5,長度為34。其含義為：最佳更新計劃為第一年年初購買新設(shè)備使用到第二年年底(第三年年初)，第三年年初再購買新設(shè)備使用到第四年年底，這個計劃使得總的支付最小，其值為34。圖與網(wǎng)絡(luò)模型及方法(8)考察點(diǎn)v4圖與網(wǎng)絡(luò)模型及方法77???????v1v3v2v7v5v4v617134452572練習(xí)、求下圖中任意兩點(diǎn)間的最短路4圖與網(wǎng)絡(luò)模型及方法???????v1v3v2v7v5v4v617134452578例、某地7個村莊之間的現(xiàn)有交通道路如下圖所示，邊旁數(shù)字為各村莊之間道路的長度?，F(xiàn)要在某一村莊修建一所小學(xué)，該小學(xué)應(yīng)建在哪個村莊,可使離該村最遠(yuǎn)的村莊的學(xué)生所走的路程最少？該問題可分作兩步來考慮：1）求出任意兩個村莊之間的最短路長；2）找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn),大中取小即可。圖與網(wǎng)絡(luò)模型及方法例、某地7個村莊之間的現(xiàn)有交通道路如下圖所示，邊旁數(shù)字為各村79首先寫出權(quán)矩陣用Floyd算法求出任意兩點(diǎn)之間的最短路的長度找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn)取這些最遠(yuǎn)距離中的最小者(小學(xué)應(yīng)建在v4村)max作業(yè):P227

習(xí)題4.4圖與網(wǎng)絡(luò)模型及方法首先寫出權(quán)矩陣用Floyd算法求出任意兩點(diǎn)之間的最短路的長度80覆蓋與點(diǎn)獨(dú)立集圖與網(wǎng)絡(luò)模型及方法覆蓋與點(diǎn)獨(dú)立集圖與網(wǎng)絡(luò)模型及方法81圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法82圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法83圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法84圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法85圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法86圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法87圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法88圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法89圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法90圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法91圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法92最大流問題最大流問題是在一個給定網(wǎng)絡(luò)上求流量最大的可行流，即給一個網(wǎng)絡(luò)的每條弧規(guī)定一個流量的上界，求從點(diǎn)vs到vt的最大流。下圖是一個輸油管道網(wǎng)，vs為起點(diǎn)，vt為終點(diǎn)，v1~v6為中轉(zhuǎn)站，弧旁的數(shù)表示該管道的最大輸油量。問題：如何安排，才能使從vs到vt的輸油量最大？圖與網(wǎng)絡(luò)模型及方法最大流問題最大流問題是在一個給定網(wǎng)絡(luò)上求流量最大的可行流，即93最大流問題1最大流問題的數(shù)學(xué)描述1.1網(wǎng)絡(luò)中的流定義在以V為節(jié)點(diǎn)集，A為弧集的有向圖G=(V,A)上定義如下的權(quán)函數(shù)：圖與網(wǎng)絡(luò)模型及方法最大流問題圖與網(wǎng)絡(luò)模型及方法94（i）L:A→R為孤上的權(quán)函數(shù)，弧(i,j)∈A對應(yīng)的權(quán)L(i,j)記為lij，稱為孤(i,j)的容量下界（lowerbound）；（ii）U:A→R為弧上的權(quán)函數(shù)，弧(i,j)∈A對應(yīng)的權(quán)U(i,j)記為uij，稱為孤(i,j)的容量上界，或直接稱為容量（capacity）；（iii）D:V→R為頂點(diǎn)上的權(quán)函數(shù)，節(jié)點(diǎn)i∈V對應(yīng)的權(quán)D(i)記為di，稱為頂點(diǎn)i的供需量（supply／demand）；此時所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記為N=(V,A,L,U,D)。圖與網(wǎng)絡(luò)模型及方法（i）L:A→R為孤上的權(quán)函數(shù)，弧(i,j)∈A95由于我們只討論V,A為有限集合的情況，所以對于弧上的權(quán)函數(shù)L,U和頂點(diǎn)上的權(quán)函數(shù)D，可以直接用所有孤上對應(yīng)的權(quán)和頂點(diǎn)上的權(quán)組成的有限維向量表示，因此L,U,D有時直接稱為權(quán)向量，或簡稱權(quán)。由于給定有向圖G=(V,A)后，我們總是可以在它的弧集合和頂點(diǎn)集合上定義各種權(quán)函數(shù)，所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò)。圖與網(wǎng)絡(luò)模型及方法由于我們只討論V,A為有限集合的情況，所以對于弧上的權(quán)函數(shù)96定義對于流網(wǎng)絡(luò)N=(V,A,L,U,D)，其上的一個流（flow）f是指從N的弧集A到R的一個函數(shù)，即對每條弧(i,j)賦予一個實數(shù)fij

（稱為弧(i,j)的流量）。如果流f滿足則稱f為可行流（feasibleflow）。至少存在一個可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasiblenetwork）．約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。圖與網(wǎng)絡(luò)模型及方法定義對于流網(wǎng)絡(luò)N=(V,A,L,U,D)，其上的一97定義：設(shè)有向連通圖G＝(V,E)，G的每條邊(vi,vj)上有非負(fù)數(shù)cij稱為邊的容量，僅有一個入次為0的點(diǎn)vs稱為發(fā)點(diǎn)(源)，一個出次為0的點(diǎn)vt稱為收點(diǎn)(匯)，其余點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，常記做G＝(V,E,C)。對任一G中的邊(vi,vj)有流量fij,，稱集合f＝{fij}網(wǎng)絡(luò)G上的一個流。稱滿足下列條件的流f為可行流：

(1)容量限制條件：對G中每條邊(vi,vj)，有0≤fij≤cij(2)平衡條件：對中間點(diǎn)vi，

(即中間點(diǎn)vi的物資的輸入量與輸出量相等)

對收、發(fā)點(diǎn)vs,vt,有

(即從vs點(diǎn)發(fā)出的物資總量等于vt點(diǎn)輸入的量。)W為網(wǎng)絡(luò)流的總流量。圖與網(wǎng)絡(luò)模型及方法定義：設(shè)有向連通圖G＝(V,E)，G的每條邊(vi,vj98可行流總是存在的，例如f＝{0}就是一個流量為0的可行流。最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。一個流f={fij},當(dāng)fij=cij，則稱流f對邊(vi,vj)是飽和的，否則稱f對(vi,vj)不飽和。根據(jù)弧的流量是否為0，可把弧分為零流弧和非零流弧兩類。最大流問題實際是個線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系，能更為直觀簡便地求解。圖與網(wǎng)絡(luò)模型及方法可行流總是存在的，例如f＝{0}就是一個流量為0的可行流。圖99把網(wǎng)絡(luò)D=(V,E,C)的點(diǎn)集V剖分為兩個非空集合Vs和Vt(即Vs∩Vt=

，Vs∪Vt=V)，使vs∈Vs,vt∈Vt，把從Vs指向Vt的弧的全體稱為（分離vs和vt的）截集。稱截集中所有弧的容量之和為這個截集的容量（簡稱為截量）。分離vs和vt的截集往往不只一個，稱其中截量最小的為最小截集。。圖與網(wǎng)絡(luò)模型及方法把網(wǎng)絡(luò)D=(V,E,C)的點(diǎn)集V剖分為兩個非空集合Vs和Vt100由截集的定義可知：截集是從vs到vt的必經(jīng)之路，無論去掉哪個截集，從vs到vt就不存在路了，因此任何一個可行流的流量不會超過任何一個截集的容量。因而若能找到一個可行流和一個截集，使得可行流的流量等于這個截集的容量，則該可行流一定是最大流，該截集一定是最小截集。在上圖中，若令Vs={vs,v1,v6},Vt={v2,v3,v4,v5,vt},則：截集為{(vs,v5)(v1,v2),(v1,v5),(v6,v5),(v6,v4)},截量為3+2+4+2+3=14；圖與網(wǎng)絡(luò)模型及方法由截集的定義可知：截集是從vs到vt的必經(jīng)之路，無論去101設(shè)

是網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向為從vs到vt，沿此方向上的弧可分為兩類：一類是與鏈的方向一致的弧稱為正向弧，用

+

表示正向弧的全體，另一類是與鏈的方向相反的弧稱為反向弧，用-

表示反向弧的全體。在上圖中，在鏈

={vs,v5,v6,v4,v3,vt}中，+={(vs,v5),(v6,v4),(v3,vt)},

-={(v5,v6),(v4,v3)}。增廣鏈：對于可行流f，是一條從vs到vt的一條鏈，如果+中的弧均為非飽和弧，-中的弧均為非零流弧，則稱為從vs到vt的關(guān)于f的增廣鏈。定理（最大流量—最小截量定理）：在網(wǎng)絡(luò)N中，從vs到vt的最大流的流量等于分離vs到vt的最小截集的截量。圖與網(wǎng)絡(luò)模型及方法設(shè)是網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向為從vs到vt，沿102計算網(wǎng)絡(luò)最大流的方法增廣鏈的實際意義在于沿著這條鏈存在增大輸送能力的潛力。如沿著增廣鏈

1={vs,v2,v5,v4,v6,vt}，凡是正向弧的流量都增加1，反向弧的流量都減少1（見上圖），結(jié)果整個網(wǎng)絡(luò)的流增加了1，即由6增加到7。用這種方法調(diào)整后的流仍為可行流。這樣就得到了一個尋找最大流的方法：從一個可行流開始，尋找關(guān)于這個可行流的增廣鏈，若增廣鏈存在，則可以經(jīng)過調(diào)整，得到一個新的可行流，其流量比調(diào)整前的可行流大，重復(fù)這個過程，直到不存在增廣鏈時就得到了最大流。圖與網(wǎng)絡(luò)模型及方法計算網(wǎng)絡(luò)最大流的方法圖與網(wǎng)絡(luò)模型及方法103下面介紹計算網(wǎng)絡(luò)最大流的標(biāo)號算法標(biāo)號法是由Ford和Fulkerson在1957年提出的設(shè)已有一個可行流f(若網(wǎng)絡(luò)中沒有給出可行流,則可設(shè)f為零流)，標(biāo)號法可分為兩步：（一）標(biāo)號過程在這個過程中,網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號點(diǎn)，或者是未標(biāo)號點(diǎn)。每個標(biāo)號點(diǎn)的標(biāo)號包含兩個部分：第一個標(biāo)號表明它的標(biāo)號是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個標(biāo)號是為確定增廣鏈的調(diào)整量

用的。(1)給發(fā)點(diǎn)vs以標(biāo)號（0，+∞），第二個數(shù)值表示從上一標(biāo)號點(diǎn)到這個標(biāo)號點(diǎn)的最大允許調(diào)整量。vs為發(fā)點(diǎn)，不限允許調(diào)整量，故為+∞。最大流的一種算法—標(biāo)號法圖與網(wǎng)絡(luò)模型及方法下面介紹計算網(wǎng)絡(luò)最大流的標(biāo)號算法最大流的一種算法—標(biāo)號法圖與104(2)選擇一個已標(biāo)號的點(diǎn)vi,對于vi的所有未標(biāo)號的鄰點(diǎn)vj,按下列規(guī)則處理：若邊(vi,vj)∈E,且fij<cij,則令vj=min{vi,cij-fij},并給vj以標(biāo)號（vi,vj）。若邊(vj,vi)∈E,且fji>0,則令vj=min{fji,vi},并給vj以標(biāo)號(-vi,vj)(3)重復(fù)(2)直到收點(diǎn)vt被標(biāo)號或不再有點(diǎn)可標(biāo)號時為止。若vt得到標(biāo)號，說明存在一條增廣鏈，轉(zhuǎn)(二)調(diào)整過程。若vt未得到標(biāo)號，標(biāo)號過程已無法進(jìn)行時，說明f已是最大流。（二）調(diào)整過程

(1)確定調(diào)整量

=

vt，

(2)若vt的標(biāo)號為（vj,vt）,則以fit+代替fit;若vt的標(biāo)號為 （-vj,vt）,則以fit-代替fit。

(3)令vj代替vt，返回(2)；若vj=vs，則去掉所有標(biāo)號轉(zhuǎn)(一)。圖與網(wǎng)絡(luò)模型及方法(2)選擇一個已標(biāo)號的點(diǎn)vi,對于vi的所有未標(biāo)號的鄰點(diǎn)v105標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基本思想。用標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止。即首先給出一個初始流，這樣的流是存在的，例如零流。如果存在關(guān)于它的可增廣軌，那么調(diào)整該軌上每條弧上的流量，就可以得到新的流。對于新的流，如果仍存在可增廣軌，則用同樣的方法使流的值增大，繼續(xù)這個過程，直到網(wǎng)絡(luò)中不存在關(guān)于新得到流的可增廣軌為止，則該流就是所求的最大流。圖與網(wǎng)絡(luò)模型及方法標(biāo)號法尋求網(wǎng)絡(luò)中最大流的基本思想。用標(biāo)號法尋求網(wǎng)絡(luò)中最大流的106標(biāo)號法過程A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。這兩個過程的步驟分述如下圖與網(wǎng)絡(luò)模型及方法標(biāo)號法過程A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。圖與網(wǎng)107圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法108圖與網(wǎng)絡(luò)模型及方法圖與網(wǎng)絡(luò)模型及方法109例、用標(biāo)號法求下圖所示的網(wǎng)絡(luò)中從vs到vt的最大流量，圖中弧旁數(shù)值為容量cij(1)圖中沒有給出初始可行流,可設(shè)零流為出初始可行流.如圖1。先給vs標(biāo)以標(biāo)號（0，+∞）。(2)檢查vs的鄰點(diǎn)v1,v2可知（vs,v1）∈E，且fs1=0<cs1=10,令

v1=min{+∞,10-0}=10,給v1以標(biāo)號（vs,10）。用同樣的方法給v2以標(biāo)號（vs,14）。見圖2圖與網(wǎng)絡(luò)模型及方法例、用標(biāo)號法求下圖所示的網(wǎng)絡(luò)中從vs到vt的最大流量，圖中弧110(3)檢查v1的尚未標(biāo)號的鄰點(diǎn)v3,v4可知(v1,v3)∈E，且f13=0<c13=10,令

v3=min{v1,10-0}=min{10,10}=10,給v3以標(biāo)號(v1,10),用同樣的方法給v4以標(biāo)號(v1,10)。圖與網(wǎng)絡(luò)模型及方法(3)檢查v1的尚未標(biāo)號的鄰點(diǎn)v3,v4可知(v1,v3)111(4)檢查v3的尚未標(biāo)號的鄰點(diǎn)v5,v6可知(v3,v5）∈E，且f35=0<c35=4,令

v5=min{v3,4-0}=min{10,4}=4,給v5以標(biāo)號(v3,4),對于v6，由于(v6,v3)∈E，且f63=0，不滿足標(biāo)號條件。檢查v4的尚未標(biāo)號的鄰點(diǎn)vt可知(v4,vt)∈E，且f4t=0<c4t=13,令vt=min{v4,13-0}=min{10,13}=10,給vt以標(biāo)號(v4,10)。圖與網(wǎng)絡(luò)模型及方法(4)檢查v3的尚未標(biāo)號的鄰點(diǎn)v5,v6可知(v3,v5）112(5)由于vt已得到標(biāo)號，則存在增廣鏈，標(biāo)號過程結(jié)束，轉(zhuǎn)入調(diào)整過程。令

=

vt=10為調(diào)整量，從vt開始，按標(biāo)號(v4,10)找到v4并用f4t+10代替f4t，由標(biāo)號(v1,10)找到v1并用f14+10代替f14，再由標(biāo)號(vs,10)找到vs并用fs1+10代替fs1，調(diào)整過程結(jié)束。調(diào)整后的可行流見圖5。去掉所有標(biāo)號，重新開始標(biāo)號過程。圖5圖與網(wǎng)絡(luò)模型及方法(5)由于vt已得到標(biāo)號，則存在增廣鏈，標(biāo)號過程結(jié)束，轉(zhuǎn)入調(diào)113先給vs標(biāo)以標(biāo)號（0，+∞）。檢查vs的鄰點(diǎn)v1,v2可知（vs,v1）∈E但fs1=10=cs1=10,不滿足標(biāo)號條件。（vs,v2）∈E且fs2=0<cs2=14,令

v2=min{+∞，14-0}=14,給v2以標(biāo)號（vs,14）。（圖6）(v6,5)用同樣的方法可得v6的標(biāo)號(v2,5),vt的標(biāo)號(v6,5)圖與網(wǎng)絡(luò)模型及方法先給vs標(biāo)以標(biāo)號（0，+∞）。(v6,5)用同樣的方法可得v114令

=5為調(diào)整量，從vt開始進(jìn)行調(diào)整，調(diào)整后的可行流見下圖。去掉所有標(biāo)號，重新開始標(biāo)號過程。(0.+∞)(vs,9)(v2,.5)(v3,5)(v3,4)不滿足標(biāo)號條件（反向零流?。?v4,3)圖與網(wǎng)絡(luò)模型及方法令=5為調(diào)整量，從vt開始進(jìn)行調(diào)整，調(diào)整后的可行流見下圖。115去掉所有標(biāo)號，重新開始標(biāo)號過程。令

=3為調(diào)整量，從vt開始進(jìn)行調(diào)整，調(diào)整后的可行流見下圖。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)圖與網(wǎng)絡(luò)模型及方法去掉所有標(biāo)號，重新開始標(biāo)號過程。令=3為調(diào)整量，從vt開始116令

=2為調(diào)整量，從vt開始進(jìn)行調(diào)整，調(diào)整后的可行流見下圖。(0.+∞)(v2,.2)(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)圖與網(wǎng)絡(luò)模型及方法令=2為調(diào)整量，從vt開始進(jìn)行調(diào)整，調(diào)整后的可行流見下圖。117用標(biāo)號法在得到最大流的同時也得到最小截集(如圖中虛線所示)。標(biāo)號點(diǎn)集合為VS,即VS={vs,v2}，未標(biāo)號點(diǎn)集合為Vt

，即Vt={v1,v3,v4,v5,v6,vt}，最小截集{(vs,v1),(v2,v3),(v2,v6)}。最小截集的意義：最小截集中各弧的容量總和決定了網(wǎng)絡(luò)的通過能力，為了提高網(wǎng)絡(luò)的通過能力，就必須增大最小截集中弧的容量。去掉所有標(biāo)號，重新開始標(biāo)號過程。(0.+∞)(vs,4)vt未得到標(biāo)號，但標(biāo)號過程已無法進(jìn)行,說明已得到最大流.其值為20。圖與網(wǎng)絡(luò)模型及方法用標(biāo)號法在得到最大流的同時也得到最小截集(如圖中虛線所示)。118352圖與網(wǎng)絡(luò)模型及方法352圖與網(wǎng)絡(luò)模型及方法119最小費(fèi)用流問題上面我們介紹了一個網(wǎng)絡(luò)上最短路以及最大流的算法，但是還沒有考慮到網(wǎng)絡(luò)上流的費(fèi)用問題，在許多實際問題中，費(fèi)用的因素很重要。例如，在運(yùn)輸問題中，人們總是希望在完成運(yùn)輸任務(wù)的同時，尋求一個使總的運(yùn)輸費(fèi)用最小的運(yùn)輸方案。這就是下面要介紹的最小費(fèi)用流問題。圖與網(wǎng)絡(luò)模型及方法最小費(fèi)用流問題上面我們介紹了一個網(wǎng)絡(luò)上最短路以及最大流的算法1204.6最小費(fèi)用流問題最小費(fèi)用最大流問題:給了一個帶收發(fā)點(diǎn)的網(wǎng)絡(luò),對每一條弧(vi,vj),除了給出容量cij外,還給出了這條弧的單位流量的費(fèi)用bij,要求一個最大流F,并使得總運(yùn)送費(fèi)用最小。最小費(fèi)用最大流的網(wǎng)絡(luò)圖論解法較麻煩,因此下面介紹用線性規(guī)劃模型結(jié)合運(yùn)籌學(xué)軟件求解最小費(fèi)用最大流問題例.某石油公司擁有一個管道網(wǎng)絡(luò),使用這個網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn),這個網(wǎng)絡(luò)的一部分如下圖所示.由于管道的直徑的變化,它的各段管道(vi,vj)的容量cij(單位:萬加侖/小時,各段管道單位流量的費(fèi)用為bij(單位:百元/萬加侖).如圖,從采地v1向銷地v7運(yùn)送石油,怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最小?求出最大流量和最小費(fèi)用.(弧旁括號中第一個數(shù)表示容量cij,第二個數(shù)表示單位流量的費(fèi)用bij)圖與網(wǎng)絡(luò)模型及方法4.6最小費(fèi)用流問題最小費(fèi)用最大流問題:給了一個帶收發(fā)121(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)(4,4)(1,3)(2,8)(6,3)(3,2)v1v2v7v4v3v6用線性規(guī)劃模型求解該問題,可分為兩個步驟:第一步先求出此網(wǎng)絡(luò)圖中的最大流量F,通過運(yùn)籌學(xué)軟件獲得以下結(jié)果.f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最大流量=10。圖與網(wǎng)絡(luò)模型及方法(6,6)(3,4)(5,7)(2,5)(2,4)(2,3)122第二步在最大流量F的所有解中,找出一個最小費(fèi)用的解.下面建立第二步中的線性規(guī)劃模型如下：仍然設(shè)弧(vi,vj)上的流量為fij,這時已知網(wǎng)絡(luò)中最大流量為F.線性規(guī)劃模型如下：s.t.圖與網(wǎng)絡(luò)模型及方法第二步在最大流量F的所有解中,找出一個最小費(fèi)用的解.下面123用管理運(yùn)籌學(xué)軟件,可求得如下結(jié)果：f12=4,f14=6,f25=3,f23=1,f43=3,f57=5,f36=2,f46=1,f47=2,f67=3,f35=2.其最優(yōu)值(最小費(fèi)用)=145.與前面求最大流的結(jié)果對比.f12=5,f14=5,f23=2,f25=3,f43=2,f46=1,f47=2,f35=2,f36=2,f57=5,f67=3最大流量=10。圖與網(wǎng)絡(luò)模型及方法用管理運(yùn)籌學(xué)軟件,可求得如下結(jié)果：f12=5,f14=5,f124如果把上例的問題改為：每小時運(yùn)送6萬加侖的石油從采地v1到銷地v7最小費(fèi)用是多少？應(yīng)怎樣運(yùn)送？這就變成了一個最小費(fèi)用流的問題。一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對每條弧(vi,vj)賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中，求一個給定值f的流量的最小費(fèi)用，這個給定值f的流量應(yīng)小于等于最大流量F，否則無解。求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可。在上例中只要把f12+f14=F改為f12+f14=f=6得到了最小費(fèi)用流的線性規(guī)劃的模型。圖與網(wǎng)絡(luò)模型及方法如果把上例的問題改為：每小時運(yùn)送6萬加侖的石油從采地v1到銷1254.7分配問題一、最大匹配例、考慮有n個工人，m件工作的工作分配問題。每個工人能力不同，各能勝任某幾項工作。假設(shè)每件工作只需一人做，每人只做一件工作