系統(tǒng)工程導(dǎo)論蔣珉東南大學(xué)自動(dòng)化學(xué)院本課程學(xué)學(xué)習(xí)要求求：掌握基本本理論；；熟悉基本本方法；；能聯(lián)系實(shí)實(shí)際，解解決問(wèn)題題。本課程學(xué)學(xué)習(xí)方法法及考核核：以課堂討討論、自自學(xué)為主主，教師師講授為為輔。考核成績(jī)績(jī)=大作作業(yè)成績(jī)績(jī)（60%，大作業(yè)業(yè)報(bào)告、、發(fā)言情情況）++平時(shí)作作業(yè)（10%）+開開卷考試試成績(jī)（（30%）第7章圖圖和和網(wǎng)絡(luò)優(yōu)優(yōu)化圖論廣泛泛地應(yīng)用用與物理理學(xué)、化化學(xué)、控控制論、、信息、、科學(xué)管管理、電電子計(jì)算算機(jī)等領(lǐng)領(lǐng)域。很很多實(shí)際際問(wèn)題可可以采用用圖論的的理論和和方法來(lái)來(lái)解決。。圖論的歷歷史最早早可以追追溯到1736年E.Euler（瑞士數(shù)數(shù)學(xué)家））解決著名名的哥尼尼斯堡七七橋問(wèn)題題。第7章圖圖和和網(wǎng)絡(luò)優(yōu)優(yōu)化原問(wèn)題：：能否走走過(guò)七座座橋，且且每座橋橋只走過(guò)過(guò)一次，，最后回回到出發(fā)發(fā)點(diǎn)？Euler解題的思思路：將將原問(wèn)題題化為一一筆畫問(wèn)問(wèn)題。圖圖中的每每個(gè)點(diǎn)都都只與奇奇數(shù)條線線相關(guān)聯(lián)聯(lián)，不可可能不重重復(fù)地一一筆畫成成。第7章圖圖和和網(wǎng)絡(luò)優(yōu)優(yōu)化第7章圖圖和和網(wǎng)絡(luò)優(yōu)優(yōu)化結(jié)論：哥哥尼斯堡堡七橋問(wèn)問(wèn)題不可可能有解解。第7章圖圖和網(wǎng)絡(luò)絡(luò)優(yōu)化許多工程程問(wèn)題可可以采用用圖來(lái)描描述，并并且可以以化為相相應(yīng)的優(yōu)優(yōu)化問(wèn)題題，最終終采用優(yōu)優(yōu)化算法法來(lái)加以以解決。。由于計(jì)計(jì)算機(jī)的的普及和和大量算算法的出出現(xiàn)，使使得圖論論方法的的應(yīng)用成成為了可可能。第7章圖圖和網(wǎng)絡(luò)絡(luò)優(yōu)化第1節(jié)圖的的概念圖：由點(diǎn)點(diǎn)和線組組成，可可以表示示對(duì)象之之間的相相互關(guān)系系。一、圖概概念的引引進(jìn)第1節(jié)圖的的概念例1十個(gè)城市市之間的的鐵路交交通圖。。反映了了這十個(gè)個(gè)城市之之間的鐵鐵路分布布情況。。點(diǎn)代表表城市，，點(diǎn)與點(diǎn)點(diǎn)之間的的連線代代表相鄰鄰兩個(gè)城城市之間間的鐵路路線。類似的問(wèn)問(wèn)題還有有電話線線分布圖圖、煤氣氣管道圖圖、航空空線路圖圖等。第1節(jié)圖的的概念例2球隊(duì)之間間比賽的的情況。。vi(i=1,…,5)表示五個(gè)個(gè)球隊(duì)。。如果某某兩個(gè)球球隊(duì)比賽賽過(guò)了，，則在這這兩個(gè)隊(duì)隊(duì)所相應(yīng)應(yīng)的點(diǎn)之之間聯(lián)一一條線，，這條線線不過(guò)其其它點(diǎn)。。第1節(jié)圖的的概念例3化學(xué)藥品品儲(chǔ)存問(wèn)問(wèn)題。某某些藥品品不能儲(chǔ)儲(chǔ)存在同同一個(gè)庫(kù)庫(kù)房里。。vi(i=1,…,8)表示八八種藥品品。若藥藥品vi和藥品vj不能儲(chǔ)存在同同一個(gè)庫(kù)庫(kù)房里，，則在它它們之間間聯(lián)一條條線。需需要解決決的問(wèn)題題是：至至少需要要幾個(gè)庫(kù)庫(kù)房，能能將儲(chǔ)存存這八種種藥品第1節(jié)圖的的概念圖是反映映對(duì)象之之間關(guān)系系的一種種工具，，是一種種數(shù)學(xué)抽抽象。通通常用點(diǎn)點(diǎn)代表研研究的對(duì)對(duì)象，用用點(diǎn)與點(diǎn)點(diǎn)之間的的連線表表示這兩兩個(gè)對(duì)象象之間有有特定的的關(guān)系。。注意：圖圖中點(diǎn)的的相對(duì)位位置如何何，點(diǎn)與與點(diǎn)之間間的連線線的長(zhǎng)短短曲直，，對(duì)于反反映對(duì)象象之間的的關(guān)系并并不重要要。第1節(jié)圖的的概念反映例2中球隊(duì)之之間的比比賽情況況的兩種種圖沒(méi)有有本質(zhì)上上的區(qū)別別。第1節(jié)圖的的概念例1～例3中涉及到到的對(duì)象象之間的的“關(guān)系系”具有有“對(duì)稱稱性”。。即：如如果甲與與乙有某某種關(guān)系系，則乙乙與甲也也有同樣樣的這種種關(guān)系。。在實(shí)際生生活中，，有許多多關(guān)系不不具有這這種對(duì)稱稱性。例例2中的比賽賽勝負(fù)情情況就不不能用簡(jiǎn)簡(jiǎn)單的連連線來(lái)表表示。為為了反映映這種關(guān)關(guān)系，可可以用一一條帶箭箭頭的連線表表示。第1節(jié)圖的的概念二、定義義圖：由一些些點(diǎn)及一一些點(diǎn)之之間的連連線（帶帶箭頭或或不帶箭箭頭）所所組成。。邊：兩點(diǎn)之之間的不不帶箭頭頭的連線線?；。簝牲c(diǎn)之之間的帶帶箭頭的的連線。。無(wú)向圖（簡(jiǎn)稱圖）：由點(diǎn)點(diǎn)及邊構(gòu)構(gòu)成的圖圖。有向圖：由點(diǎn)及及弧構(gòu)成成的圖。。第1節(jié)圖的的概念點(diǎn)用集合合V={v1,…,,vn}表示。聯(lián)結(jié)點(diǎn)vi和vj∈V的邊記為為[vi,vj](或[vj,vi]）。聯(lián)結(jié)點(diǎn)vi和vj∈V的弧記為為（vi,vj），方向向是從vi指向vj。無(wú)向圖記為G=(V,E)，V、E分別為G的點(diǎn)集合合和邊集集合。有向圖記為D=(V,A)，V、A分別為G的點(diǎn)集合合和弧集集合。第1節(jié)圖的的概念無(wú)向圖實(shí)實(shí)例第1節(jié)圖的的概念有向圖實(shí)實(shí)例第1節(jié)圖的的概念圖G或D中的點(diǎn)數(shù)數(shù)記為p(G)或p(D)，邊（弧?。?shù)記記為q(G)或q(D)。簡(jiǎn)記為為p或q。第1節(jié)圖的的概念三、術(shù)語(yǔ)語(yǔ)1、無(wú)向圖圖若，，則則稱u，v是e的端點(diǎn)，也稱u，v是相鄰的。稱e是點(diǎn)u（及點(diǎn)v）的關(guān)連邊。若圖G中，某個(gè)個(gè)邊e的兩個(gè)端端點(diǎn)相同同，則稱稱e是環(huán)；若兩個(gè)個(gè)點(diǎn)之間間有多于于一條的的邊，稱稱這些邊邊為多重邊。一個(gè)無(wú)環(huán)環(huán)，無(wú)多多重邊的的圖稱為為簡(jiǎn)單圖；一個(gè)無(wú)無(wú)環(huán)，但但允許有有多重邊邊的圖稱稱為多重圖。第1節(jié)圖的的概念以點(diǎn)v為端點(diǎn)的的邊的個(gè)個(gè)數(shù)稱為為v的次，記為或或。。注意：圖圖中環(huán)在在計(jì)算邊邊時(shí)記做做兩次。。稱次為1的點(diǎn)為懸掛點(diǎn)，懸掛點(diǎn)點(diǎn)的關(guān)連連邊稱為為懸掛邊，次為零的點(diǎn)稱稱為孤立點(diǎn)。第1節(jié)圖的的概念定理1圖中中，，所有點(diǎn)點(diǎn)的次之之和是邊邊數(shù)的兩兩倍，即即次為奇數(shù)數(shù)的點(diǎn)稱稱為奇點(diǎn)，否則稱稱為偶點(diǎn)。定理2任一圖中中，奇點(diǎn)點(diǎn)的個(gè)數(shù)數(shù)為偶數(shù)數(shù)。第1節(jié)圖的的概念給定一個(gè)個(gè)圖，，一一個(gè)點(diǎn)邊邊的交錯(cuò)錯(cuò)序列，，若若，，則稱為一一條聯(lián)結(jié)結(jié)和和的的鏈，記為，，有時(shí)稱點(diǎn)點(diǎn)為為鏈的的中間點(diǎn)。第1節(jié)圖的的概念鏈中中，若，，則則稱之為為一個(gè)圈，記為。。若若鏈中中，，點(diǎn)都都是不同同的，則則稱之為為初等鏈；若圈中中，點(diǎn)點(diǎn)都都是不不同的，，則稱之為初等圈；若鏈（（圈）中中含的邊邊均不相相同，則則稱之為簡(jiǎn)單(鏈)圈。除非特別別說(shuō)明，，鏈（圈圈）均指指初等鏈鏈（圈））。第1節(jié)圖的的概念是一條簡(jiǎn)簡(jiǎn)單鏈，，但不是是初等鏈鏈，是是一條初初等鏈。。該圖中中，不不存在聯(lián)聯(lián)結(jié)和和的的鏈。是是一個(gè)初初等圈，，是是簡(jiǎn)單單圈，但但不是初初等圈。。圖中，第1節(jié)圖的的概念圖G中，若任任何兩個(gè)個(gè)點(diǎn)之間間，至少少有一條條鏈，則則稱G是連通圖，否則稱稱為不連通圖圖。若G是不連通通圖，它它的每個(gè)個(gè)連通的的部分稱稱為G的一個(gè)連通分圖圖（簡(jiǎn)稱為為分圖）。第1節(jié)圖的的概念給定一個(gè)個(gè)圖，，如果果圖，，使及及，，則稱稱是是的的一一個(gè)支撐子圖圖。設(shè)，，用表表示從從圖G中去掉v及v的關(guān)聯(lián)邊邊后得到到的一個(gè)個(gè)圖。第1節(jié)圖的的概念2、有向圖圖設(shè)給定了了一個(gè)有有向圖，，從D中去掉所所有弧上上的箭頭頭，就得得到了一一個(gè)無(wú)向向圖，稱稱之為D的基礎(chǔ)圖，記之為為G(D)。給定D中的一條條弧，，稱稱u為a的始點(diǎn)，v為a的終點(diǎn)，稱弧a是從u指向v的。第1節(jié)圖的的概念設(shè)是是D中的點(diǎn)弧弧交錯(cuò)序序列，如如果該序序列在基基礎(chǔ)圖G(D)中所對(duì)應(yīng)應(yīng)的點(diǎn)邊邊序列是是一條鏈鏈，則稱稱該點(diǎn)弧弧交錯(cuò)序序列是D的一條鏈鏈。類似似定義圈圈和初等等鏈（圈圈）。如果是是D中的一條條鏈，并并且對(duì)，，均均有，，稱稱之為從到到的的一一條路。若路的的第一個(gè)個(gè)點(diǎn)和最最后一個(gè)個(gè)點(diǎn)相同同，則稱稱之為回路。類似定定義初等路（回路）。第1節(jié)圖圖的概念念是一個(gè)回回路；是是從到到的的路；；是是一條條鏈，但但不是路路。第7章圖圖和網(wǎng)絡(luò)絡(luò)優(yōu)化第2節(jié)樹樹2.1樹及其性性質(zhì)定義1一個(gè)無(wú)圈圈的連通通圖稱為為樹。樹是極其其簡(jiǎn)單然然而卻是是非常有有用的一一類圖。。2.1樹及其性性質(zhì)例4五個(gè)城市市之間架架設(shè)電話話線。要要求任何何兩個(gè)城城市都可可以相互互通話（（允許通通過(guò)其他他城市）），并且且電話線線的根數(shù)數(shù)最少。。用五個(gè)點(diǎn)點(diǎn)代代表表五個(gè)城城市。若若在某兩兩個(gè)城市市之間架架設(shè)電話話線，則則在相應(yīng)應(yīng)的兩個(gè)個(gè)點(diǎn)之間間連一條條邊。這這樣一個(gè)個(gè)電話線線網(wǎng)就可可以用一一個(gè)圖來(lái)來(lái)表示。。2.1樹及其性性質(zhì)為了使任任何兩個(gè)個(gè)城市都都可以通通話，這這樣的圖圖必須是是連通的的。如果圖中中有圈的的話，從從圈中去去掉任意意一條邊邊，剩下下的圖仍仍然是連連通的。。如此可可以省去去一條電電話線。。因此，，滿足要要求的電電話線網(wǎng)網(wǎng)必定是是樹（無(wú)無(wú)圈的連連通圖））。2.1樹及其性性質(zhì)例5某工廠的的組織結(jié)結(jié)構(gòu)可以以表示成成一個(gè)樹樹。2.1樹及其性性質(zhì)定理3設(shè)圖是是一一個(gè)樹，，，，則G中至少有有兩個(gè)懸懸掛點(diǎn)。。定理４圖是是一個(gè)個(gè)樹的充充分必要要條件是是G不含圈，，且恰有有條邊。定理５圖是是一個(gè)個(gè)樹的充充分必要要條件是是G是連通圖圖，并且且定理６圖G是一個(gè)樹樹的充分分必要條條件是任意兩個(gè)個(gè)頂點(diǎn)之之間恰有有一條鏈鏈。2.1樹及其性性質(zhì)推論１從從一個(gè)個(gè)樹中去去掉任意意一條邊邊，則余余下的圖圖是不連連通的。。即：在在點(diǎn)集合合相同的的所有圖圖中，樹樹是含邊邊樹最少少的連通通圖。推論２在在樹中中不相鄰鄰的兩個(gè)個(gè)點(diǎn)間添添上一條條邊，則則恰好得得到一個(gè)個(gè)圈。第2節(jié)樹樹2.2圖的支撐撐樹定義2設(shè)圖是是圖的的支撐子子圖，如如果圖是是一個(gè)個(gè)樹，則則稱T是G的一個(gè)支支撐樹。。2.2圖的支撐撐樹若圖是是圖的的一個(gè)支支撐樹，，則樹Ｔ中邊的個(gè)個(gè)樹是，，G中不屬于于樹T的邊數(shù)是是。。定理７圖G有支撐樹充充分必要要條件是是圖G是連通的的。利用定理理７充充分性的的證明過(guò)過(guò)程，可可以得到到一個(gè)尋尋求連通通圖的支支撐樹的的方法——“破圈法法”：任取一一個(gè)圈，，從圈中中去掉一一邊，對(duì)對(duì)余下的的圖重復(fù)復(fù)該步驟驟，直到到不含圈圈為止。。2.2圖的支撐撐樹例6在圖7-15中，用“破圈法”求出圖的的一個(gè)支撐樹。。2.2圖的支撐撐樹另外一種種尋求連連通圖的的支撐樹樹的方法法—“避圈法法”：在圖中中任取一一條邊，，找一一條與不不構(gòu)成成圈的邊邊，再再找一條條與不不構(gòu)構(gòu)成圈的的邊。。一般，，設(shè)已有有，，找找一條與與中中的的任何一一條邊不不構(gòu)成圈圈的邊。。重復(fù)復(fù)上述過(guò)過(guò)程，直直到不能能進(jìn)行為為止。2.2圖的支撐撐樹例7在圖7-16中，用““避圈法法”求出出圖的一一個(gè)支撐撐樹。2.2圖的支撐撐樹根據(jù)定理理４和定定理５可可知，在在“破圈圈法”中中去掉的的邊數(shù)必必是條條；；在“避避圈法””中取出出的邊數(shù)數(shù)必是條條。。第2節(jié)樹樹2.3最小支撐撐樹問(wèn)題定義３給定圖，，對(duì)圖圖G中的每一一條邊，，相應(yīng)地地有一個(gè)個(gè)數(shù)，，則稱這這樣的圖圖為賦權(quán)圖，稱為為邊上上的的權(quán)。這里所說(shuō)說(shuō)的“權(quán)權(quán)”是指指與邊有有關(guān)的數(shù)數(shù)量指標(biāo)標(biāo)?？梢砸愿鶕?jù)實(shí)實(shí)際問(wèn)題題，賦予予它不同同的含義義。賦權(quán)圖不不僅指出出了各個(gè)個(gè)點(diǎn)之間間的連結(jié)結(jié)關(guān)系，，而且同同時(shí)也表表示出各各點(diǎn)之間間的數(shù)量量關(guān)系。。所以，，賦權(quán)圖圖被廣泛泛地應(yīng)用用于解決決最優(yōu)化化問(wèn)題。。2.3最小支撐撐樹問(wèn)題題設(shè)有一個(gè)個(gè)連通圖圖，，每一邊邊，，有一一個(gè)非負(fù)負(fù)權(quán)

定義４如果圖是是圖G的一個(gè)支支撐樹，，稱中中所有邊邊的權(quán)之之和為支支撐樹T的權(quán)，記記為。。即即2.3最小支撐撐樹問(wèn)題題如果支撐撐樹的的權(quán)是是G的所有支撐樹的的權(quán)中最最小者，，則稱是是G的最小支撐撐樹（簡(jiǎn)稱最小樹）。即式中對(duì)G的所有支支撐樹T取最小。。最小支撐撐樹問(wèn)題題就是要要求給定定連通賦賦值權(quán)圖圖G的最小支支撐樹。。實(shí)際應(yīng)用用：城市市間交通通網(wǎng)的建建造問(wèn)題題。兩種求最最小樹的的方法：：“避避圈法””和“破破圈法””2.3最小支撐撐樹問(wèn)題題1、避圈法法開始選一一條權(quán)最最小的邊邊，以后后每一步步，總從從與已選選邊不構(gòu)構(gòu)成圈的的那些未未選邊中中，選一一條權(quán)最最小的。。在每一一步中，，如果有有兩條或或兩條以以上的邊邊都是權(quán)權(quán)最小的的邊，則則從中任任選一條條。2.3最小支撐撐樹問(wèn)題題算法步驟驟：第1步令令（（表表示空集集）；第2步選選一一條邊，，使是是使使不不含含圈的所所有邊中中權(quán)最小小的邊。。令，，如果這這樣的邊邊不存在在，則第3步把把換換成，，轉(zhuǎn)入入第2步。2.3最小支撐撐樹問(wèn)題題例8已知某工工廠內(nèi)聯(lián)聯(lián)結(jié)六個(gè)個(gè)車間的的道路網(wǎng)網(wǎng)及每條條道路的的長(zhǎng)，要要求沿道道路架設(shè)設(shè)六個(gè)車間間的電話話線網(wǎng)，，是電話話線的總總長(zhǎng)度最最小。2.3最小支撐撐樹問(wèn)題題2、破圈法法任取一個(gè)個(gè)圈，從從圈中去去掉權(quán)最最大的邊邊（如果果有兩條條或兩條條以上的的邊都是是權(quán)最大大的邊，，則任意意去掉其其中的一一條）。。在余下下的圖中中，重復(fù)復(fù)這個(gè)步步驟，直直到得到到一個(gè)不不含圈的的圖為止止。這時(shí)時(shí)的圖就就是最小小樹。2.3最小支撐撐樹問(wèn)題題例9用破圈法法求例8中的最小小支撐樹。。第7章圖圖和網(wǎng)絡(luò)絡(luò)優(yōu)化第3節(jié)最最短路問(wèn)問(wèn)題3.1引例例10如圖7-18所示的單單行線交交通網(wǎng)，，每弧旁旁的數(shù)字字表示通通過(guò)該單行線所所需的費(fèi)費(fèi)用。從從v1出發(fā)到v8，求使總總費(fèi)用為為最小的的旅行路路線。3.1引例顯然，從從v1到v8的旅行線線路很多多。不同同的路線線，所需需的總費(fèi)費(fèi)用是不不同的。。一條旅旅行線路路的總費(fèi)費(fèi)用就是是相應(yīng)的的從v1到v8的路中所所有弧旁旁數(shù)字之之和。注意：這這里所說(shuō)說(shuō)的路可可以不是是初等路路。3.1引例一般的最最短路問(wèn)問(wèn)題：給定一個(gè)個(gè)賦權(quán)有有向圖，，即給定定一個(gè)有有向圖D=(V,A),對(duì)每個(gè)弧弧a=(vi,vj),有權(quán)ω(a)=ωij。又給定定D中兩個(gè)頂頂點(diǎn)vs和vt。設(shè)P是D中從vs到vt的一條路路，定義義路P的權(quán)是P中所有弧弧的權(quán)之之和，記記為ω(P)。最短路問(wèn)問(wèn)題就是是要在所所有從vs到vt的路中，，找一條條權(quán)最小小的路，，即尋找找P0，使3.1引例上式中，，稱：：P0是從vs到vt的最短路；路P0的權(quán)為從從vs到vt的距離，記為d(vs,vt)。最短路問(wèn)問(wèn)題是網(wǎng)網(wǎng)絡(luò)理論論中應(yīng)用用最廣泛泛的問(wèn)題題之一。。許多優(yōu)優(yōu)化問(wèn)題題可以使使用這個(gè)個(gè)模型．．如設(shè)備備更新、、管道鋪鋪設(shè)、線線路安排排、廠區(qū)區(qū)布局等等。第3節(jié)最最短短路問(wèn)題題Dijkstra算法本算法由由Dijkstra于1959年提提出，可可用于求求解指定定兩點(diǎn)vs、vt間的最短短路，或或從指定定點(diǎn)vs到其余各各點(diǎn)的最最短路。。思路———若序列{vs,v1,…,vn-1,vn}是從vs到vn的最短路路，則{vs,v1,…,vn-1}必為從vs到vn-1的最短路路。適用范圍圍——有向圖中所有弧弧的權(quán)均均非負(fù)，，即：ωij≧0。3.2最短路算算法3.2最短路算算法Dijkstra算法的基基本步驟驟，采用用標(biāo)號(hào)法法。用兩種標(biāo)標(biāo)號(hào)：T標(biāo)號(hào)與P標(biāo)號(hào)，T標(biāo)號(hào)為試試探性標(biāo)標(biāo)號(hào)，P為永久性性標(biāo)號(hào)。。給vi點(diǎn)一個(gè)P標(biāo)號(hào)時(shí)，，表示從從vs到點(diǎn)vi的最短路路權(quán),vi點(diǎn)的標(biāo)號(hào)號(hào)不再改改變。給給vi點(diǎn)一個(gè)T標(biāo)號(hào)時(shí)，，表示從從vs到vi點(diǎn)的估計(jì)計(jì)最短路路權(quán)的上上界，是是一種臨臨時(shí)標(biāo)號(hào)號(hào)。凡沒(méi)沒(méi)有得到到P標(biāo)號(hào)的點(diǎn)點(diǎn)都有T標(biāo)號(hào)。3.2最短路算算法算法的每每一步都都把某一一點(diǎn)的T標(biāo)號(hào)改為為P標(biāo)號(hào)，當(dāng)當(dāng)終點(diǎn)vt得到P標(biāo)號(hào)時(shí)，，全部計(jì)計(jì)算結(jié)束束。對(duì)于于有n個(gè)頂點(diǎn)的的圖，最最多經(jīng)n-1步就可以以得到從從始點(diǎn)到到終點(diǎn)的的最短路路。標(biāo)號(hào)的意意義：①標(biāo)號(hào)P(永久性標(biāo)標(biāo)號(hào))—從始點(diǎn)到到該標(biāo)號(hào)號(hào)點(diǎn)的最最短路權(quán)權(quán)；②標(biāo)號(hào)T(臨時(shí)性標(biāo)標(biāo)號(hào))—從始點(diǎn)到到該標(biāo)號(hào)號(hào)點(diǎn)的最最短路權(quán)權(quán)上界。3.2最短路算算法計(jì)算步驟驟第1步給始點(diǎn)vs標(biāo)上永久久性標(biāo)號(hào)號(hào)P(vs)=0，其余各各點(diǎn)標(biāo)臨臨時(shí)性標(biāo)標(biāo)號(hào)T(vj)=+；第2步若vi為剛得到到P標(biāo)號(hào)的點(diǎn)點(diǎn)，考慮慮這樣的的點(diǎn)vj：(vi,vj)屬于D，且vj為T標(biāo)號(hào)。對(duì)對(duì)vj的T標(biāo)號(hào)進(jìn)行行如下的的更改：：T(vj)=min{{T(vj),P(vi)+ωij}3.2最短路算算法第3步比比較所有有具有T標(biāo)號(hào)的點(diǎn)點(diǎn)，把最最小者改改為P標(biāo)號(hào)，即即當(dāng)存在兩兩個(gè)以上上最小者者時(shí)，可可同時(shí)改改為P標(biāo)號(hào)。若若全部點(diǎn)點(diǎn)均為P標(biāo)號(hào)則停停止。否否則用代代vi轉(zhuǎn)回第二二步。3.2最短路算算法例用用Dijkstra算法求下下圖中v1到v7點(diǎn)的最短短路。???????v1v2v7v5v4171344452572v33.2最短路算算法圖中()內(nèi)的數(shù)表表示P標(biāo)號(hào)，[]內(nèi)的數(shù)表表示T標(biāo)號(hào)。???????v1(0)v2v7v5v411344452572v3[∞]v6[∞][∞][∞][∞][∞]7(1)首先給v1以P標(biāo)號(hào),P(v1)=0,,其余所有有點(diǎn)給T標(biāo)號(hào),T(vi)=+∞∞；3.2最短路算算法(2)由于弧(v1,v2)、(v1,v3)、(v1,v4)屬于D，且v2、v3、v4為T標(biāo)號(hào)，所所以修改改這三個(gè)個(gè)點(diǎn)的標(biāo)標(biāo)號(hào)：T(v2)=min{T(v2),P(v1)+ω12}=min{∞∞,0++4}==4T(v3)=min{T(v3),P(v1)+ω13}=min{∞∞,0++2}==2T(v4)=min{T(v4),P(v1)+ω14}=min{∞∞,0++5}==5???????v1(0)v2v7v5v411344452572v3[2]v6[4][5][∞][∞][∞]73.2最短路算算法(3)比較所有有T標(biāo)號(hào)，T(v3)最小，故故令令P(v3)=2???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算算法(4)v3為剛得到到P標(biāo)號(hào)的點(diǎn)點(diǎn)，考察察弧(v3,v4)，(v3,v6)的端點(diǎn)v4,v6T(v4)=min{T(v4),P(v3)+ω34}=min{5,2++2}==4T(v6)=min{T(v6),P(v3)+ω36}=min{∞∞,2++7}==9???????v1(0)v2v7v5v411344452572v3(2)v6[4][5][∞][∞][∞]73.2最短路算算法(5)比較所有有T標(biāo)號(hào)，T(v2),T(v4)最小，所所以令P(v2)=P(v4)=4???????v1(0)v2v7v5v411344452572v3(2)v6[4][4][9][∞][∞]73.2最短路算算法???????v1(0)v2v7v5v411344452572v3(2)v6(4)(4)[9][∞][∞]73.2最短路算算法(6)v2,v4為剛得到到P標(biāo)號(hào)的點(diǎn)點(diǎn),考察弧(v2,v5)，(v4,v5)，(v4,v6)的端點(diǎn)v5,v6T(v5)=min{T(v5),P(v4)+ω45,P(v2)+ω25}==min{{∞,4+3,,4+4}=7T(v6)=min{T(v6),P(v4)+ω46}=min{9,4++4}==8???????v1(0)v2v7v5v411344452572(4)(4)[8][7][∞]7v3(2)v63.2最短路算算法(7)比較所有有T標(biāo)號(hào)，T(v5)最小，所以令P(v5)=7???????v1(0)v2v7v5v411344452572(4)(4)(7)[∞][8]v3(2)v673.2最短路算算法???????v1(0)v2v7v5v411344452572(4)(4)(7)[14]][8]v3(2)v6(8)v5為剛得到到P標(biāo)號(hào)的點(diǎn)點(diǎn)，考察察弧(v5,v6)，(v5,v7)的端點(diǎn)v6,v7T(v6)=min{T(v6),P(v5)+ω56}=min{8,7++1}==8T(v7)=min{T(v7),P(v5)+ω57}=min{∞∞,7++7}==1473.2最短路算算法(9)比較所有有T標(biāo)號(hào)，T(v6)最小，所所以令P(v6)=8???????v1(0)v2v7v5v411344452572(4)(4)(7)[14]](8)v3(2)v673.2最短路算算法(10))v6為剛得到到P標(biāo)號(hào)的點(diǎn)點(diǎn)，考察察弧(v6,v7)的端點(diǎn)v7T(v7)=min{T(v7),P(v6)+ω67}=min{14,8+5}}=13???????v1(0)v2v7v5v411344452572(4)(4)(7)[13]](8)v3(2)v673.2最短路算算法(11))只有一個(gè)個(gè)T標(biāo)號(hào)T(v7)，令P(v7)=13，停止。。???????v1(0)v2v7v5v411344452572(4)(4)(7)(13))(8)v3(2)v67計(jì)算結(jié)果果見(jiàn)上圖圖，v1到v7的最短路路為：同時(shí)得到到v1到其余各各點(diǎn)的最最短路。。3.2最短路算算法例11用Dijkstra算法求圖圖7-19中v1到v8的最短路路。計(jì)算過(guò)程程略，v1到v8的最短路路為：3.2最短路算算法Dijkstra算法只適適用于全全部權(quán)為為非負(fù)情情況．如如果某弧弧的權(quán)為為負(fù)，算算法失效效。負(fù)權(quán)的情情況自學(xué)學(xué)討論。。第3節(jié)最最短路問(wèn)問(wèn)題最短路問(wèn)問(wèn)題是網(wǎng)網(wǎng)絡(luò)理論論中應(yīng)用用最廣泛泛的問(wèn)題題之一。。許多優(yōu)優(yōu)化問(wèn)題題可以使使用這個(gè)個(gè)模型．．如設(shè)備備更新、、管道鋪鋪設(shè)、線線路安排排、廠區(qū)區(qū)布局等等。3.3應(yīng)用舉例例3.3應(yīng)用舉例例例(設(shè)備更新新問(wèn)題)某企業(yè)在在四年內(nèi)內(nèi)都要使使用某種種設(shè)備，，在每年年年初作作出是購(gòu)購(gòu)買新設(shè)設(shè)備還是是繼續(xù)使使用舊設(shè)設(shè)備的決決策。若若購(gòu)買新新設(shè)備就就要支付付購(gòu)置費(fèi)費(fèi)；若繼繼續(xù)使用用舊設(shè)備備，則需需支付維維修費(fèi)用用。這種種設(shè)備在在四年之之內(nèi)每年年年初的的價(jià)格以以及使用用不同時(shí)時(shí)間（年年）的設(shè)設(shè)備的維維修費(fèi)用用估計(jì)為為：年份1234年初購(gòu)價(jià)10111213維修費(fèi)用247143.2應(yīng)用舉例例問(wèn)題：制制定一個(gè)個(gè)四年之之內(nèi)的設(shè)設(shè)備更新新計(jì)劃，，使得四四年之內(nèi)內(nèi)的設(shè)備備購(gòu)置費(fèi)費(fèi)和維修修費(fèi)用之之和最小小?？梢杂们笄笞疃搪仿穯?wèn)題的的方法來(lái)來(lái)解決總總費(fèi)用最最少的設(shè)設(shè)備更新新計(jì)劃問(wèn)問(wèn)題。3.3應(yīng)用舉例例符號(hào)的含含義：vi—第i年年初購(gòu)購(gòu)進(jìn)一臺(tái)臺(tái)新設(shè)備備(v5表示第四四年年底底)；弧(vi,vj)—第i年年初購(gòu)購(gòu)進(jìn)的設(shè)設(shè)備一直直使用到到第j年年初(即第j-1年年底)；弧(vi,vj)的權(quán)數(shù)—從第i年年初購(gòu)購(gòu)進(jìn)的設(shè)設(shè)備一直直使用到到第j年年初所所花費(fèi)的的購(gòu)置費(fèi)費(fèi)和維修修費(fèi)用的的總和。。3.3應(yīng)用舉例例如何制定定使得總總費(fèi)用最最少的設(shè)設(shè)備更新新計(jì)劃問(wèn)問(wèn)題可以以轉(zhuǎn)化最最短路問(wèn)問(wèn)題。此此最短路路問(wèn)題如如圖所示示。3.3應(yīng)用舉例例圖中權(quán)數(shù)數(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=153.3應(yīng)用舉例例如何制定定使得總總費(fèi)用最最少的設(shè)設(shè)備更新新計(jì)劃問(wèn)問(wèn)題可以以轉(zhuǎn)化最最短路問(wèn)問(wèn)題。此此最短路路問(wèn)題如如圖所示示。3.3應(yīng)用舉例例圖中權(quán)數(shù)數(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=153.3應(yīng)用舉例例用Dijkstra算法求v1到v5的最短路路。(1)給v1以P標(biāo)號(hào),P(v1)=0,,其余各點(diǎn)點(diǎn)給以T標(biāo)號(hào)T(vi)=++∞((i==2,3,4,,5)（圖中()內(nèi)的數(shù)表表示P標(biāo)號(hào)；[]內(nèi)的數(shù)表表示T標(biāo)號(hào)）3.3應(yīng)用舉例例(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）∈D，且v2,v3,v4,v5為T標(biāo)號(hào)，所所以修改改這四個(gè)個(gè)點(diǎn)的標(biāo)標(biāo)號(hà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}=373.3應(yīng)用舉例例(3)比較所有有具有T標(biāo)號(hào)的點(diǎn)點(diǎn)，把最最小者改改為P標(biāo)號(hào)。T(v2)最小，令令P(v2)=12。3.3應(yīng)用舉例例(4)v2為剛得到到P標(biāo)號(hào)的點(diǎn)點(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}==363.3應(yīng)用舉例例(5)比較所有有具有T標(biāo)號(hào)的點(diǎn)點(diǎn)，把最最小者改改為P標(biāo)號(hào)。T(v3)最小，令令P(v3)=16。3.3應(yīng)用舉例例(6)考察點(diǎn)v3T(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)號(hào)中，，T(v4)最小，令令P(v4)=233.3應(yīng)用舉例例(8)考察點(diǎn)v4T(v5)=min{{T(v5),P(v4)+45}=min{{34,,23+15}=34(9)只有一個(gè)個(gè)T標(biāo)號(hào)T(v5)，令P(v5)=34。計(jì)算結(jié)束束。由上可知知：v1到v5的最短路路為v1→v3→v5,長(zhǎng)度為34。其含義義為：最最佳更新新計(jì)劃為為第一年年年初購(gòu)購(gòu)買新設(shè)設(shè)備使用用到第二二年年底底(第三年年年初)，第三年年年初再再購(gòu)買新新設(shè)備使使用到第第四年年年底，這這個(gè)計(jì)劃劃使得總總的支付付最小，，其值為為34。3.3應(yīng)用舉例例例13(類似）自己完成成。第7章圖圖和網(wǎng)絡(luò)絡(luò)優(yōu)化最大流問(wèn)問(wèn)題是在在一個(gè)給給定網(wǎng)絡(luò)絡(luò)上求流流量最大大的可行行流，即即給一個(gè)個(gè)網(wǎng)絡(luò)的的每條弧弧規(guī)定一一個(gè)流量量的上界界，求從從點(diǎn)vs到vt的最大流流。第4節(jié)網(wǎng)網(wǎng)絡(luò)最大大流問(wèn)題題第4節(jié)網(wǎng)網(wǎng)絡(luò)最大大流問(wèn)題題下圖是一一個(gè)輸油油管道網(wǎng)網(wǎng)，vs為起點(diǎn)，，vt為終點(diǎn)，，v1~v6為中轉(zhuǎn)站站，弧旁旁的數(shù)表表示該管管道的最最大輸油油量。問(wèn)題：如如何安排排，才能能使從vs到vt的輸油量量最大？？第4節(jié)網(wǎng)網(wǎng)絡(luò)最大大流問(wèn)題題4.1基本概念念與基本本定理1、網(wǎng)絡(luò)與與流定義6給定有向向圖D=(V,A)，在V中指定一一點(diǎn)稱為為發(fā)點(diǎn)（記為vi），而另另一點(diǎn)稱稱為收點(diǎn)（記為vj），其余余的點(diǎn)為為中間點(diǎn)點(diǎn)。對(duì)于于每個(gè)弧弧(vi,vj)∈A，對(duì)應(yīng)有有一個(gè)c(vi,vj)≧0（簡(jiǎn)簡(jiǎn)寫為cij），稱為為弧的容容量。這這樣的D稱為一個(gè)個(gè)網(wǎng)絡(luò)，記為D=(V,A,C)4.1基本概念念與基本本定理所謂網(wǎng)絡(luò)絡(luò)上的流流，是指指定義在在弧集合合A上的一個(gè)個(gè)函數(shù)f={f(vi,vj)}，并稱f(vi,vj)為弧(vi,vj)上的流量（簡(jiǎn)記為為fij)。圖7-23和圖7-24給出了發(fā)發(fā)點(diǎn)、收收點(diǎn)、弧弧的容量量和弧的的流量的的例子。。4.1基本概念念與基本本定理2、可行流流與最大大流在運(yùn)輸網(wǎng)網(wǎng)絡(luò)的實(shí)實(shí)際問(wèn)題題中，對(duì)對(duì)流有兩兩個(gè)明顯顯的要求求：①每每個(gè)弧上上的流量量不能超超過(guò)該弧弧的最大大通行能能力（即即弧的容容量）；；②中間間點(diǎn)的流流量為零零。理由：對(duì)對(duì)于每一一個(gè)點(diǎn)，，運(yùn)出該該點(diǎn)的產(chǎn)產(chǎn)品總量量與運(yùn)出出該點(diǎn)的的產(chǎn)品總總量之差差為該點(diǎn)點(diǎn)的凈輸輸出量，，簡(jiǎn)稱為為該點(diǎn)的的流量；；中間點(diǎn)點(diǎn)只起轉(zhuǎn)轉(zhuǎn)運(yùn)作用用，其流流量為零零。易見(jiàn)，發(fā)發(fā)點(diǎn)的凈凈流出量量與收點(diǎn)點(diǎn)的凈流流入量相相等，也也就是該該方案的的總輸送送量。4.1基本概念念與基本本定理定義7滿足下述述條件的的流f稱為可行流：（1）容量限限制條件件：對(duì)每每一弧(vi,vj)∈A（2）平衡條條件：對(duì)于中間間點(diǎn)：流流入量等等于流出出量，即即對(duì)于每每個(gè)i(i≠s,t)，有4.1基本概念念與基本本定理對(duì)于發(fā)點(diǎn)點(diǎn)vs，記對(duì)于收點(diǎn)點(diǎn)vs，記式中v(f)稱為這個(gè)個(gè)可行流流的流量量，即發(fā)發(fā)點(diǎn)的凈凈輸出量量（或收收點(diǎn)的凈凈輸入量量）。4.1基本概念念與基本本定理最大流問(wèn)問(wèn)題就是求一一個(gè)流{fij}使其流量量v(f)達(dá)到最大大，并且且滿足：：4.1基本概念念與基本本定理最大流問(wèn)問(wèn)題是一一個(gè)特殊殊的求極極大值的的線性規(guī)規(guī)劃問(wèn)題題。利用用圖的特特點(diǎn)，可可以比采采用線性性規(guī)劃的的一般方方法更為直觀觀簡(jiǎn)便地地求解。4.1基本概念念與基本本定理3、增廣鏈若給定一一個(gè)可行行流f={fij}，把網(wǎng)絡(luò)絡(luò)中使fij=cij的弧稱為為飽和弧，使fij<cij的弧稱為為非飽和弧弧，使fij=0的弧稱為為零流弧，使fij>0的弧稱為為非零流弧弧。若μ是網(wǎng)絡(luò)中中聯(lián)結(jié)發(fā)發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈鏈,定義鏈的的方向是是從vs到vt,則鏈上上的弧被被分為兩兩類:一一類是弧弧的方向向與鏈的的方向一一致,稱為前向弧；另一類類弧與鏈鏈的方向向相反，，稱為后向弧。前向弧的的全體記記為μ＋；后向弧的的全體記記為μ－。4.1基本概念念與基本本定理定義8設(shè)f是一個(gè)可可行流，，μ是網(wǎng)絡(luò)中中聯(lián)結(jié)發(fā)發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈鏈。若μ滿足下列列條件，，稱之為為（關(guān)于于可行流流f的)增廣鏈。在弧(vi,vj)∈μ＋上，0≤fij<cij，即μ＋中每一弧弧是非飽飽和弧；；在弧(vi,vj)∈μ－上，0<fij≤cij，即μ－中每一弧弧是非零零和??；；4.1基本概念念與基本本定理4、截集與截截量設(shè)S,T∈V，S∩T=Φ，把始點(diǎn)點(diǎn)在S中、終點(diǎn)在T中的所有有弧構(gòu)成成的集合合，記為為(S,T)。定義9給定網(wǎng)絡(luò)絡(luò)D=(V,A,C)，若點(diǎn)集集V被剖分為為兩個(gè)非非空集合合V1和，，使，，則把把弧集稱稱為是是（分離離vs和vt的）截集。顯然，若若把某一一截集的的弧從網(wǎng)網(wǎng)絡(luò)中去去掉，則則從發(fā)點(diǎn)點(diǎn)到收點(diǎn)點(diǎn)便不存存在路。。所以，，截集是是從發(fā)點(diǎn)點(diǎn)到收點(diǎn)點(diǎn)的必經(jīng)經(jīng)之道。。4.1基本概念念與基本本定理定義10給定一截集。把截集中所有弧弧的容量量之和稱稱為這個(gè)個(gè)截集的的容量（（簡(jiǎn)稱為為截量），記為為，，即不難證明明，任何何一個(gè)可可行流的的流量v(f)都不會(huì)超超過(guò)任一一截集的的容量，，即4.1基本概念念與基本本定理由截集的的定義可可知：截截集是從從vs到vt的必經(jīng)之之路，無(wú)無(wú)論去掉掉哪個(gè)截截集，從從vs到vt就不存在在路了。。因此任任何一個(gè)個(gè)可行流流的流量量不會(huì)超超過(guò)任何何一個(gè)截截集的容容量。因因而若能能找到一一個(gè)可行行流和一一個(gè)截集集，使得得可行流流的流量量等于這這個(gè)截集集的容量量，則該該可行流流一定是是最大流流，該截截集一定定是最小小截集。。4.1基本概念念與基本本定理在上圖中中，若令令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。4.1基本概念念與基本本定理定理8可行流f*是最大流流，當(dāng)且且僅當(dāng)不不存在關(guān)關(guān)于f*的增廣鏈鏈。（證證明從略略）顯然，若若對(duì)于一一個(gè)可行行流f*，網(wǎng)絡(luò)中中有一個(gè)個(gè)截集，，使，，則f*必是最大大流，而而必必定定是D的所有截截集中，，容量最最小的一一個(gè)，即即最小截截集。4.1基本概念念與基本本定理若f*是最大流流，則網(wǎng)網(wǎng)絡(luò)中必必存在一一個(gè)截集集，，使最大流量量最小截截量定理理：任一網(wǎng)網(wǎng)絡(luò)D中，從vs到vt的最大流流等于分分離vs,vt的最小截截集容量量。定理8提供了尋尋求網(wǎng)絡(luò)絡(luò)中最大大流的一一個(gè)方法法。實(shí)際際計(jì)算時(shí)時(shí)，通常常采用標(biāo)標(biāo)號(hào)法。。第4節(jié)網(wǎng)網(wǎng)絡(luò)最大大流問(wèn)題題4.2尋求最大大流的標(biāo)標(biāo)號(hào)法設(shè)已有一一個(gè)可行行流f(若網(wǎng)絡(luò)絡(luò)中沒(méi)有有給出可可行流，，則可設(shè)設(shè)f為零流))，標(biāo)號(hào)號(hào)法可分分為兩步步進(jìn)行。。1、標(biāo)號(hào)過(guò)過(guò)程在這個(gè)過(guò)過(guò)程中,,網(wǎng)絡(luò)中中的點(diǎn)或或者是標(biāo)標(biāo)號(hào)點(diǎn)，，或者是是未標(biāo)號(hào)號(hào)點(diǎn)。每每個(gè)標(biāo)號(hào)號(hào)點(diǎn)的標(biāo)標(biāo)號(hào)包含含兩個(gè)部分分：第一個(gè)個(gè)標(biāo)號(hào)表表明它的的標(biāo)號(hào)是是從哪一一點(diǎn)得到到的，以以便找出出增廣鏈鏈；第二二個(gè)標(biāo)號(hào)號(hào)是為確確定增廣廣鏈的調(diào)調(diào)整量用的。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(1)給發(fā)點(diǎn)vs以標(biāo)號(hào)（（0，+∞），第二個(gè)數(shù)數(shù)值表示示從上一一標(biāo)號(hào)點(diǎn)點(diǎn)到這個(gè)個(gè)標(biāo)號(hào)點(diǎn)點(diǎn)的最大大允許調(diào)調(diào)整量。vs為發(fā)點(diǎn)，，不限允允許調(diào)整整量，故故為+∞。(2)選擇一個(gè)個(gè)已標(biāo)號(hào)號(hào)的點(diǎn)vi，對(duì)于vi的所有未未標(biāo)號(hào)的的鄰點(diǎn)vj，按下列列規(guī)則處處理：若在(vi,vj)上，fij<cij，則令l(vj)=min{l(vi),cij-fij}，并給vj以標(biāo)號(hào)(vi,l(vj))。若在(vj,vi)上，fji>0，則令l(vj)=min{{fji,l(vi)}，并給vj以標(biāo)號(hào)(-vi,l(vj))。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(3)重復(fù)(2)直到收點(diǎn)點(diǎn)vt被標(biāo)號(hào)或或不再有有點(diǎn)可標(biāo)標(biāo)號(hào)時(shí)為為止。若vt得到標(biāo)號(hào)號(hào)，說(shuō)明明存在一一條增廣廣鏈，轉(zhuǎn)轉(zhuǎn)入調(diào)整過(guò)程程。若vt未得到標(biāo)標(biāo)號(hào)，標(biāo)標(biāo)號(hào)過(guò)程程已無(wú)法法進(jìn)行時(shí)時(shí)，說(shuō)明明f已是最大大流。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法2、調(diào)整過(guò)程程(1)確定調(diào)整整量=l(vt)。(2)若vt的標(biāo)號(hào)為為(vj,l(vt))，則以fit+代替fit；若vt的標(biāo)號(hào)為為(-vj,l(vt))，則以fit-代替fit。(3)令vj代替vt，返回(2)；若vj=vs，則去掉掉所有標(biāo)標(biāo)號(hào)轉(zhuǎn)入入標(biāo)號(hào)過(guò)過(guò)程。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法例用用標(biāo)號(hào)法法求下圖圖所示的的網(wǎng)絡(luò)中中從vs到vt的最大流流量，圖圖中弧旁旁數(shù)值為為容量cij。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(1)圖中沒(méi)有有給出初初始可行行流，可可設(shè)零流流為出初初始可行行流（如如圖1所示）。。先給vs標(biāo)以標(biāo)號(hào)號(hào)(0,++∞)。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(2)檢查vs的鄰點(diǎn)v1,v2，可知在在弧(vs,v1)上，fs1=0<cs1=10。令l(v1)=min{++∞,,10--0}}=10，給v1以標(biāo)號(hào)(vs,10))。用同樣樣的方法法給v2以標(biāo)號(hào)(vs,14))。見(jiàn)圖2。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(3)檢查v1的尚未標(biāo)標(biāo)號(hào)的鄰鄰點(diǎn)v3,v4，可知在在弧(v1,v3)上，f13=0<c13=10。令l(v3)=min{l(v1),10-0}==min{10,10}=10，給v3以標(biāo)號(hào)(v1,10))。用同樣樣的方法法給v4以標(biāo)號(hào)(v1,10))。見(jiàn)圖3。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(4)檢查v3的尚未標(biāo)標(biāo)號(hào)的鄰鄰點(diǎn)v5,v6，可知在弧弧(v3,v5)上，f35=0<c35=4。令l(v5)=min{l(v3),4-0}}=min{{10,,4}==4，給v5以標(biāo)號(hào)(v3,4)。對(duì)于v6，由于f63=0，不滿足足標(biāo)號(hào)條條件。檢查v4的尚未標(biāo)標(biāo)號(hào)的鄰鄰點(diǎn)vt，f4t=0<c4t=13。令l(vt)=min{l(v4),13-0}=min{{10,,13}}=10,給vt以標(biāo)號(hào)(v4,10))。見(jiàn)圖4。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法4.2尋求最大大流的標(biāo)標(biāo)號(hào)法(5)由于vt已得到標(biāo)標(biāo)號(hào)，則則存在增增廣鏈，，標(biāo)號(hào)過(guò)過(guò)程結(jié)束束，轉(zhuǎn)入入調(diào)整過(guò)過(guò)程。令=l(vt)=10為調(diào)整量量，從vt開始，按按標(biāo)號(hào)(v4,10))找到v4并用f4t+10代替f4t；由標(biāo)號(hào)號(hào)(v1,10))找到v1并用f14+10代替f14；再由標(biāo)標(biāo)號(hào)(vs,10))找到vs，并用fs1+10代替fs1，調(diào)整過(guò)過(guò)程結(jié)束束。調(diào)整整后的可可行流見(jiàn)見(jiàn)圖5。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法去掉所有有標(biāo)號(hào)，，重新開開始標(biāo)號(hào)號(hào)過(guò)程。。圖54.2尋求最大大流的標(biāo)標(biāo)號(hào)法先給vs以標(biāo)號(hào)(0,++∞)。檢查vs的鄰點(diǎn)v1,v2，可知fs1=10==cs1=10,,不滿足標(biāo)標(biāo)號(hào)條件件；fs2=0<cs2=14。令l(v2)=min{+∞∞，14-0}==14，給v2以標(biāo)號(hào)(vs,14))。圖6用同樣的的方法可可得v6的標(biāo)號(hào)(v2,5)，vt的標(biāo)號(hào)(v6,5)。見(jiàn)圖6。(v6,5)4.2尋求最大大流的標(biāo)標(biāo)號(hào)法令=5為調(diào)整量量，從vt開始進(jìn)行行調(diào)整，，調(diào)整后后的可行行流見(jiàn)下下圖。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法去掉所有有標(biāo)號(hào)，，重新開開始標(biāo)號(hào)號(hào)過(guò)程。。(0.++∞)(vs,9)(v2,.5))(v3,5)(v3,4)不滿足標(biāo)標(biāo)號(hào)條件件（反向向零流弧?。?v4,3)4.2尋求最大大流的標(biāo)標(biāo)號(hào)法令=3為調(diào)整量量，從vt開始進(jìn)行行調(diào)整，，調(diào)整后后的可行行流見(jiàn)下下圖。4.2尋求最大大流的標(biāo)標(biāo)號(hào)法去掉所有有標(biāo)號(hào)，，重新開開始標(biāo)號(hào)號(hào)過(guò)程。。(0.++∞)(v2,.2))(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2尋求最大大流的標(biāo)標(biāo)號(hào)法令=2為調(diào)整量量，從vt開始進(jìn)行行調(diào)整，，調(diào)整后后的可行行流見(jiàn)下下圖。(0.++∞)(v2,.2))(v3,2)(v3,2)(v5,2)(vs,6)(v6,2)4.2尋求最大大流的標(biāo)標(biāo)號(hào)法去掉所有有標(biāo)號(hào)，，重新開開始標(biāo)號(hào)號(hào)過(guò)程。。(0.++∞)(vs,4)vt未得到標(biāo)標(biāo)號(hào)，但但標(biāo)號(hào)過(guò)過(guò)程已無(wú)無(wú)法進(jìn)行行,說(shuō)明已得得到最大大流.其值為20