第11章-圖與網(wǎng)絡(luò)

Chapter11：

圖與網(wǎng)絡(luò)模型圖與網(wǎng)絡(luò)模型11.1圖與網(wǎng)絡(luò)的根本概念11.2最短路問題11.3最小生成樹問題11.4最大流問題11.5最小費(fèi)用最大流問題近代圖論的歷史可追溯到18世紀(jì)的七橋問題—穿過K?nigsberg城的七座橋，要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋〞難題。Euler1736年證明了不可能存在這樣的路線。11.1圖的根本概念與模型K?nigsberg橋?qū)?yīng)的圖11.1圖與網(wǎng)絡(luò)的根本概念圖論：圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系※

圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)、以及哪些點(diǎn)之間有連線。例如：在一個(gè)人群中，對相互認(rèn)識這個(gè)關(guān)系我們可以用圖來表示一般情況下，圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e511.1圖與網(wǎng)絡(luò)的根本概念圖論：圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。一般情況以下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。圖的定義： 假設(shè)用點(diǎn)表示研究的對象，用邊表示這些對象之間的聯(lián)系，那么圖G可以定義為“點(diǎn)〞和“邊〞的集合，記作：其中:V——點(diǎn)集E——邊集※

圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。無向圖定義:圖中的點(diǎn)用v表示，邊用e表示。對每條邊可用它所連接的點(diǎn)表示，記作：e1=[v1,v1];e2=[v1,v2];v3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn)，關(guān)聯(lián)邊，相鄰假設(shè)有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。假設(shè)點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；假設(shè)邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。11.1圖與網(wǎng)絡(luò)的根本概念如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)如右圖中邊e1為環(huán)如果兩個(gè)點(diǎn)之間多于一條邊，稱為多重邊，如右圖中的e4和e5對無環(huán)、無多重邊的圖稱作簡單圖v3e7e4e8e5e6e1e2e3v1v2v4v5

環(huán)，多重邊，簡單圖11.1圖與網(wǎng)絡(luò)的根本概念與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次〔也叫做度〕，記作d(vi)右圖中d(v1)＝4，d(v3)=5，d(v5)=1次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個(gè)圖的次等于各點(diǎn)的次之和。

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)11.1圖與網(wǎng)絡(luò)的根本概念圖中某些點(diǎn)和邊的交替序列，假設(shè)其中各邊互不相同，且對任意vt-1和vt均相鄰，稱為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱作圈〔回路〕如果任意兩個(gè)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖11.1圖與網(wǎng)絡(luò)的根本概念鏈，圈〔回路〕，連通圖圖的根本概念與模型二部圖〔偶圖〕圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為偶圖。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖改畫為(c)時(shí)清楚看出。如果我們把上面例子中的“相互認(rèn)識〞關(guān)系改為“認(rèn)識〞的關(guān)系，那么只用兩點(diǎn)之間的連線就很難刻畫他們之間的關(guān)系了，這時(shí)我們引入一個(gè)帶箭頭的連線，稱為弧。相互認(rèn)識用兩條反向的弧表示。11.1圖與網(wǎng)絡(luò)的根本概念有向圖的定義： 圖D被定義為“點(diǎn)〞和“弧〞的集合，記作：其中:V——點(diǎn)集；A——弧集a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳無向圖G＝(V,E)，對G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，稱wij為邊(vi,vj)上的權(quán)，稱圖G為賦權(quán)圖賦權(quán)的有向圖D=(V,A)，指定一點(diǎn)為發(fā)點(diǎn)〔vs〕，指定另一點(diǎn)為收點(diǎn)〔vt〕，稱其它點(diǎn)為中間點(diǎn)，并把D中每一條弧的賦權(quán)數(shù)cij稱為弧(vi,vj)的容量，這樣的賦權(quán)有向圖D就稱為網(wǎng)絡(luò)①②③④⑤⑥910201571419256

賦權(quán)圖，網(wǎng)絡(luò)11.1圖與網(wǎng)絡(luò)的根本概念權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等圖的根本概念與模型

出次與入次

有向圖中，以vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用d+(vi)表示；以vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示d-(vi)；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次?！邢驁D中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。圖的根本概念與模型圖的模型應(yīng)用例11.1有甲,乙,丙,丁,戊,己6名運(yùn)發(fā)動報(bào)名參加A,B,C,D,E,F6個(gè)工程的比賽。下表中打√的是各運(yùn)發(fā)動報(bào)告參加的比賽工程。問6個(gè)工程的比賽順序應(yīng)如何安排，做到每名運(yùn)發(fā)動都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√圖的根本概念與模型解：用圖來建模。把比賽工程作為研究對象，用點(diǎn)表示。如果2個(gè)工程有同一名運(yùn)發(fā)動參加，在代表這兩個(gè)工程的點(diǎn)之間連一條線，可得以下圖。ABCDEF在圖中找到一個(gè)點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A圖的根本概念與模型 一個(gè)班級的學(xué)生共計(jì)選修A、B、C、D、E、F六門課程，其中一局部人同時(shí)選修D(zhuǎn)、C、A，一局部人同時(shí)選修B、C、F，一局部人同時(shí)選修B、E，還有一局部人同時(shí)選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。思考題圖的根本概念與模型AFEDCB圖的根本概念與模型AFEDCB圖的根本概念與模型思考題解答：

以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對應(yīng)課程允許連續(xù)考試，如C—E—A—F—D—B，就是一個(gè)符合要求的考試課程表。11.2最短路問題

有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。最短路問題對一個(gè)賦權(quán)的圖〔G或D〕中的指定的兩個(gè)點(diǎn)Vs和Vt找到一條從Vs到Vt的路，使得這條路上所有弧〔邊〕的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路Dijkstra算法(雙標(biāo)號法〕最短路問題求最短路有兩種算法:

狄克斯屈拉(Dijkstra)標(biāo)號算法

逐次逼近算法假設(shè)序列{vs,v1…..vn-1,vn}是從vs到vt間的最短路，那么序列{vs,v1…..vn-1}必為從vs到vn-1的最短路。 假定v1→v2→v3→v4是v1→v4的最短路，那么v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v511.2最短路問題Dijkstra標(biāo)號算法的根本思路(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v41.給出點(diǎn)Vs以標(biāo)號(0,s)2.找出已標(biāo)號的點(diǎn)的集合I，沒標(biāo)號的點(diǎn)的集合J，以及弧的集合3.如果B是空集，那么計(jì)算結(jié)束。①如果Vt已標(biāo)號(Lt,Kt)，那么Vs到Vt的距離為Lt，而從Vs到Vt的最短路徑，那么可以從Vt反向追蹤到起點(diǎn)Vs〔根據(jù)Kt的記錄〕而得到。②如果Vt未標(biāo)號，那么可以斷言不存在從Vs到Vt的路。11.2最短路問題Dijkstra雙標(biāo)號法的步驟：如果上述的弧(B)的集合不是空集，那么轉(zhuǎn)下一步。4.對B中的每一條弧，計(jì)算Sij=Li+Cij。在所有的Sij中，找到其值為最小的弧。不妨設(shè)此弧為〔Vc,Vd〕，那么給此弧的終點(diǎn)以雙標(biāo)號〔Scd,c〕，返回步驟2。11.2最短路問題Dijkstra雙標(biāo)號法的步驟：例1.求以下圖中v1到v6的最短路11.2最短路問題Dijkstra雙標(biāo)號法：v23527531512v1v6v5v3v4v23527531512v1v6v5v3v4〔0，s〕0+30+20+5〔2，1〕2+1〔3，1〕(3,3)3+73+5(8,4)v1到v6的最短距離為8；最短路為：v1→v3

→v4

→v6最短路問題求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是vs,終點(diǎn)是vt,以vi為起點(diǎn)vj為終點(diǎn)的弧記為(i,j)

距離為dijP標(biāo)號(點(diǎn)標(biāo)號)：b(j)—起點(diǎn)vs到點(diǎn)vj的最短路長；T標(biāo)號(邊標(biāo)號)：k(i,j)=b(i)+dij，步驟：1.令起點(diǎn)的標(biāo)號；b(s)＝0。2.找出所有vi已標(biāo)號vj未標(biāo)號的弧集合B={(i,j)}如果這樣的弧不存在或vt已標(biāo)號那么計(jì)算結(jié)束；3.計(jì)算集合B中弧k(i，j)=b(i)+dij的標(biāo)號4.選一個(gè)點(diǎn)標(biāo)號在終點(diǎn)vl處標(biāo)號b(l),返回到第2步。例2.求以下圖v1到v7的最短路線①②③④⑤⑥⑦862523534210570862254411147510711v7已標(biāo)號，計(jì)算結(jié)束。從v1到v7的最短路長是11,最短路線：v1→v4→v6

→v7P標(biāo)號T標(biāo)號11.2最短路問題12從上例知，只要某點(diǎn)已標(biāo)號，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號，說明vs不可達(dá)vj

。注：無向圖最短路的求法只將上述步驟中的弧改成邊即可。11.2最短路問題例3.求以下圖v1到各點(diǎn)的最短距離及最短路線。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點(diǎn)都已標(biāo)號，點(diǎn)上的標(biāo)號就是v1

到該點(diǎn)的最短距離，最短路線就是紅色的鏈。11.2最短路問題1.求從v1到v8的最短路徑23718456613410527593468211.2最短路問題237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到v8的最短路徑為v1→v4→v7→v5→v8，最短距離為1011.2最短路問題2.求以下圖中v1點(diǎn)到另外任意一點(diǎn)的最短路徑v1v2v3v4v6v532276213311.2最短路問題v1V2V3V4V6V532276213302471411.2最短路問題例4.電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？以下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度〔單位：公里〕。v1（甲地）1517624431065v2v7(乙地)v3v4v5v611.2最短路問題解：這是一個(gè)求無向圖的最短路的問題。v1（甲地）1517624431065v2v7(乙地)v3v4v5v611.2最短路問題(0,s)(10,1)(13,3)(14,3)(16,5)(18,5)(22,6)甲地到乙地的最短路為：例5.設(shè)備更新問題。某公司使用一臺設(shè)備，在每年年初，公司就要決定是購置新的設(shè)備還是繼續(xù)使用舊設(shè)備。如果購置新設(shè)備，就要支付一定的購置費(fèi)，當(dāng)然新設(shè)備的維修費(fèi)用就低。如果繼續(xù)使用舊設(shè)備，可以省去購置費(fèi)，但維修費(fèi)用就高了。請?jiān)O(shè)計(jì)一個(gè)五年之內(nèi)的更新設(shè)備的方案，使得五年內(nèi)購置費(fèi)用和維修費(fèi)用總的支付費(fèi)用最小?！睵237E3.zdl〕設(shè)備每年年初的價(jià)格表年份12345年初價(jià)格111112121311.2最短路問題設(shè)備維修費(fèi)如下表使用年數(shù)0-11-22-33-44-5每年維修費(fèi)用5681118解：將問題轉(zhuǎn)化為最短路問題，如以下圖：用vi表示“第i年年初購進(jìn)一臺新設(shè)備〞,弧〔vi,vj〕表示第i年年初購進(jìn)的設(shè)備一直使用到第j年年初。v1v2v3v4v5v611.2最短路問題把所有弧的權(quán)數(shù)計(jì)算如下表，把權(quán)數(shù)賦到圖中，再用Dijkstra算法求最短路。123456116223041592162230413172331417235186v1v2v3v4v5v616223041591622304131231718172311.2最短路問題年份12345年初價(jià)1111121213使用年數(shù)0-11-22-33-44-5每年維修費(fèi)5681118最終得到以下圖，可知，v1到v6的距離是53，最短路徑有兩條：v1→v3→v6和v1→v4→v6V1（0,s）v3v4(41,1)v5v62230415916(22,1)3041312317181723V2（16,1）16(30,1)(53,3)(53,4)11.2最短路問題樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖。在自然和社會領(lǐng)域應(yīng)用極為廣泛。乒乓球單打比賽抽簽后，可用圖來表示相遇情況，如以下圖所示。ABCDEFGH運(yùn)發(fā)動11.3最小生成樹問題某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長經(jīng)營副廠長開發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科銷售科檢驗(yàn)科動力科11.3最小生成樹問題性質(zhì)1：任何樹中必存在次為1的點(diǎn)。性質(zhì)2：n個(gè)頂點(diǎn)的樹必有n-1條邊。性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。v1v2v3v4v5v6

樹：無圈的連通圖即為樹11.3最小生成樹問題11.3最小生成樹問題圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)以下圖中，哪些是樹？圖G1={V1、E1}和圖G2={V2，E2}，如果有，稱G1是G2的一個(gè)子圖假設(shè)有，那么稱G1是G2的一個(gè)支撐子圖v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5(a)v3e7e4e8e6e2e3v1v2v4v5(b)〔G圖〕

子圖，支撐子圖11.3最小生成樹問題如果G2是G1的支撐圖〔生成圖〕，又是樹圖，那么稱G2是G1的生成樹〔或支撐樹〕。v1v2v3v4v5v1v2v3v4v5G1G211.3最小生成樹問題圖的生成樹〔支撐樹〕abcfedhgbfed11.3最小生成樹問題圖的生成樹〔支撐樹〕abcfedhgbfdg11.3最小生成樹問題圖的生成樹〔支撐樹〕bcedabcfedhg11.3最小生成樹問題圖的生成樹〔支撐樹〕abchabcfedhg11.3最小生成樹問題圖的生成樹〔支撐樹〕afdgabcfedhg11.3最小生成樹問題圖的生成樹〔支撐樹〕破圈法11.3最小生成樹問題

求支撐樹的方法：破圈法和避圈法生成樹〔支撐樹〕

求支撐樹的方法：破圈法和避圈法11.3最小生成樹問題v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5

求支撐樹的方法：破圈法和避圈法11.3最小生成樹問題避圈法最小生成樹問題：在一個(gè)賦權(quán)的、連通的、無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小11.3最小生成樹問題圖的最小生成樹〔支撐樹〕1.在給定的賦權(quán)的連通圖上任找一個(gè)圈2.在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊〔如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，那么任意去掉其中一條〕。3、如果所余下的圖已不包含圈，那么計(jì)算結(jié)束，所余下的圖即為最小生成樹，否那么返回第1步。求解最小生成樹的破圈算法v1v2v4v5v6435215878破圈法：任取一圈，去掉圈中最長邊，直到無圈。5v1v2v3v4v5v6843752618v3邊數(shù)＝n-1=511.3最小生成樹問題圖的最小生成樹〔支撐樹〕6v1v2v3v4v5v643521MinC(T)=1511.3最小生成樹問題圖的最小生成樹〔支撐樹〕樹與圖的最小樹避圈法: 去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。加邊的原那么為：從最短邊開始添加，加邊的過程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。5v1v2v3v4v5v6843752618樹與圖的最小樹v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹11.3最小生成樹問題v1v7v4v3v2v5v62015916253281741233611.3最小生成樹問題v1v7v4v3v2v5v620159162532817412311.3最小生成樹問題v1v7v4v3v2v5v620159162532817412311.3最小生成樹問題v1v7v4v3v2v5v6159162532817412311.3最小生成樹問題v1v7v4v3v2v5v6159162532817412311.3最小生成樹問題v1v7v4v3v2v5v69162532817412311.3最小生成樹問題v1v7v4v3v2v5v69162532817412311.3最小生成樹問題v1v7v4v3v2v5v692532817412311.3最小生成樹問題v1v7v4v3v2v5v692532817412311.3最小生成樹問題v1v7v4v3v2v5v6932817412311.3最小生成樹問題v1v7v4v3v2v5v6932817412311.3最小生成樹問題v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=5711.3最小生成樹問題樹與圖的最小樹練習(xí)：應(yīng)用避圈法求最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336樹與圖的最小樹v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57課堂練習(xí)：3749346321MinC(T)=12MinC(T)=15254173314475答案：11.3最小生成樹問題34122323242MinC(T)=12213638534567454321MinC(T)=1811.3最小生成樹問題例6.用破圈算法求圖〔a〕中的一個(gè)最小生成樹11.3最小生成樹問題v1331728541034v7v6v5v4v2v3(a)7v6v5v4v2v3(b)v133725434v7v6v5v4v2v31(c)v13372434v7v6v5v4v2v31(d)v4v1337234v7v6v5v2v31(e)v133723v7v6v5v4v2v31(f)例7.某大學(xué)準(zhǔn)備對其所屬的7個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如以下圖，圖中v1,…,v7表示7個(gè)學(xué)院辦公室，請?jiān)O(shè)計(jì)一個(gè)網(wǎng)絡(luò)能聯(lián)通7個(gè)學(xué)院辦公室，并使總的線路長度為最短(P242E5.treemin)。11.3最小生成樹問題v1331728541034v7v6v5v4v2v3圖11-14

此問題實(shí)際上是求圖11-14的最小生成樹，這在例6中已經(jīng)求得，即按照圖(f)的設(shè)計(jì)，可使此網(wǎng)絡(luò)的總的線路長度為最短，為19百米。網(wǎng)絡(luò)的最大流如何制定一個(gè)運(yùn)輸方案使生產(chǎn)地到銷售地的產(chǎn)品輸送量最大。這就是一個(gè)網(wǎng)絡(luò)最大流問題。網(wǎng)絡(luò)的最大流根本概念：1.容量網(wǎng)絡(luò)：對網(wǎng)絡(luò)上的每條弧(vi,vj)都給出一個(gè)最大的通過能力，稱為該弧的容量，簡記為cij。容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(也稱源點(diǎn)，記為s)和一個(gè)收點(diǎn)(也稱匯點(diǎn)，記為t)，網(wǎng)絡(luò)中其他點(diǎn)稱為中間點(diǎn)。s①②③④t4844122679網(wǎng)絡(luò)的最大流2.網(wǎng)絡(luò)的最大流

是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過的最大流量。3.流與可行流流是指加在網(wǎng)絡(luò)各條弧上的實(shí)際流量，對加在弧(vi,vj)上的負(fù)載量記為fij。假設(shè)fij=0，稱為零流。滿足以下條件的一組流稱為可行流。

容量限制條件。容量網(wǎng)絡(luò)上所有的弧滿足：0≤fij≤cij

中間點(diǎn)平衡條件。假設(shè)以v(f)表示網(wǎng)絡(luò)中從s→t的流量，那么有：網(wǎng)絡(luò)的最大流結(jié)論：任何網(wǎng)絡(luò)上一定存在可行流。〔零流即是可行流〕網(wǎng)絡(luò)最大流問題： 指滿足容量限制條件和中間點(diǎn)平衡的條件下，使v(f)值到達(dá)最大。v563522241263v1v2v7v4v3v6圖11-2611.4最大流問題最大流問題：給一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)稱之為容量，在不超過每條弧的容量的前提下，求出從發(fā)點(diǎn)到收點(diǎn)的最大流量。一、最大流的數(shù)學(xué)模型例8.某石油公司擁有一個(gè)管道網(wǎng)絡(luò)，使用這個(gè)網(wǎng)絡(luò)可以把石油從采地運(yùn)送到一些銷售點(diǎn)，這個(gè)網(wǎng)絡(luò)的一局部如以下圖所示。由于管道的直徑的變化，它的各段管道〔vi,vj〕的流量cij〔容量〕是不一樣的。cij的單位為萬加侖/小時(shí)。如果使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從采地v1向銷地v7運(yùn)送石油，問每小時(shí)能運(yùn)送多少加侖石油？(P243E6.maxflow)v563522241263v1v2v7v4v3v6圖11-2611.4最大流問題

我們可以為此例題建立線性規(guī)劃數(shù)學(xué)模型：設(shè)弧(vi,vj)上流量為fij，網(wǎng)絡(luò)上的總的流量為F，那么有(P243E6.maxfpow)：一、最大流的數(shù)學(xué)模型11.4最大流問題

1、在這個(gè)線性規(guī)劃模型中，其約束條件中的前6個(gè)方程表示了網(wǎng)絡(luò)中的流量必須滿足守恒條件：發(fā)點(diǎn)的流出量必須等于收點(diǎn)的總流入量；其余的點(diǎn)稱之為中間點(diǎn)，它的總流入量必須等于總流出量。2、對每一條弧(vi,vj)的流量fij要滿足流量的可行條件，應(yīng)小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我們把滿足守恒條件及流量可行條件的一組網(wǎng)絡(luò)流{fij}稱之為可行流，〔即線性規(guī)劃的可行解〕，可行流中一組流量最大〔也即發(fā)出點(diǎn)總流出量最大〕的稱之為最大流〔即線性規(guī)劃的最優(yōu)解〕。11.4最大流問題一、最大流的數(shù)學(xué)模型二、最大流問題的網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上弧的容量的表示作改進(jìn)。對一條弧〔vi,vj)的容量我們用一對數(shù)cij,0標(biāo)在弧〔vi,vj)上，cij靠近vi點(diǎn)，0靠近vj點(diǎn)，表示從vi到vj容許通過的容量為cij，而從vj到vi容許通過的容量為0，這樣我們可以省去弧的方向了。如以下圖:(a)和(b)、(c)和(d)的意義相同。vivjcij0（b）vivj（a）cijcijvivj（cji）（c）vivjcijcji（d）11.4最大流問題63522241263v1v2v5v7v4v3v60000000000011.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法用以上方法對例8的圖的容量標(biāo)號作改進(jìn)，得以下圖：〔1〕找出一條從發(fā)點(diǎn)到收點(diǎn)的路，在這條路上的每一條弧順流方向的容量都大于零。如果不存在這樣的路，那么已經(jīng)求得最大流?！?〕找出這條路上各條弧的最小的順流的容量pf，從而通過這條路增加網(wǎng)絡(luò)的流量pf?！?〕在這條路上，減少每一條弧的順流容量pf，同時(shí)增加這些弧的逆流容量pf，返回步驟〔1〕。****為了使算法更快捷有效，我們一般在步驟〔1〕中盡量選擇包含弧數(shù)最少的路。11.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法根本算法步驟：①第一次迭代：選擇路為v1→v4→v7?；　瞯4,v7〕的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如以下圖：63522241263v1v2v5v7v4v3v60000000000042022第一次迭代后的總流量211.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法用此方法對例8求解：②第二次迭代：選擇路為v1→v2→v5→v7。弧〔v2,v5〕的順流容量為3，決定了pf=3，改進(jìn)的網(wǎng)絡(luò)流量圖如以下圖：635222413v1v2v5v7v4v3v6000000004202203330355第二次迭代后的總流量11.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法③第三次迭代：選擇路為v1→v4→v6→v7?；　瞯4,v6〕的順流容量為1，決定了pf=1，改進(jìn)的網(wǎng)絡(luò)流量圖如以下圖：222413v1v2v5v7v4v3v600000042022033333013166第三次迭代后的總流量11.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法④第四次迭代：選擇路為v1→v4→v3→v6→v7?；　瞯3,v6〕的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如以下圖：22233v1v2v5v7v4v3v611000203203335031200213388第四次迭代后的總流量111.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法⑤第五次迭代：選擇路為v1→v2→v3→v5→v7。弧〔v2,v3〕的順流容量為2，決定了pf=2，改進(jìn)的網(wǎng)絡(luò)流量圖如以下圖：22v1v2v5v7v4v3v6101202033350120213315002020510第五次迭代后的總流量1011.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法經(jīng)過第五次迭代后在圖中已經(jīng)找不到從發(fā)點(diǎn)到收點(diǎn)的一條路——路上的每一條弧順流容量都大于零，運(yùn)算停止。得到最大流量為10。最大流量圖如以下圖：22v1v2v5v7v4v3v612352235511.4最大流問題二、最大流問題的網(wǎng)絡(luò)圖論解法11.5最小費(fèi)用最大流問題一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條弧〔vi,vj〕，除了給出容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總運(yùn)送費(fèi)用最小。(6,6)(3,4)(5,7)(2,5)(2,4)〔2,3〕(4,4)(1,3)(2,8)〔3,2〕v1v2v5v7v4v3v6(6,3)22v1v2v5v7v4v3v612352235511.5最小費(fèi)用最大流問題

例8最大流問題可能有多種解法，如：12v1v2v5v7v4v3v6123632345解1解2一、最小費(fèi)用最大流的數(shù)學(xué)模型例9.由于輸油管道的長短不一，所以在例6中每段管道〔vi,vj〕除了有不同的流量限制cij外，還有不同的單位流量的費(fèi)用bij，cij的單位為萬加侖/小時(shí)，bij的單位為百元/萬加侖。如以下圖所示。從采地v1向銷地v7運(yùn)送石油，怎樣運(yùn)送才能運(yùn)送最多的石油并使得總的運(yùn)送費(fèi)用最??？求出最大流量的最小費(fèi)用(P249E7.mcmf)。11.5最小費(fèi)用最大流問題(6,6)(3,4)(5,7)(2,5)(2,4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)

第1步，建立最大流的數(shù)學(xué)模型：一、最小費(fèi)用最大流的數(shù)學(xué)模型11.5最小費(fèi)用最大流問題

一、最小費(fèi)用最大流的數(shù)學(xué)模型11.5最小費(fèi)用最大流問題

第2步，建立求最小費(fèi)用的數(shù)學(xué)模型：一、最小費(fèi)用最大流的數(shù)學(xué)模型一般來說，所謂最小費(fèi)用流的問題就是：在給定了收點(diǎn)和發(fā)點(diǎn)并對每條弧(vi,vj)賦權(quán)以容量cij及單位費(fèi)用bij的網(wǎng)絡(luò)中，求一個(gè)給定流量f的最小費(fèi)用，這個(gè)給定流量f應(yīng)小于等于最大流量F，否那么無解。求最小費(fèi)用流的問題的線性規(guī)劃的模型只要把最小費(fèi)用最大流模型中的約束條件中的發(fā)點(diǎn)流量F改為f即可。11.5最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法對網(wǎng)絡(luò)上弧〔vi,vj〕的〔cij,bij〕的表示作如下改動11.5最小費(fèi)用最大流問題vivj（cij,bij）（0,-bij）（b）vivj（a）（cij,bij）（cij,bij）vivj（cji,bji）（c）（cij,bij）vivj（cji,bji）（0,-bij)（0,-bji)（d）11.5最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法用以上方法對例9的圖形進(jìn)行改進(jìn)，得以下圖：(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(4,4)(1,3)(2,8)（3,2）v1v2v5v7v4v3v6(6,3)(0,-3)(0,-8)(0,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(0,-4)（0,-3）圖11-2811.5最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法最小費(fèi)用最大流的根本算法：在對弧的標(biāo)號作了改進(jìn)的網(wǎng)絡(luò)圖上求最小費(fèi)用最大流的根本算法，與求最大流的算法根本一樣，不同的只是：****在步驟〔1〕中要選擇一條總的單位費(fèi)用最小的路，而不是包含邊數(shù)最小的路。用上述方法對例9求解：①第一次迭代：找到最短路v1

→v4

→v6

→v7。第一次迭代后總流量為1，決定了pf=1,總費(fèi)用為10。v5(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(2,8)（3,2）v1v2v7v4v3v6(5,3)(1,-3)(0,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-2911第一次迭代后的總流量11.5最小費(fèi)用最大流問題二、最小費(fèi)用最大流問題的網(wǎng)絡(luò)圖論解法②第二次迭代：找到最短路v1

→v4

→v7。第二次迭代后總流量為3，總費(fèi)用32。(6,6)(3,4)(5,7)(2,5)(0,-4)（2,3）(3,4)(0,3)(0,8)（3,2）v1v2v5v7v4v3v6(3,3)(3,-3)(2,-8)(1,-3)（0,-2）(0,-6)(0,-4)(0,-5)（2,4）(0,-7)(1,-4)（0,-3）圖11-3033第二次迭代后的總流量11.5最小費(fèi)用最大流問題