運(yùn)籌學(xué)圖與網(wǎng)絡(luò)問題課件

第十一章圖與網(wǎng)絡(luò)模型

一、圖與網(wǎng)絡(luò)模型介紹二、最短路問題三、最小生成樹問題四、最大流問題第十一章圖與網(wǎng)絡(luò)模型一、圖與網(wǎng)絡(luò)模型介紹一、圖與網(wǎng)絡(luò)模型介紹

1、引例一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識、與孫也相互認(rèn)識；錢與孫相互認(rèn)識、孫與李相互認(rèn)識。他們與周都不認(rèn)識。如何清晰的表示這些人之間的關(guān)系呢？當(dāng)人數(shù)更多、人們間相互關(guān)系更復(fù)雜時(shí)，該怎樣描述人們間的關(guān)系？一、圖與網(wǎng)絡(luò)模型介紹1、引例一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識、與孫也相互認(rèn)識；錢與孫相互認(rèn)識、孫與李相互認(rèn)識。他們與周都不認(rèn)識。趙錢孫李周一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識趙錢孫李周吳陳如果我們將上面的例子中人們之間的關(guān)系由“相互認(rèn)識”改變成“認(rèn)識”，如趙和周之間的關(guān)系是，周認(rèn)識趙而趙不認(rèn)識周，這時(shí)我們?nèi)绾伪磉_(dá)人們之間的這種關(guān)系呢？趙錢孫李周吳陳如果我們將上面的例子中人們之間的關(guān)系由“相互認(rèn)用帶箭頭的線來表示人們之間的關(guān)系：趙孫周吳陳錢李用帶箭頭的線來表示人們之間的關(guān)系：趙孫周吳陳錢李一、圖與網(wǎng)絡(luò)模型介紹2、相關(guān)概念（1）點(diǎn)、邊、?。?）無向圖、有向圖（3）鏈、圈、連通圖（4）路、回路（5）權(quán)、網(wǎng)絡(luò)一、圖與網(wǎng)絡(luò)模型介紹2、相關(guān)概念點(diǎn)、邊、弧點(diǎn)——用于表示各種事物，一般用V表示一個(gè)圖中往往有多個(gè)點(diǎn)，一般用v1、v2、…表示。一個(gè)圖中所有的n個(gè)點(diǎn)構(gòu)成點(diǎn)集V={v1、v2、…、vn}邊——用于描述事物間關(guān)系的線，一般用E表示。一個(gè)圖中往往有多個(gè)邊，一般用e1、e2、…表示。一個(gè)圖中所有的n條邊構(gòu)成邊集E={e1、e2、…、en}弧——帶有箭頭的線，一般用A表示。一個(gè)圖中的n條弧，一般用a1、a2、…表示。一個(gè)圖中所有的n條邊構(gòu)成邊集A={a1、a2、…、an}點(diǎn)、邊、弧點(diǎn)——用于表示各種事物，一般用V表示無向圖、有向圖無向圖：由點(diǎn)和邊構(gòu)成的圖，簡稱“圖”，一般用G表示。G=（V，E），V是圖G的點(diǎn)集，E是圖G的邊集。有向圖：由點(diǎn)和弧構(gòu)成的圖，一般用D表示。D=（V，A），V是圖D的點(diǎn)集，A是圖D的弧集。無向圖、有向圖無向圖：由點(diǎn)和邊構(gòu)成的圖，簡稱“圖”，一般用G鏈、圈、連通圖鏈：對于無向圖G來說，如果存在一個(gè)點(diǎn)、邊交錯(cuò)序列（v1、e1、v2、e2、…、vn）,其中邊ei的起點(diǎn)是vi，終點(diǎn)是vi+1，即ei=（vi，vi+1），則稱這條點(diǎn)、邊交錯(cuò)序列為聯(lián)結(jié)v1，vn的鏈。圈：如果一條鏈（v1、e1、v2、e2、…、vn）中，v1=vn，則稱之為圈連通圖：對一個(gè)無向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則稱G為連通圖鏈、圈、連通圖鏈：對于無向圖G來說，如果存在一個(gè)點(diǎn)、邊交錯(cuò)序路、回路路：在有向圖D中，如果存在一個(gè)點(diǎn)、弧交錯(cuò)序列：（v1、a1、v2、a2、…、vn）,其中邊ai的起點(diǎn)是vi，終點(diǎn)是vi+1，即ai=（vi，vi+1），則稱這條點(diǎn)、弧交錯(cuò)序列為聯(lián)結(jié)v1，vn的一條路?；芈罚喝绻返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則稱這條路為回路。路、回路路：在有向圖D中，如果存在一個(gè)點(diǎn)、弧交錯(cuò)序列：（v權(quán)、網(wǎng)絡(luò)權(quán)：當(dāng)無向圖G的每一條邊（vi，vj），或有向圖D的每一條?。╲’i，vj’）上都相應(yīng)地有一個(gè)數(shù)來進(jìn)一步說明點(diǎn)與點(diǎn)之間的關(guān)系，那么這樣的數(shù)我們可以稱之為權(quán)，記為wij。給無向圖G或有向圖D添加權(quán)的過程，通常稱為賦權(quán)。網(wǎng)絡(luò)：我們稱賦了權(quán)的有向圖D為網(wǎng)絡(luò)。權(quán)、網(wǎng)絡(luò)權(quán)：當(dāng)無向圖G的每一條邊（vi，vj），或有向圖D二、最短路問題最短路問題是對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)vs到vt找到一條從vs到vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱為從vs到vt的最短路，這條路上所有弧的權(quán)數(shù)的總和被稱之為從vs到vt的距離。如下圖，找出從v1到v4的最短路v1v2v3v442159v2二、最短路問題最短路問題是對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)對下圖，找出從vs到vt的最短路161617171822222323303031414159vsv1v2v3v4vt對下圖，找出從vs到vt的最短路16161717182222例1求下圖中v1到v6的最短路有向圖D=（V，A），V={v1，v2，…，v6}A={(v1,v2)

，(v1,v4)，(v1,v3),(v2,v6),(v4,v2),(v4,v6),(v3,v5),(v3,v5),(v5,v4),(v5,v6)

}cij表示vi到vj的權(quán)v1v2v3v4v5v63252153571例1求下圖中v1到v6的最短路有向圖D=（V，A），v1例1求下圖中v1到v6的最短路v1到vt的最短路步驟：1、給起點(diǎn)v1標(biāo)號（0，s）2、確定已標(biāo)號點(diǎn)集I，未標(biāo)號點(diǎn)集J，找出弧集A={（vi,vj）|viI，vjJ}3、如果弧集A=空集，那么如果vt已標(biāo)號，則結(jié)束，如果vt未標(biāo)號則說明不存在從v1到vt的路。否則，如果弧集A≠空集，轉(zhuǎn)44、對A中的弧，計(jì)算sij=li+cij,從中找出值最小的弧，給此弧標(biāo)號為（sij，i）v1v2v3v4v5v63252153571雙標(biāo)號（sij，i）中sij表示由vi到vj的最短路長，i表示vi到vj的最短路上，此點(diǎn)前一個(gè)點(diǎn)的下角標(biāo)。例1求下圖中v1到v6的最短路v1到vt的最短路步驟：v例2電線公司準(zhǔn)備在甲乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短。兩地交通圖如下：v1v2v3v4v5v61510326245176v7（甲）（乙）例2電線公司準(zhǔn)備在甲乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)1、永久標(biāo)號：v1（0，s）K=12、I={v1}，J={v2,v3,v4,v5,v6,v7}，A={(v1,v2)，(v1,v3)}3、A≠?4、s12=l1+c12=0+15=15s13=l1+c13=0+10=10Minsij=s13,永久標(biāo)號：v3=（sij,i）=（10，1）v1v2v3v4v5v61510326245176v7（0，s）（10，1）1、永久標(biāo)號：v1（0，s）v1v2v3v4v5v6151s12=l1+c12=0+15=15K=22、I={v1,v3}，J={v2,v4,v5,v6,v7}，A={(v1,v2)，(v3,v2)，(v3,v5)}3、A≠?4、s32=l3+c32=10+3=13s35=l3+c35=10+5=15Minsij=s32,永久標(biāo)號：v2=（sij,i）=（13，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）s12=l1+c12=0+15=15v1v2v3v4v5v6s35=l3+c35=10+5=15K=32、I={v1,v2,v3}，J={v4,v5,v6,v7}，A={(v2,v7)，(v2,v4)，(v3,v5)}3、A≠?4、s27=l2+c27=13+17=30s24=l2+c24=13+6=19Minsij=s35,永久標(biāo)號：v5=（sij,i）=（15，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）s35=l3+c35=10+5=15v1v2v3v4v5v6s27=l2+c27=13+17=30s24=l2+c24=13+6=19K=42、I={v1,v2,v3,v5}，J={v4,v6,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v5,v6)}3、A≠?4、s54=l5+c54=15+4=19s56=l5+c56=15+2=17Minsij=s56,永久標(biāo)號：v6=（sij,i）=（17，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）s27=l2+c27=13+17=30v1v2v3v4v5vs27=30s24=19s54=19K=52、I={v1,v2,v3,v5,v6}，J={v4,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v6,v7)}3、A≠?4、s67=l6+c67=17+6=23Minsij=s24=s54,永久標(biāo)號：v4=（sij,i）=（19，2）或（19，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)s27=30s24=19s54=19v1vs27=30K=62、I={v1,v2,v3,v4,v5,v6}，J={v7}，A={(v2,v7)，(v4,v7)，(v6,v7)}3、A≠?4、s47=l4+c47=19+2=21s67=l6+c67=17+6=23Minsij=s47,永久標(biāo)號：v7=（sij,i）=（21，4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）s27=30v1v2v3v4v5v615103262V1到v7的最短路長為21，最短路徑是v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）v7→v4→v2→v7→v4→v5→v3→v1v3→v1V1到v7的最短路長為21，最短路徑是v1v2v3v4v5v三、最小生成樹問題幾個(gè)概念：樹：無圈的連通圖生成子圖：給定一個(gè)無向圖G=(V,E)，保留G中的所有點(diǎn)，刪掉部分G的邊，所得的新圖G’就是G的生成子圖。生成樹：如果圖G的生成子圖是一個(gè)樹，則稱這個(gè)生成子圖為生成樹。最小生成樹：在一個(gè)賦權(quán)的連通的無向圖中，找出一個(gè)生成樹，如果這個(gè)生成樹的所有邊的權(quán)數(shù)之和最小，那么這個(gè)樹就叫做最小生成樹。三、最小生成樹問題幾個(gè)概念：最小生成樹求解方法一：破圈法算法步驟：1、在給定的賦權(quán)連通圖上任找一圈2、在找到的圈中刪掉一條權(quán)數(shù)最大的邊3、如果余下的圖不含圈，則它們構(gòu)成最小生成樹。最小生成樹求解方法一：破圈法算法步驟：例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278最小生成樹如圖，總權(quán)數(shù)為19例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v最小生成樹求解方法一：避圈法算法步驟：1、另作一圖G’，繪制原圖G的所有頂點(diǎn)2、依次選取權(quán)數(shù)最小的邊3、若在圖G’中加入此邊后不會產(chǎn)生圈，則在圖G’中加入此邊。否則在剩下的邊中繼續(xù)選取。最小生成樹求解方法一：避圈法算法步驟：v1v2v6v7v5v4v3103345341278v1v2v6v7v5v4v3333127最小生成樹如圖，總權(quán)數(shù)為19v1v2v6v7v5v4v3103345341278v1v2四、最大流問題給了一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)表示容量。在不超過每條弧容量的前提下，求從發(fā)點(diǎn)到收點(diǎn)的最大流量。四、最大流問題給了一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)表示例6根據(jù)石油公司的管道網(wǎng)絡(luò)，確定從v1到v7的最大流。v1v2v6v7v5v4v366321223254例6根據(jù)石油公司的管道網(wǎng)絡(luò)，確定從v1到v7的最大流。vv1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→

（2，4）（2，0）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（0，2）（0，2）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（0，2）+2→（2，0）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）+2→（2，0）+3（3，0）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3（0，3）（0，2）+2→（2v1v2v6v7v5v4v3+2→（2，0）+3（3，0）+1（1，0）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3+2→（2，0）+3（3，0）五、最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條弧（vi，vj），除了給出了容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總費(fèi)送費(fèi)用最小。五、最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的例7由于輸油管道長短不一，所以例6中的每段管道除了有不同流量cij的限制外，還有不同的單位流量的費(fèi)用bij，我們對每段管道（vi，vj）都用（cij，bij）。使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從v1向v7運(yùn)送石油，怎樣才能運(yùn)送最多的石油，并使得總的運(yùn)送費(fèi)最??？v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）例7由于輸油管道長短不一，所以例6中的每段管道除了有不同v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）從發(fā)點(diǎn)到收點(diǎn)的增廣路首選總的單位費(fèi)用最小的路單位費(fèi)用：101費(fèi)用：1×10（5，3）（1，-3）（0，3）（1，-3）（3，4）（1，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（5，3）（3，2）（2，3）（0，3）（2，8）（3，4）（2，4）（0，-6）（1，-3）（0，-4）（0，-5）（0，-2）（1，-3）（0，-8）（0，-4）（0，-3）（0，-7）（1，-4）費(fèi)用：1×101單位費(fèi)用：11+2+2×11（3，3）（3，-3）（0，8）（2，-8）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（3，3）（3，2）（2，3）（0，3）（0，8）（3，4）（2，4）（0，-6）（3，-3）（0，-4）（0，-5）（0，-2）（1，-3）（2，-8）（0，-4）（0，-3）（0，-7）（1，-4）1+2費(fèi)用：1×10+2×11+2單位費(fèi)用：12+2×12（1，3）（5，-3）（1，2）（2，-2）（0，3）（2，-3）（1，4）（3，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（1，3）（1，2）（0，3）（0，3）（0，8）（1，4）（2，4）（0，-6）（5，-3）（0，-4）（0，-5）（2，-2）（1，-3）（2，-8）（0，-4）（2，-3）（0，-7）（3，-4）1+2+2費(fèi)用：1×10+2×11+2×12單位費(fèi)用：16+1+1×16（0，3）（6，-3）（0，2）（2，-2）（1，4）（1，-4）（4，7）（1，-7）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（4，7）（2，5）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（1，4）（0，-6）（6，-3）（0，-4）（0，-5）（3，-2）（1，-3）（2，-8）（1，-4）（2，-3）（1，-7）（3，-4）1+2+2+1費(fèi)用：1×10+2×11+2×12+1×16單位費(fèi)用：17+3+3×17（3，6）（3，-6）（0，4）（3，-4）（1，7）（4，-7）v1v2v6v7v5v4v3（6，6）（3，4）（4，7）（v1v2v6v7v5v4v3（3，6）（0，4）（1，7）（2，5）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（1，4）（3，-6）（6，-3）（3，-4）（0，-5）（3，-2）（1，-3）（2，-8）（1，-4）（2，-3）（4，-7）（3，-4）1+2+2+1+3費(fèi)用：1×10+2×11+2×12+1×16+3×17單位費(fèi)用：22+1+1×22（2，6）（4，-6）（1，5）（1，-5）（0，4）（2，-4）（0，7）（5，-7）v1v2v6v7v5v4v3（3，6）（0，4）（1，7）（v1v2v6v7v5v4v3（0，4）（0，3）（0，2）（0，3）（0，3）（0，8）（1，4）（6，-3）（3，-4）（3，-2）（1，-3）（2，-8）（2，-3）（3，-4）10費(fèi)用：1×10+2×11+2×12+1×16+3×17+1×22（2，6）（4，-6）（1，5）（1，-5）（0，4）（2，-4）（0，7）（5，-7）=145v1v2v6v7v5v4v3（0，4）（0，3）（0，2）（運(yùn)籌學(xué)圖與網(wǎng)絡(luò)問題課件第十一章圖與網(wǎng)絡(luò)模型

一、圖與網(wǎng)絡(luò)模型介紹二、最短路問題三、最小生成樹問題四、最大流問題第十一章圖與網(wǎng)絡(luò)模型一、圖與網(wǎng)絡(luò)模型介紹一、圖與網(wǎng)絡(luò)模型介紹

1、引例一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識、與孫也相互認(rèn)識；錢與孫相互認(rèn)識、孫與李相互認(rèn)識。他們與周都不認(rèn)識。如何清晰的表示這些人之間的關(guān)系呢？當(dāng)人數(shù)更多、人們間相互關(guān)系更復(fù)雜時(shí)，該怎樣描述人們間的關(guān)系？一、圖與網(wǎng)絡(luò)模型介紹1、引例一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識、與孫也相互認(rèn)識；錢與孫相互認(rèn)識、孫與李相互認(rèn)識。他們與周都不認(rèn)識。趙錢孫李周一群人之間存在錯(cuò)綜的關(guān)系：趙、錢、孫、李、周。趙與錢相互認(rèn)識趙錢孫李周吳陳如果我們將上面的例子中人們之間的關(guān)系由“相互認(rèn)識”改變成“認(rèn)識”，如趙和周之間的關(guān)系是，周認(rèn)識趙而趙不認(rèn)識周，這時(shí)我們?nèi)绾伪磉_(dá)人們之間的這種關(guān)系呢？趙錢孫李周吳陳如果我們將上面的例子中人們之間的關(guān)系由“相互認(rèn)用帶箭頭的線來表示人們之間的關(guān)系：趙孫周吳陳錢李用帶箭頭的線來表示人們之間的關(guān)系：趙孫周吳陳錢李一、圖與網(wǎng)絡(luò)模型介紹2、相關(guān)概念（1）點(diǎn)、邊、?。?）無向圖、有向圖（3）鏈、圈、連通圖（4）路、回路（5）權(quán)、網(wǎng)絡(luò)一、圖與網(wǎng)絡(luò)模型介紹2、相關(guān)概念點(diǎn)、邊、弧點(diǎn)——用于表示各種事物，一般用V表示一個(gè)圖中往往有多個(gè)點(diǎn)，一般用v1、v2、…表示。一個(gè)圖中所有的n個(gè)點(diǎn)構(gòu)成點(diǎn)集V={v1、v2、…、vn}邊——用于描述事物間關(guān)系的線，一般用E表示。一個(gè)圖中往往有多個(gè)邊，一般用e1、e2、…表示。一個(gè)圖中所有的n條邊構(gòu)成邊集E={e1、e2、…、en}弧——帶有箭頭的線，一般用A表示。一個(gè)圖中的n條弧，一般用a1、a2、…表示。一個(gè)圖中所有的n條邊構(gòu)成邊集A={a1、a2、…、an}點(diǎn)、邊、弧點(diǎn)——用于表示各種事物，一般用V表示無向圖、有向圖無向圖：由點(diǎn)和邊構(gòu)成的圖，簡稱“圖”，一般用G表示。G=（V，E），V是圖G的點(diǎn)集，E是圖G的邊集。有向圖：由點(diǎn)和弧構(gòu)成的圖，一般用D表示。D=（V，A），V是圖D的點(diǎn)集，A是圖D的弧集。無向圖、有向圖無向圖：由點(diǎn)和邊構(gòu)成的圖，簡稱“圖”，一般用G鏈、圈、連通圖鏈：對于無向圖G來說，如果存在一個(gè)點(diǎn)、邊交錯(cuò)序列（v1、e1、v2、e2、…、vn）,其中邊ei的起點(diǎn)是vi，終點(diǎn)是vi+1，即ei=（vi，vi+1），則稱這條點(diǎn)、邊交錯(cuò)序列為聯(lián)結(jié)v1，vn的鏈。圈：如果一條鏈（v1、e1、v2、e2、…、vn）中，v1=vn，則稱之為圈連通圖：對一個(gè)無向圖G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則稱G為連通圖鏈、圈、連通圖鏈：對于無向圖G來說，如果存在一個(gè)點(diǎn)、邊交錯(cuò)序路、回路路：在有向圖D中，如果存在一個(gè)點(diǎn)、弧交錯(cuò)序列：（v1、a1、v2、a2、…、vn）,其中邊ai的起點(diǎn)是vi，終點(diǎn)是vi+1，即ai=（vi，vi+1），則稱這條點(diǎn)、弧交錯(cuò)序列為聯(lián)結(jié)v1，vn的一條路?；芈罚喝绻返牡谝粋€(gè)點(diǎn)和最后一個(gè)點(diǎn)相同，則稱這條路為回路。路、回路路：在有向圖D中，如果存在一個(gè)點(diǎn)、弧交錯(cuò)序列：（v權(quán)、網(wǎng)絡(luò)權(quán)：當(dāng)無向圖G的每一條邊（vi，vj），或有向圖D的每一條?。╲’i，vj’）上都相應(yīng)地有一個(gè)數(shù)來進(jìn)一步說明點(diǎn)與點(diǎn)之間的關(guān)系，那么這樣的數(shù)我們可以稱之為權(quán)，記為wij。給無向圖G或有向圖D添加權(quán)的過程，通常稱為賦權(quán)。網(wǎng)絡(luò)：我們稱賦了權(quán)的有向圖D為網(wǎng)絡(luò)。權(quán)、網(wǎng)絡(luò)權(quán)：當(dāng)無向圖G的每一條邊（vi，vj），或有向圖D二、最短路問題最短路問題是對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)點(diǎn)vs到vt找到一條從vs到vt的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱為從vs到vt的最短路，這條路上所有弧的權(quán)數(shù)的總和被稱之為從vs到vt的距離。如下圖，找出從v1到v4的最短路v1v2v3v442159v2二、最短路問題最短路問題是對一個(gè)賦權(quán)的有向圖D中的指定的兩個(gè)對下圖，找出從vs到vt的最短路161617171822222323303031414159vsv1v2v3v4vt對下圖，找出從vs到vt的最短路16161717182222例1求下圖中v1到v6的最短路有向圖D=（V，A），V={v1，v2，…，v6}A={(v1,v2)

，(v1,v4)，(v1,v3),(v2,v6),(v4,v2),(v4,v6),(v3,v5),(v3,v5),(v5,v4),(v5,v6)

}cij表示vi到vj的權(quán)v1v2v3v4v5v63252153571例1求下圖中v1到v6的最短路有向圖D=（V，A），v1例1求下圖中v1到v6的最短路v1到vt的最短路步驟：1、給起點(diǎn)v1標(biāo)號（0，s）2、確定已標(biāo)號點(diǎn)集I，未標(biāo)號點(diǎn)集J，找出弧集A={（vi,vj）|viI，vjJ}3、如果弧集A=空集，那么如果vt已標(biāo)號，則結(jié)束，如果vt未標(biāo)號則說明不存在從v1到vt的路。否則，如果弧集A≠空集，轉(zhuǎn)44、對A中的弧，計(jì)算sij=li+cij,從中找出值最小的弧，給此弧標(biāo)號為（sij，i）v1v2v3v4v5v63252153571雙標(biāo)號（sij，i）中sij表示由vi到vj的最短路長，i表示vi到vj的最短路上，此點(diǎn)前一個(gè)點(diǎn)的下角標(biāo)。例1求下圖中v1到v6的最短路v1到vt的最短路步驟：v例2電線公司準(zhǔn)備在甲乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短。兩地交通圖如下：v1v2v3v4v5v61510326245176v7（甲）（乙）例2電線公司準(zhǔn)備在甲乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)1、永久標(biāo)號：v1（0，s）K=12、I={v1}，J={v2,v3,v4,v5,v6,v7}，A={(v1,v2)，(v1,v3)}3、A≠?4、s12=l1+c12=0+15=15s13=l1+c13=0+10=10Minsij=s13,永久標(biāo)號：v3=（sij,i）=（10，1）v1v2v3v4v5v61510326245176v7（0，s）（10，1）1、永久標(biāo)號：v1（0，s）v1v2v3v4v5v6151s12=l1+c12=0+15=15K=22、I={v1,v3}，J={v2,v4,v5,v6,v7}，A={(v1,v2)，(v3,v2)，(v3,v5)}3、A≠?4、s32=l3+c32=10+3=13s35=l3+c35=10+5=15Minsij=s32,永久標(biāo)號：v2=（sij,i）=（13，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）s12=l1+c12=0+15=15v1v2v3v4v5v6s35=l3+c35=10+5=15K=32、I={v1,v2,v3}，J={v4,v5,v6,v7}，A={(v2,v7)，(v2,v4)，(v3,v5)}3、A≠?4、s27=l2+c27=13+17=30s24=l2+c24=13+6=19Minsij=s35,永久標(biāo)號：v5=（sij,i）=（15，3）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）s35=l3+c35=10+5=15v1v2v3v4v5v6s27=l2+c27=13+17=30s24=l2+c24=13+6=19K=42、I={v1,v2,v3,v5}，J={v4,v6,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v5,v6)}3、A≠?4、s54=l5+c54=15+4=19s56=l5+c56=15+2=17Minsij=s56,永久標(biāo)號：v6=（sij,i）=（17，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）s27=l2+c27=13+17=30v1v2v3v4v5vs27=30s24=19s54=19K=52、I={v1,v2,v3,v5,v6}，J={v4,v7}，A={(v2,v7)，(v2,v4)，(v5,v4),(v6,v7)}3、A≠?4、s67=l6+c67=17+6=23Minsij=s24=s54,永久標(biāo)號：v4=（sij,i）=（19，2）或（19，5）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)s27=30s24=19s54=19v1vs27=30K=62、I={v1,v2,v3,v4,v5,v6}，J={v7}，A={(v2,v7)，(v4,v7)，(v6,v7)}3、A≠?4、s47=l4+c47=19+2=21s67=l6+c67=17+6=23Minsij=s47,永久標(biāo)號：v7=（sij,i）=（21，4）v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）s27=30v1v2v3v4v5v615103262V1到v7的最短路長為21，最短路徑是v1v2v3v4v5v61510326245176v7（0，s）（10，1）（13，3）（15，3）（17，5）（19，2）/(19，5)（21，4）v7→v4→v2→v7→v4→v5→v3→v1v3→v1V1到v7的最短路長為21，最短路徑是v1v2v3v4v5v三、最小生成樹問題幾個(gè)概念：樹：無圈的連通圖生成子圖：給定一個(gè)無向圖G=(V,E)，保留G中的所有點(diǎn)，刪掉部分G的邊，所得的新圖G’就是G的生成子圖。生成樹：如果圖G的生成子圖是一個(gè)樹，則稱這個(gè)生成子圖為生成樹。最小生成樹：在一個(gè)賦權(quán)的連通的無向圖中，找出一個(gè)生成樹，如果這個(gè)生成樹的所有邊的權(quán)數(shù)之和最小，那么這個(gè)樹就叫做最小生成樹。三、最小生成樹問題幾個(gè)概念：最小生成樹求解方法一：破圈法算法步驟：1、在給定的賦權(quán)連通圖上任找一圈2、在找到的圈中刪掉一條權(quán)數(shù)最大的邊3、如果余下的圖不含圈，則它們構(gòu)成最小生成樹。最小生成樹求解方法一：破圈法算法步驟：例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v4v3103345341278最小生成樹如圖，總權(quán)數(shù)為19例4用破圈法求解下圖的一個(gè)最小生成樹v1v2v6v7v5v最小生成樹求解方法一：避圈法算法步驟：1、另作一圖G’，繪制原圖G的所有頂點(diǎn)2、依次選取權(quán)數(shù)最小的邊3、若在圖G’中加入此邊后不會產(chǎn)生圈，則在圖G’中加入此邊。否則在剩下的邊中繼續(xù)選取。最小生成樹求解方法一：避圈法算法步驟：v1v2v6v7v5v4v3103345341278v1v2v6v7v5v4v3333127最小生成樹如圖，總權(quán)數(shù)為19v1v2v6v7v5v4v3103345341278v1v2四、最大流問題給了一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)表示容量。在不超過每條弧容量的前提下，求從發(fā)點(diǎn)到收點(diǎn)的最大流量。四、最大流問題給了一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的網(wǎng)絡(luò)，其每條弧的賦權(quán)表示例6根據(jù)石油公司的管道網(wǎng)絡(luò)，確定從v1到v7的最大流。v1v2v6v7v5v4v366321223254例6根據(jù)石油公司的管道網(wǎng)絡(luò)，確定從v1到v7的最大流。vv1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（0，2）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→

（2，4）（2，0）v1v2v6v7v5v4v3（0，6）（0，6）（0，3）（v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（0，2）（0，2）（0，3）（0，2）（0，5）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）v1v2v6v7v5v4v3（0，6）（0，3）（0，1）（v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（0，2）（0，2）（0，4）+2→（2，0）（2，4）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）v1v2v6v7v5v4v3（0，3）（0，1）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（0，2）+2→（2，0）+3（3，3）（3，0）（3，2）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）v1v2v6v7v5v4v3（0，3）（0，2）（0，2）（v1v2v6v7v5v4v3（0，3）（0，2）+2→（2，0）+3（3，0）+1（3，3）（1，0）（1，3）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3（0，3）（0，2）+2→（2v1v2v6v7v5v4v3+2→（2，0）+3（3，0）+1（1，0）+2（5，1）（2，0）（2，0）（5，0）+2（5，1）（2，1）（2，0）（3，1）v1v2v6v7v5v4v3+2→（2，0）+3（3，0）五、最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的網(wǎng)絡(luò)，對每一條?。╲i，vj），除了給出了容量cij外，還給出了這條弧的單位流量的費(fèi)用bij，要求一個(gè)最大流F，并使得總費(fèi)送費(fèi)用最小。五、最小費(fèi)用最大流問題最小費(fèi)用最大流問題：給了一個(gè)帶收發(fā)點(diǎn)的例7由于輸油管道長短不一，所以例6中的每段管道除了有不同流量cij的限制外，還有不同的單位流量的費(fèi)用bij，我們對每段管道（vi，vj）都用（cij，bij）。使用這個(gè)網(wǎng)絡(luò)系統(tǒng)從v1向v7運(yùn)送石油，怎樣才能運(yùn)送最多的石油，并使得總的運(yùn)送費(fèi)最?。縱1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）例7由于輸油管道長短不一，所以例6中的每段管道除了有不同v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（6，3）（3，2）（2，3）（1，3）（2，8）（4，4）（2，4）（0，-6）（0，-3）（0，-4）（0，-5）（0，-2）（0，-3）（0，-8）（0，-4）（0，-3）（0，-7）（0，-4）v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（v1v2v6v7v5v4v3（6，6）（3，4）（5，7）（2，5）（