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

1、.|圖與子圖|圖的連通與割集|樹與支撐樹|最小樹|最短有向路|最大流|最小費(fèi)用流|最大對集|圖與網(wǎng)絡(luò) 無向圖的基本概念 網(wǎng)絡(luò)的基本概念|關(guān)聯(lián)矩陣和鄰接矩陣 關(guān)聯(lián)矩陣 鄰接矩陣 主要結(jié)論|子圖 |圖論起源于18 世紀(jì)。|第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736 年發(fā)表的“哥尼斯堡的七座橋”。|1847 年，克?；舴?yàn)榱私o出電網(wǎng)絡(luò)方程而引進(jìn)了“樹”的概念。|1857年，凱萊在計(jì)數(shù)烷n 2n+2 C H 的同分異構(gòu)物時(shí)，也發(fā)現(xiàn)了“樹”。|哈密爾頓于1859 年提|出“周游世界”游戲，用圖論的術(shù)語，就是如何找出一個(gè)連通圖中的生成圈|近幾十年來，由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展，大大地促進(jìn)了圖論研究和應(yīng)用

2、，圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、運(yùn)籌學(xué)，生物遺傳學(xué)、心理學(xué)、經(jīng)濟(jì)學(xué)、社會學(xué)等學(xué)科中。|圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。|如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個(gè)事物的特定的聯(lián)系，就得到了描述這個(gè)“圖”的幾何形象。|圖論為任何一個(gè)包含了一種二元關(guān)系的離散系統(tǒng)提供了一個(gè)數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。這個(gè)圖是連通的，且每個(gè)點(diǎn)都與偶數(shù)線相關(guān)聯(lián)這個(gè)圖是連通的，且每個(gè)點(diǎn)都與偶數(shù)線相關(guān)聯(lián)|圖與網(wǎng)絡(luò)是運(yùn)籌學(xué)（Operations Research）中的一個(gè)經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工

3、程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域|的最短路問題、最大流問題、最小費(fèi)用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。圖-由若干個(gè)點(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，EG 一個(gè)圖1v2v3v4v5v1e2e3e4e5e6em=6,n=5,jikvve 圖的基本概念有向圖無向圖邊e=(vi, vj)有方向vi為始點(diǎn)，vj為終點(diǎn)邊e=(vi, vj)無方向， 此時(shí)(v

4、i, vj)=(vj,vi) e4=(v3，v4） =(v4， v3）e4=(v3，v4)(v4，v3）e5=(v3，v4） =(v4， v3）此時(shí)(vi, vj)(vj,vi) 1v2v3v4v1e2e3e4e5e6e1v2v3v4v1e2e3e4e5e6ee5=(v4，v3)(v3，v4)圖有向圖無向圖二.常用名詞：1v2v3v4v1e2e3e4e5e6e1、端點(diǎn)和關(guān)聯(lián)邊：的關(guān)聯(lián)邊和點(diǎn)是的端點(diǎn)，邊是邊、則稱點(diǎn)若jikkjijikvveevvEvve,2、相鄰點(diǎn)和相鄰邊：邊邊稱為相鄰邊，簡稱鄰端點(diǎn)落在同一個(gè)頂點(diǎn)的相鄰點(diǎn)，簡稱鄰點(diǎn)，一條邊的兩個(gè)端點(diǎn)稱為3、多重邊與環(huán)：點(diǎn)的邊稱為環(huán)。兩個(gè)端點(diǎn)落在

5、同一個(gè)頂多重邊或平行邊；具有相同端點(diǎn)的邊稱為4、多重圖和簡單圖：無環(huán)也無多重邊的圖稱為簡單圖。含有多重邊的圖稱為多重圖；5、次：)(iiivdvv的次，點(diǎn)為端點(diǎn)的邊的條數(shù)稱為以點(diǎn)6、懸掛點(diǎn)和懸掛邊：次為1的點(diǎn)稱為懸掛點(diǎn)，與懸掛點(diǎn)相聯(lián)的邊稱為懸掛邊。7、孤立點(diǎn)：8、奇點(diǎn)與偶點(diǎn)：的點(diǎn)稱為孤立點(diǎn)次為0點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶次為奇數(shù)的點(diǎn)稱為奇點(diǎn)1v2v3v4v2e3e4e5e1e5v6v6e, 3)(1vd為懸掛點(diǎn)，、62vv為懸掛邊，、52ee為孤立點(diǎn)，5v4)(3vd, 1)(2vd, 3)(4vd, 0)(5vd, 1)(6vd為奇點(diǎn)，、6421vvvv為偶點(diǎn)、35vv)(ivd12，G的邊數(shù)m

6、=6mvdi2)(即性質(zhì)性質(zhì)1 1：在圖：在圖G=(V,E)G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)中，所有點(diǎn)的次之和是邊數(shù)m m的兩倍。的兩倍。證明：由于每條邊均與兩個(gè)頂點(diǎn)關(guān)聯(lián)，因此在計(jì)算頂點(diǎn)的次時(shí)每條邊都計(jì)算了兩遍，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的二倍。三三. .次（度）的性質(zhì)次（度）的性質(zhì)性質(zhì)性質(zhì)2 2：在任何圖：在任何圖G=(V,E)G=(V,E)中，中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)奇點(diǎn)的個(gè)數(shù)為偶數(shù)證明：設(shè)V1，V2分別是圖G中奇點(diǎn)和偶點(diǎn)的集合，則V1V2=V, V1V2=,有性質(zhì)1， ，因?yàn)閂2是偶點(diǎn)的集合，d(vi)(iV2)均為偶數(shù)，所以mvdvdvdViiViiVii2)()()(21為偶數(shù)所以

7、2)(Viivd為偶數(shù)1)(Viivd是奇點(diǎn)的集合而1,V均為奇數(shù))(,1Vivdi只有偶數(shù)個(gè)奇數(shù)相加才能得到偶數(shù)，所以V1中的點(diǎn)，即奇點(diǎn)的個(gè)數(shù)為偶數(shù)。四四. . 鏈、路、連通圖鏈、路、連通圖1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1.鏈：對于無向圖G=(V，E)，若圖G中有一個(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中

8、，連結(jié) vi0與vik的一條鏈，當(dāng)vi0與vik是同一個(gè)點(diǎn) 時(shí)，稱此鏈為圈。圈中只有重復(fù)點(diǎn)而無重復(fù)邊者為簡單圈， 既（除起點(diǎn)、終點(diǎn)重復(fù)外）無重復(fù)點(diǎn)也無重復(fù)邊者為初等圈,48176vevev不是鏈,17556vevev初等鏈evevevevev簡單鏈1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e為一個(gè)圈,5443322948175vevevevevevev為一個(gè)圈,544816655vevevevev（簡單圈）（初等圈）2 路路：在有向圖D=(V，A)中，若有從vi0到vik不考慮方向的鏈，且各邊方向一致，則稱之為從vi0到vik的一條路。 對于有向圖可以

9、類似于無向圖定義鏈和圈，初等鏈、圈，簡單鏈、圈此時(shí)不考慮邊的方向。而當(dāng)鏈(圈)上的邊方向相同時(shí)，稱為道路(回路)。對于無向圖來說，道路與鏈、回路與圈意義相同1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1v2v3v4v2e3e4e1e5v6e3 連通圖連通圖：一個(gè)圖中任意兩點(diǎn)間至少有一條鏈(或路)相連的圖。 連通圖非連通圖五網(wǎng)絡(luò) 在實(shí)際問題中，往往只用圖來描述所研究對象之間的關(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)圖)。如公路交通圖：vi表示城市,ei表示

10、公路w(ei)表示公路ei的長度如w(e2)=50表示城市v2與城市v3之間的距離是50千米1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e六. 完全圖、偶圖1完全圖： 一個(gè)簡單圖，若任意兩個(gè)頂點(diǎn)之間均有一條邊相連，則稱這樣的圖為完全圖。 對于完全圖，由于每個(gè)頂點(diǎn)與所有其余頂點(diǎn)都有一條邊相連，所以在有n個(gè)頂點(diǎn)的完全圖中，各個(gè)頂點(diǎn)的次均為（n-1）。2.偶圖：若圖G的頂點(diǎn)能分成兩個(gè)互不相交的非空集合V1和V2，使在同一集合中的任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為偶圖，也稱為二部圖。若偶圖的頂點(diǎn)集合V1，V2之間的每一對不同頂點(diǎn)都有一條邊相連，稱這樣的圖為完全偶圖。v2v3v4v5v2v

11、3v4v5v1v1完全圖(完全)偶圖定理定理 一個(gè)圖為偶圖的充分必要條件該圖無奇圈一個(gè)圖為偶圖的充分必要條件該圖無奇圈七.子圖、部分圖對于圖G1=V1,E1和圖G2=V2,E2,若有 ，稱G1是G2的一個(gè)子圖。若有 ，稱G1是G2的一個(gè)部分圖（生成子圖）。2121EEVV和2121EEVV和* 部分圖也是子圖，但子圖不一定是部分圖。生成子圖七.子圖、部分圖* 部分圖也是子圖，但子圖不一定是部分圖。生成子圖2121EEVV和2121EEVV和對于圖G1=V1,E1和圖G2=V2,E2,若有 ，稱G1是G2的一個(gè)子圖。若有 ，稱G1是G2的一個(gè)部分圖（生成子圖）。八.前向弧與后向弧設(shè)是一條從vs到

12、vt的鏈，則鏈上與鏈的方向一致的弧稱為前向弧，記這些弧為+；鏈上與鏈的方向相反的弧稱為后向弧，記這些弧為-。vsv1v2v3v4v5vt前向弧與后向弧|子圖子圖 設(shè)設(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)出子圖：導(dǎo)出子圖：如果 V2 V1 , E2 = vi , vj vi , vj V2 ，稱 G2 是 G1 中由V2 導(dǎo)出的導(dǎo)

13、出子圖。九、圖的矩陣表示 用矩陣表示圖對研究圖的性質(zhì)及應(yīng)用常常是比較方便的定義：網(wǎng)絡(luò)(賦權(quán)圖)G(V，E)，其邊(vi,vj)有權(quán)ij,構(gòu)造矩陣A=(aij)nn,其中：其它0E)v,v(ajiijij稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。例、寫出下圖的權(quán)矩陣v1v2v3v4v57654249380650760844580320430974290A定義：對于圖G(V，E)，|V|=n,構(gòu)造一個(gè)矩陣A=(aij)nn,其中：其它0E)v,v(1ajiij稱矩陣A為圖G的鄰接矩陣。例、寫出下圖的鄰接矩陣v1v3v5v2v4v6當(dāng)G為無向圖時(shí)，鄰接矩陣為對稱矩陣0100001010101000100100100

14、00100000110A654321vvvvvv654321vvvvvv|給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。|以各城鎮(zhèn)為圖以各城鎮(zhèn)為圖G 的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖圖G 相應(yīng)兩頂點(diǎn)間的邊，得圖相應(yīng)兩頂點(diǎn)間的邊，得圖G 。對。對G 的每一邊的每一邊e，賦以一個(gè)實(shí)數(shù)賦以一個(gè)實(shí)數(shù)w(e)直通鐵路的長度，稱為直通鐵路的長度，稱為e的權(quán)，的權(quán)，得到賦權(quán)圖得到賦權(quán)圖G 。G 的子圖的權(quán)是指子圖的各邊的的子圖的權(quán)是指子圖的各邊的權(quán)和。權(quán)和。|問題就

15、是求賦權(quán)圖問題就是求賦權(quán)圖G 中指定的兩個(gè)頂點(diǎn)中指定的兩個(gè)頂點(diǎn)u0 ,v0間的間的具最小權(quán)的軌。這條軌叫做具最小權(quán)的軌。這條軌叫做u0 ,v0間的最短路，它間的最短路，它的權(quán)叫做的權(quán)叫做u0 ,v0間的距離，亦記作間的距離，亦記作d(u0 ,v0)|基本思想 是按距 u 0從近到遠(yuǎn)為順序，依次求得u 0到G 的各頂點(diǎn)的最短路和距離，直至v 0 （或直至G 的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號算法。定義：連通且不含圈的無向圖稱為樹。記作T(V，E)二、二、 樹樹|樹可以有很多等價(jià)的定義,以下定理中的各命題都體現(xiàn)樹的特征.定理 設(shè)G=V,E是一無向圖，|V|=n，|

16、E|=m。則以下命題是等價(jià)的.(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連通，但刪去任何一邊后不再連通。 定理：無向圖G有生成樹當(dāng)且僅當(dāng)G連通。證明: 必要性顯然, 只證充分性。若G無圈，則G本身就是G的生成樹。若G有圈C，則在G中刪去C的一條邊，所得的圖是連通的，繼續(xù)這個(gè)過程，直到所得的圖T無圈為止，則T就是G的一棵生成樹。定義： 若圖G的生成子圖是一棵樹，則稱該樹為G的生成樹(支撐樹)?；蚝喎Q為圖G的樹(b)為(a)圖的生成樹最小生成樹的求法：避圈法與破圈法定

17、義： 樹的各條邊稱為樹枝。一般圖G的生成樹有多個(gè)，稱其中樹枝總長度最小的生成樹為最小樹。避圈法：在圖G中，每步選出一條邊e，使它與已選邊不構(gòu)成圈，且e是未選邊中長度最小的邊，直到選夠 n-1 邊為止。v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232破圈法：從網(wǎng)絡(luò)圖N中任取一回路，去掉該回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N1。在N1中再任取一回路，去掉該回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N2。如此繼續(xù)下

18、去，直到剩下的子圖中不再含回路為止。該子圖就是N的最小生成樹。v1v2v3v8v7v6v5v4v04112131444523552|欲修筑連接n個(gè)城市的鐵路，已知i城與j城之間的鐵路造價(jià)為wij，設(shè)計(jì)一個(gè)線路圖使總造價(jià)最低|連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具最小權(quán)的生 成樹叫做最小生成樹|造最小生成樹的兩種常用算法-prim 算法與Kruskal 算法。|設(shè)置兩個(gè)集合P 和Q,其中P 用于存放G 的最小生成樹中的頂點(diǎn)，集合Q存放G的最小生成樹中的邊。令集合P的初值為 1 P = v （假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn) v 1出發(fā)），集合Q的初值為Q = 。|prim算法

19、的思想是：從所有pP，vV P的邊 中 ，選取具有最小權(quán)值的邊pv ，將頂點(diǎn)v 加入集合P 中，將邊pv 加入集合Q中，如此不斷重復(fù)，直到P =V 時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合Q中包含了最小生成樹的所有邊。|定義 1： 經(jīng)過G 的每條邊的跡叫做G 的Euler 跡；閉的Euler 跡叫做Euler 回路或E回路；含Euler 回路的圖叫做Euler 圖。|直觀地講，Euler 圖就是從一頂點(diǎn)出發(fā)每邊恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的邊再回到出發(fā)點(diǎn)。|定理6 （i）G 是Euler 圖的充分必要條件是G 連通且每頂點(diǎn)皆偶次。|（ ii ） G 是Euler 圖的充分必要條件

20、是G 連通且|（iii）G 中有Euler 跡的充要條件是G 連通且至多有兩個(gè)奇次點(diǎn)。|定義 包含G 的每個(gè)頂點(diǎn)的軌叫做Hamilton(哈密頓)軌；閉的Hamilton 軌叫做Hamilton 圈或H 圈；含Hamilton 圈的圖叫做Hamilton 圖。|直觀地講，Hamilton 圖就是從一頂點(diǎn)出發(fā)每頂點(diǎn)恰通過一次能回到出發(fā)點(diǎn)的那種 圖，即不重復(fù)地行遍所有的頂點(diǎn)再回到出發(fā)點(diǎn)。|中國郵遞員問題 一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當(dāng)然他必須經(jīng)過他負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計(jì)一條投遞路線，使得他行程最短。|中國郵遞員問題的數(shù)學(xué)模型：在一個(gè)賦權(quán)連通圖上求一個(gè)含所有邊的回路，

21、且使此回路的權(quán)最小。|若此連通賦權(quán)圖是 Euler 圖，則可用Fleury 算法求Euler 回路，此回路即為所求。|對于非 Euler 圖，1973 年，Edmonds 和Johnson 給出下面的解法：|郵局有k(k 2)位投遞員，同時(shí)投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時(shí)間最早？我們把這一問題記成kPP。|kPP 的數(shù)學(xué)模型如下：|一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？|是在一個(gè)賦權(quán)完全圖中，找出一個(gè)有最小權(quán)的Hamilton 圈。稱這種圈為最

22、優(yōu)圈|與最短路問題及連線問題相反，目前還沒有求解與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個(gè)方法以旅行商問題的有效算法。所以希望有一個(gè)方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。獲得相當(dāng)好（但不一定最優(yōu)）的解。1957 年，貝爾熱(Berge)得到最大對集的充要條件：|定理2 M 是圖G 中的最大對集當(dāng)且僅當(dāng)G 中無M 可增廣軌。1935 年，霍爾(Hall)得到下面的許配定理：|定理 3 G 為二分圖， X 與Y 是頂點(diǎn)集的劃分，G 中存在把X 中頂點(diǎn)皆許配的對集的充要條件是，S X ，則| N(S) | S |，其中N(S)是S 中頂點(diǎn)的鄰集。|推論 1：若G

23、是k 次（k 0)正則2分圖，則G 有完美對集。|所謂 k 次正則圖，即每頂點(diǎn)皆k 度的圖。由此推論得出下面的婚配定理：|定理定理 4 每個(gè)姑娘都結(jié)識 k(k 1)位小伙子，每個(gè)小伙子都結(jié)識k 位姑娘，則每位姑娘都能和她認(rèn)識的一個(gè)小伙子結(jié)婚，并且每位小伙子也能和他認(rèn)識的一個(gè)姑娘結(jié)婚。|工作人員 x 1, x2 , , xn 去做n件工作y 1, y 2, , y n ，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？|這個(gè)問題的數(shù)學(xué)模型是： G 是二分圖，頂點(diǎn)集劃分為V (G) = X UY ，|X = x1, , x n ， Y = y1, , y

24、 n ，當(dāng)且僅當(dāng)x i適合做工作y j時(shí)，x i y j E(G) ，求G 中的最大對集。|1965 年埃德門茲(Edmonds)提出匈牙利算法。|匈牙利算法：|（i）從G 中任意取定一個(gè)初始對集M 。|（ii）若M 把X 中的頂點(diǎn)皆許配，停止，M 即完美對集；否則取X 中未被M 許|配的一頂點(diǎn)u，記S = u，T = 。|（iii）若N(S) = T ，停止，無完美對集；否則取yN(S) T 。|（iv）若y 是被M 許配的，設(shè)yzM ，S = S Uz，T = T Uy，轉(zhuǎn)（iii）；|否則，取可增廣軌P(u, y)，令M = (M E(P) U(E(P) M)，轉(zhuǎn)（ii）。|在人員分派問

25、題中，工作人員適合做的各項(xiàng)工作當(dāng)中，效益未必一致，我們需要制定一個(gè)分派方案，使公司總效益最大。|這 個(gè) 問 題 的 數(shù) 學(xué) 模 型 是 ： 在 人 員 分 派 問 題 的 模 型 中 ， 圖 G 的每邊加了權(quán)|w (x i ， y j ) 0 表示 x i干 y j工作的效益，求加權(quán)圖G 上的權(quán)最大的完美對集。|解決這個(gè)問題可以用庫恩曼克萊斯（Kuhn-Munkres）算法|定義 若映射l :V(G) R，滿足x X , yY ，l(x) + l( y) w(x, y)，|則稱 l 是二分圖G 的可行頂點(diǎn)標(biāo)號。|令El = xy | xy E(G),l(x) + l( y) =w(xy) ，稱

26、以 l E 為邊集的G 的生成子圖為相等子圖，記作G l 。|可行頂點(diǎn)標(biāo)號是存在的。例如定理5 G l的完美對集即為G 的權(quán)最大的完美對集。最短路問題 最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以便用這個(gè)模型如設(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)最小的路。即)v,v(ijjil)(L最小有些最短路問題是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有點(diǎn)的最短路，或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。下面介紹三種算法，可分別用

27、于求解這幾種最短路問題。使用條件網(wǎng)絡(luò)中所有的弧(邊)權(quán)均，即：0lij(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)號法?？捎脙煞N標(biāo)號：T標(biāo)號與P標(biāo)號，T標(biāo)號為試探性標(biāo)號，P為永久性標(biāo)號，給vi點(diǎn)一個(gè)P標(biāo)號時(shí)，表示從vs到點(diǎn)vi的最短路權(quán),vi點(diǎn)的標(biāo)號不再改變。給vi點(diǎn)一個(gè)T標(biāo)號時(shí)表示從vs到點(diǎn)vi的估計(jì)最短路權(quán)的

28、上界，是一種臨時(shí)標(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)號時(shí)，全部計(jì)算結(jié)束。對于有n個(gè)頂點(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(臨時(shí)性標(biāo)號從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。第二步：若vi為剛得到P標(biāo)號的點(diǎn)，考慮這樣的點(diǎn)vj：(vi,vj)屬于E，且vj為T標(biāo)號。對vj的T標(biāo)號進(jìn)行如下的更改：T(vj)=minT(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)臨時(shí)性標(biāo)號

29、T(vj)=+,vTmin)v(PiTvii標(biāo)號為當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號。若全部點(diǎn)均為P標(biāo)號則停止。否則用 代vi轉(zhuǎn)回第二步。iv例、用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)v2v7v5v411344452572v3v67v1(0)v2v7v5v411344452572v32v645(2)由于邊(v1,v2)、(v1,v3) 、(v1,v4)屬于E，且v2,v3,v4為T標(biāo)號，

30、所以修改這三個(gè)點(diǎn)的標(biāo)號：T(v2)=minT(v2),P(v1)+l12=min,0+4=4T(v3)=minT(v3),P(v1)+l13=min,0+2=2 T(v4)=minT(v4),P(v1)+l14=min,0+5=57(3) 比較所有T標(biāo)號，T(v3)最小，所以令P(v3)=2v1(0)v2v7v5v411344452572v3(2)v6457v1(0)v2v7v5v411344452572v3(2)v64497(4) v3為剛得到P標(biāo)號的點(diǎn)，考察邊(v3,v4),(v3,v6)的端點(diǎn)v4,v6。T(v4)=minT(v4),P(v3)+l34=min5,2+2=4T(v6)=m

31、inT(v6),P(v3)+l36=min,2+7=9(5) 比較所有T標(biāo)號，T(v2), T(v4)最小，所以令P(v2)=P(v4) =4v1(0)v2v7v5v411344452572v3(2)v6(4)(4)97(6) v2,v4為剛得到P標(biāo)號的點(diǎn),考察邊(v2,v5), ),(v4,v5),(v4,v6)的端點(diǎn)v5,v6。T(v5)=minT(v5),P(v4)+l45,P(v2)+l25=min,4+3,4+4=7T(v6)=minT(v6),P(v4)+l46=min9,4+4=8v1(0)v2v7v5v411344452572(4)(4)877v3(2)v6(7) 比較所有T標(biāo)

32、號，T(v5)所以令P(v5) =7v1(0)v2v7v5v411344452572(4)(4)(7)8v3(2)v6v1(0)v2v7v5v411344452572(4)(4)(7)148v3(2)v6(8) v5為剛得到P標(biāo)號的點(diǎn)，考察邊(v5,v6),(v5,v7)的端點(diǎn)v6,v7。T(v6)=minT(v6),P(v5)+l56=min8,7+1=8T(v7)=minT(v7),P(v5)+l57=min,7+7=1477(9) 比較所有T標(biāo)號，T(v6)最小，所以令P(v6)=8v1(0)v2v7v5v411344452572(4)(4)(7)14(8)v3(2)v6(10) v6為

33、剛得到P標(biāo)號的點(diǎn)，考察邊(v6,v7)的端點(diǎn)v7。T(v7)=minT(v7),P(v6)+l67=min14,8+5=13v1(0)v2v7v5v411344452572(4)(4)(7)13(8)v3(2)v677(11) 只有一個(gè)T標(biāo)號T(v7)，令P(v7) =13 ，停止。v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67計(jì)算結(jié)果見上圖，v1到v7的最短路為：76431vvvvv765431vvvvvv同時(shí)得到v1到其余各點(diǎn)的最短路* 這個(gè)算法只適用于全部權(quán)為非負(fù)情況如果某邊的權(quán)為負(fù)，算法失效。上面的例題是針對無向圖求最短路的問題，對有向

34、圖最短路的求法類似。下面以設(shè)備更新問題為例說明有向圖最短路的計(jì)算方法。例(設(shè)備更新問題)某企業(yè)在四年內(nèi)都要使用某種設(shè)備，在每年年初作出是購買新設(shè)備還是繼續(xù)使用舊設(shè)備的決策。若購買新設(shè)備就要支付購置費(fèi)；若繼續(xù)使用舊設(shè)備，則需支付維修費(fèi)用。這種設(shè)備在四年之內(nèi)每年年初的價(jià)格以及使用不同時(shí)間（年）的設(shè)備的維修費(fèi)用估計(jì)為：年份1234年初購價(jià)10111213維修費(fèi)用24714問題：制定一個(gè)四年之內(nèi)的設(shè)備更新計(jì)劃，使得四年之內(nèi)的設(shè)備購置費(fèi)和維修費(fèi)用之和最小?？梢杂们笞疃搪穯栴}的方法來解決總費(fèi)用最少的設(shè)備更新計(jì)劃問題。符號的含義：vi第i年年初購進(jìn)一臺新設(shè)備(v5表示第四年年底)弧(vi,vj)表示第i年年

35、初購進(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è)備更新計(jì)劃問題可以轉(zhuǎn)化最短路問題。此最短路問題如圖所示。圖中權(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, 其

36、余各點(diǎn)給以T標(biāo)號，T(vi)= +(1) (i=2,3,4,5)。（圖中( )內(nèi)的數(shù)表示P標(biāo)號； 內(nèi)的數(shù)表示T標(biāo)號）(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）A，且v2,v3, v4,v5為T標(biāo)號，所以修改這四個(gè)點(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(

37、3) 比較所有具有T標(biāo)號的點(diǎn)，把最小者改為P標(biāo)號。T(v2)最小，令P(v2)=12。 (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。 (6)考察點(diǎn)v3 T(v4) =min T

38、(v4), P(v3)+ 34= min23, 16+14=23 T(v5) =min T(v5), P(v3)+ 35= min36, 16+18=34(7) 所有T標(biāo)號中，T(v4)最小，令P(v4)=23(8)考察點(diǎn)v4 T(v5) =min T(v5), P(v4)+ 45= min34, 23+15=34(9)只有一個(gè)T標(biāo)號T(v5)，令P(v5)=34，計(jì)算結(jié)束。 由上可知：v1到v5的最短路為v1v3v5,長度為34。其含義為：最佳更新計(jì)劃為第一年年初購買新設(shè)備使用到第二年年底(第三年年初)，第三年年初再購買新設(shè)備使用到第四年年底，這個(gè)計(jì)劃使得總的支付最小，其值為34。v1v3v

39、2v7v5v4v617134452572練習(xí)、求下圖中任意兩點(diǎn)間的最短路40575014771034430215720241045240)0(DD例、某地7個(gè)村莊之間的現(xiàn)有交通道路如下圖所示，邊旁數(shù)字為各村莊之間道路的長度?，F(xiàn)要在某一村莊修建一所小學(xué)，該小學(xué)應(yīng)建在哪個(gè)村莊,可使離該村最遠(yuǎn)的村莊的學(xué)生所走的路程最少？7634422571243v1v2v3v4v5v6v7村莊間的道路交通圖該問題可分作兩步來考慮：1）求出任意兩個(gè)村莊之間的最短路長；2）找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn),大中取小即可。首先寫出權(quán)矩陣024620174102546202775034423037430)0(D用F

40、loyd算法求出任意兩點(diǎn)之間的最短路的長度023587102013658310254753205258655034754230310875430)7(D找出每一點(diǎn)到其余各點(diǎn)按照最短路線的最遠(yuǎn)點(diǎn)取這些最遠(yuǎn)距離中的最小者(小學(xué)應(yīng)建在v4村)108758710max作業(yè): P227 習(xí)題4.4最大流問題最大流問題是在一個(gè)給定網(wǎng)絡(luò)上求流量最大的可行流，即給一個(gè)網(wǎng)絡(luò)的每條弧規(guī)定一個(gè)流量的上界，求從點(diǎn)vs到vt的最大流。下圖是一個(gè)輸油管道網(wǎng)，vs為起點(diǎn)，vt為終點(diǎn)，v1v6為中轉(zhuǎn)站，弧旁的數(shù)表示該管道的最大輸油量。問題：如何安排，才能使從vs到vt的輸油量最大？oooooooovsvtv1v2v3v5v6

41、v44267434232211|最大流問題|1最大流問題的數(shù)學(xué)描述|1 .1網(wǎng)絡(luò)中的流定義 在以V 為節(jié)點(diǎn)集， A為弧集的有向圖G = (V, A)上定義如下的權(quán)函數(shù)：|（i）L : A R 為孤上的權(quán)函數(shù)，弧(i, j) A對應(yīng)的權(quán)L(i, j)記為 l ij ，稱為孤(i, j)的容量下界（lower bound）；|（ii）U : A R 為弧上的權(quán)函數(shù)，弧(i, j) A對應(yīng)的權(quán)U(i, j)記為u ij ，稱為孤(i, j)的容量上界，或直接稱為容量（capacity）；|（iii）D :V R為頂點(diǎn)上的權(quán)函數(shù)，節(jié)點(diǎn)iV 對應(yīng)的權(quán)D(i)記為d i ，稱為頂點(diǎn)i 的供需量（suppl

42、ydemand）；此時(shí)所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記為N = (V, A, L,U,D)。|由于我們只討論V, A為有限集合的情況，所以對于弧上的權(quán)函數(shù)L,U 和頂點(diǎn)上的權(quán)函數(shù)D ，可以直接用所有孤上對應(yīng)的權(quán)和頂點(diǎn)上的權(quán)組成的有限維向量表示，因此L,U,D 有時(shí)直接稱為權(quán)向量，或簡稱權(quán)。|由于給定有向圖G = (V, A)后，我們總是可以在它的弧集合和頂點(diǎn)集合上定義各種權(quán)函數(shù)，所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò)。|定義 對于流網(wǎng)絡(luò)N = (V, A,L,U,D)，其上的一個(gè)流（flow） f 是指從N 的弧集A到R 的一個(gè)函數(shù)，即對每條弧(i, j)賦予一個(gè)實(shí)數(shù)f ij （稱為弧(i, j)的流量

43、）。如果流 f 滿足 則稱 f 為可行流（feasible flow）。至少存在一個(gè)可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasible network）約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。 定義： 設(shè)有向連通圖G(V,E)，G的每條邊(vi,vj)上有非負(fù)數(shù)cij稱為邊的容量，僅有一個(gè)入次為0的點(diǎn)vs稱為發(fā)點(diǎn)(源)，一個(gè)出次為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,，稱集合ffij網(wǎng)絡(luò)G上的一個(gè)流。稱滿足下列條件的流f為可行流： (1)容量限制條件：對G中每條邊(vi,

44、vj)，有0fijcij (2)平衡條件：對中間點(diǎn)vi， (即中間點(diǎn)vi的物資的輸入量與輸出量相等) 對收、發(fā)點(diǎn)vs,vt,有 (即從vs點(diǎn)發(fā)出的物資總量等于vt點(diǎn)輸入的量。)W為網(wǎng)絡(luò)流的總流量。 kkijijffWffjjtisi可行流總是存在的，例如f0就是一個(gè)流量為0的可行流。最大流問題就是在容量網(wǎng)絡(luò)中，尋找流量最大的可行流。 一個(gè)流f=fij,當(dāng)fij=cij，則稱流f對邊(vi,vj)是飽和的，否則稱f對(vi,vj)不飽和。根據(jù)弧的流量是否為0，可把弧分為零流弧和非零流弧兩類。 最大流問題實(shí)際是個(gè)線性規(guī)劃問題，但是利用它與圖的緊密關(guān)系，能更為直觀簡便地求解。把網(wǎng)絡(luò)D=(V,E,C)

45、的點(diǎn)集V剖分為兩個(gè)非空集合Vs和Vt(即VsVt=，VsVt=V)，使vsVs, vtVt，把從Vs指向Vt的弧的全體稱為（分離vs和vt的）截集。稱截集中所有弧的容量之和為這個(gè)截集的容量（簡稱為截量）。分離vs和vt的截集往往不只一個(gè)，稱其中截量最小的為最小截集。 由截集的定義可知：截集是從vs到vt的必經(jīng)之路，無論去掉哪個(gè)截集，從vs到vt就不存在路了，因此任何一個(gè)可行流的流量不會超過任何一個(gè)截集的容量。因而若能找到一個(gè)可行流和一個(gè)截集，使得可行流的流量等于這個(gè)截集的容量，則該可行流一定是最大流，該截集一定是最小截集。 在上圖中，若令Vs=vs,v1,v6,Vt=v2,v3,v4,v5,

46、vt,則：截集為(vs,v5)(v1,v2),(v1,v5), (v6,v5) ,(v6,v4),截量為3+2+4+2+3=14；oooooooovsvtv1v2v3v5v6v44267434232211設(shè)是網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，沿此方向上的弧可分為兩類：一類是與鏈的方向一致的弧稱為正向弧，用+ 表示正向弧的全體，另一類是與鏈的方向相反的弧稱為反向弧，用- 表示反向弧的全體。在上圖中，在鏈=vs,v5,v6,v4,v3,vt中，+=(vs,v5),(v6,v4),( v3,vt),-=(v5,v6),(v4,v3)。增廣鏈：對于可行流f，是一條從vs到vt的一條鏈，

47、如果+中的弧均為非飽和弧，-中的弧均為非零流弧，則稱為從vs到vt的關(guān)于f 的增廣鏈。定理（最大流量最小截量定理）：在網(wǎng)絡(luò)N中，從vs到vt的最大流的流量等于分離vs到vt的最小截集的截量。計(jì)算網(wǎng)絡(luò)最大流的方法增廣鏈的實(shí)際意義在于沿著這條鏈存在增大輸送能力的潛力。如沿著增廣鏈1=vs,v2,v5,v4,v6,vt，凡是正向弧的流量都增加1，反向弧的流量都減少1（見上圖），結(jié)果整個(gè)網(wǎng)絡(luò)的流增加了1，即由6增加到7。用這種方法調(diào)整后的流仍為可行流。這樣就得到了一個(gè)尋找最大流的方法：從一個(gè)可行流開始，尋找關(guān)于這個(gè)可行流的增廣鏈，若增廣鏈存在，則可以經(jīng)過調(diào)整，得到一個(gè)新的可行流，其流量比調(diào)整前的可行流

48、大，重復(fù)這個(gè)過程，直到不存在增廣鏈時(shí)就得到了最大流。下面介紹計(jì)算網(wǎng)絡(luò)最大流的標(biāo)號算法標(biāo)號法是由 Ford 和Fulkerson 在1957 年提出的設(shè)已有一個(gè)可行流f(若網(wǎng)絡(luò)中沒有給出可行流,則可設(shè)f為零流)，標(biāo)號法可分為兩步：（一）標(biāo)號過程在這個(gè)過程中,網(wǎng)絡(luò)中的點(diǎn)或者是標(biāo)號點(diǎn)，或者是未標(biāo)號點(diǎn)。每個(gè)標(biāo)號點(diǎn)的標(biāo)號包含兩個(gè)部分：第一個(gè)標(biāo)號表明它的標(biāo)號是從哪一點(diǎn)得到的，以便找出增廣鏈；第二個(gè)標(biāo)號是為確定增廣鏈的調(diào)整量用的。(1) 給發(fā)點(diǎn)vs以標(biāo)號（0，+），第二個(gè)數(shù)值表示從上一標(biāo)號點(diǎn)到這個(gè)標(biāo)號點(diǎn)的最大允許調(diào)整量。vs為發(fā)點(diǎn)，不限允許調(diào)整量，故為+。最大流的一種算法標(biāo)號法(2) 選擇一個(gè)已標(biāo)號的點(diǎn)vi

49、,對于vi的所有未標(biāo)號的鄰點(diǎn)vj,按下列規(guī)則處理：若邊(vi,vj) E,且fij0,則令vj=minfji, vi,并給vj以標(biāo)號(-vi,vj)(3) 重復(fù)(2)直到收點(diǎn)vt被標(biāo)號或不再有點(diǎn)可標(biāo)號時(shí)為止。 若vt得到標(biāo)號，說明存在一條增廣鏈，轉(zhuǎn)(二)調(diào)整過程。若vt未得到標(biāo)號，標(biāo)號過程已無法進(jìn)行時(shí)，說明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)(一)。|。用標(biāo)號法尋求網(wǎng)絡(luò)中最大流

50、的基本思想是尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止。即首先給出一個(gè)初始流，這樣的流是存在的，例如零流。如果存在關(guān)于它的可增廣軌，那么調(diào)整該軌上每條弧上的流量，就可以得到新的流。對于新的流，如果仍存在可增廣軌，則用同樣的方法使流的值增大，繼續(xù)這個(gè)過程，直到網(wǎng)絡(luò)中不存在關(guān)于新得到流的可增廣軌為止，則該流就是所求的最大流。|A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。|B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。|這兩個(gè)過程的步驟分述如下例、用標(biāo)號法求下圖所示的網(wǎng)絡(luò)中從vs到vt的最大流量，圖中弧旁數(shù)值為容量cij (1) 圖中沒有給出初始可行流,可設(shè)零流為出初始可行流.如圖1。先給vs標(biāo)以

51、標(biāo)號（0，+）。(2) 檢查vs的鄰點(diǎn)v1,v2可知（vs,v1）E，且fs1=0cs1=10,令v1=min +,10-0 =10,給v1以標(biāo)號（vs,10）。用同樣的方法給v2以標(biāo)號（vs,14）。見圖2(3) 檢查v1的尚未標(biāo)號的鄰點(diǎn)v3,v4可知(v1,v3)E，且f13=0c13=10,令v3=minv1, 10-0=min10,10=10,給v3以標(biāo)號(v1,10), 用同樣的方法給v4以標(biāo)號(v1,10)。(4) 檢查v3的尚未標(biāo)號的鄰點(diǎn)v5,v6可知(v3,v5）E，且f35=0c35=4,令v5=minv3, 4-0=min10,4=4,給v5以標(biāo)號(v3,4), 對于v6，

52、由于(v6,v3)E，且f63=0，不滿足標(biāo)號條件。檢查v4的尚未標(biāo)號的鄰點(diǎn)vt可知(v4,vt)E，且f4t=0c4t=13,令vt=minv4, 13-0=min10,13=10,給vt以標(biāo)號(v4,10)。(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先給vs標(biāo)以標(biāo)號（0，+）。檢查vs的鄰

53、點(diǎn)v1,v2可知（vs,v1）E但fs1=10=cs1=10, 不滿足標(biāo)號條件。（vs,v2）E且fs2=0|M|(|M|表示集合M中邊的條數(shù))，則稱M為最大匹配。上例中的問題用圖的語言描述如下：用x1,x2,xn表示n個(gè)工人，y1,y2,ym表示m項(xiàng)工作，(xi,yj)表示工人xi能勝任工作yj。X=x1,x2,xn，Y=y1,y2,ym，得到一個(gè)二部圖G=(X,Y,E)。問題：在圖G中找一個(gè)邊集E的子集M，使得M中的任意兩條邊沒有公共端點(diǎn)，并且邊數(shù)盡可能的多，即最大匹配。.x1x2x3xny1y2y3ym令M) j , i (0M) j , i (1xij若邊若邊則最大匹配問題的線性規(guī)劃模

54、型為：E) j , i (10 xVi, 1x. t . sxmaxijE) j , i (ijE) j , i (ijij變量，為這里ij=1二、最優(yōu)匹配例4.15、現(xiàn)有4個(gè)工人，4臺不同的機(jī)床，由于工人對各臺機(jī)床的操作技術(shù)水平不同，每個(gè)工人在各臺機(jī)床上完成給定任務(wù)所需工時(shí)不同，其效率矩陣為：問題：哪個(gè)工人操作哪臺機(jī)床可使總工時(shí)最少？1351015151094927917131114W工 人機(jī) 床min z=s.t.n1in1jijijx10 xn,.,2,1j1xn,.,2,1i1xijn1iijn1jij或(2)匈牙利方法定理4.9：若矩陣W的元素可分成0與非0兩部分，則覆蓋0元素的直線

55、數(shù)等于位于不同行不同列的0元素的最大個(gè)數(shù)。 定理4.8： 如果從分配問題效率矩陣W=(ij) 的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui，從每一列分別減去(或加上)一個(gè)常數(shù)vj ，得到一個(gè)新效率矩陣B=(bij),其中bij= ij-ui-vj,則二者的最優(yōu)解等價(jià)。匈牙利方法：根據(jù)定理4.8的方法不斷變換效率矩陣W，使其產(chǎn)生盡可能多的0元素，并且始終保持所有元素非負(fù)，直到能從變換后的矩陣中找出位于不同行不同列的0元素為止，這些0元對應(yīng)的xij=1,其余元素對應(yīng)xij=0的方案為最優(yōu)解。下面以例4.15說明最優(yōu)匹配的匈牙利方法的應(yīng)用542111351015151094927917131114W

56、8051011650705762036000205105650105702031B1、變換效率矩陣2、在B1中尋找位于不同行、不同列的0元20510565010570203*1B1)檢查B1的每行(列)，從中找出未加標(biāo)記的0元最少的行(列)，在該行(列)用*標(biāo)出一個(gè)0元，若該行(列)有多個(gè)0元,則任意標(biāo)一個(gè)。2)把剛得到的0*所在的行、列中的其余0元?jiǎng)澣?，?表示。3)0*、0就是有標(biāo)記的0元，返1).反復(fù)進(jìn)行,直到所有0元都有標(biāo)記為止。這樣得到的0*元一定位于不同行、不同列。如果個(gè)數(shù)等于n,已符合最優(yōu)性條件,否則轉(zhuǎn)33、找出能覆蓋矩陣中所有0元的最少直線集合1)對沒有0*的行打；2)對已打的

57、行中所有0元所在的列打；3)再對打有的列中所有0*元所在的行打；4)重復(fù)2),3)直到得不出新的打的行、列為止；5)沒有打的行和打的列就是覆蓋所有0元的最少直線集合。20510565010570203*1B4、修改矩陣B11)在未被直線覆蓋的所有元素中找出最小元素；2)所有打的行都減去此最小元素，所有打的列都加上此最小元素。令這個(gè)新矩陣為B2，返回2。205105650105702031B10495750004603032B10495750004603032B*符合最優(yōu)條件，總工時(shí)29x1x2x3x4y1y2y3y411945工人機(jī)床一般的指派問題在實(shí)際應(yīng)用中，會遇到各種非標(biāo)準(zhǔn)形式的指派問題。

58、通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后再用匈牙利法求解1、最大化指派問題設(shè)最大化指派問題系數(shù)矩陣C(cij)nn。其中最大元素為m。令矩陣B(bij)nn=(m-cij)nn。則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解。9118713161491514210413152C7589302712126123114916111681671613161616141691615161416216101641613161516216B例 矩陣的最大元素為c33=16,取m=16,令2人數(shù)和事數(shù)不等的指派問題若人少事多，則添上一些虛擬的“人”。這些虛擬的“人”做各事

59、的費(fèi)用系數(shù)可取0、理解為這些費(fèi)用實(shí)際上不會發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的“事”被各人做的費(fèi)用系數(shù)同樣也取0。3一個(gè)人可做幾件事的指派問題若某個(gè)人可做幾件事，則可將該人化作相同的幾個(gè)“人”來接受指派。這幾個(gè)“人做同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。4某事一定不能由某人做的指派問題若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M。例、 某商業(yè)公司計(jì)劃開辦五家新商店。為了盡早建成營業(yè)：商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai(i1,2, ,5)對新商店Bj(j1,2,5)的建造費(fèi)用的報(bào)價(jià)(萬元)為cij(i，j1,2,5)，見下表。商業(yè)公司應(yīng)當(dāng)對5家建筑公司

60、怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最少?BjB1B2B3B4B5AiA14871512A279171410A3691287A46714610A56912106cij這是標(biāo)準(zhǔn)形式的指派問題為了保證工程質(zhì)量，經(jīng)研究決定舍棄建筑公司A1和A5，而讓技術(shù)力量較強(qiáng)的建筑公司A1、A2和A3來承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一家或二家商店。求使總費(fèi)用最少的指派方案。反映投標(biāo)費(fèi)用的系數(shù)矩陣為：BjB1B2B3B4B5AiA14871512A279171410A3691287cij由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司(Ai 和 ，i1，2，3)。這樣，