運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析

圖與網(wǎng)絡(luò)分析(GraphTheoryandNetworkAnalysis)圖與網(wǎng)絡(luò)的基本知識(shí)最短路問題樹及最小樹問題最大流問題1可編輯ppt哥尼斯堡七橋問題哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，Pregei河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們提出這樣的問題：有沒有辦法從某處（如A）出發(fā)，經(jīng)過各橋一次且僅一次最后回到原地呢？2可編輯pptBDACABCD哥尼斯堡七空橋一筆畫問題3可編輯ppt哈密爾頓（Hamilton）回路是十九世紀(jì)英國數(shù)學(xué)家哈密頓提出，給出一個(gè)正12面體圖形，共有20個(gè)頂點(diǎn)表示20個(gè)城市，要求從某個(gè)城市出發(fā)沿著棱線尋找一條經(jīng)過每個(gè)城市一次而且僅一次，最后回到原處的周游世界線路（并不要求經(jīng)過每條邊）。4可編輯ppt5可編輯ppt6可編輯ppt7可編輯ppt8可編輯ppt9可編輯ppt10可編輯ppt11可編輯ppt12可編輯ppt13可編輯ppt14可編輯ppt15可編輯ppt16可編輯ppt17可編輯ppt18可編輯ppt19可編輯ppt20可編輯ppt21可編輯ppt有7個(gè)人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問不同的就座方案共有多少種？用頂點(diǎn)表示人，用邊表示兩者相鄰，因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰，所以任何兩點(diǎn)都可以有邊相連。22可編輯ppt123764523可編輯ppt123764524可編輯ppt123764525可編輯ppt123764526可編輯ppt123764527可編輯ppt123764528可編輯ppt123764529可編輯ppt123764530可編輯ppt得到第一次就座方案是（1，2，3，4，5，6，7，1），繼續(xù)尋求第二次就座方案時(shí)就不允許這些頂點(diǎn)之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。31可編輯ppt123764532可編輯ppt123764533可編輯ppt123764534可編輯ppt123764535可編輯ppt123764536可編輯ppt123764537可編輯ppt123764538可編輯ppt123764539可編輯ppt得出第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊。40可編輯ppt123764541可編輯ppt123764542可編輯ppt123764543可編輯ppt123764544可編輯ppt123764545可編輯ppt123764546可編輯ppt123764547可編輯ppt123764548可編輯ppt得到第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點(diǎn)孤立點(diǎn)，所以該問題只有三個(gè)就座方案。49可編輯ppt123764550可編輯ppt引論圖的用處某公司的組織機(jī)構(gòu)設(shè)置圖總公司分公司工廠或辦事處51可編輯ppt一、圖與網(wǎng)絡(luò)的基本知識(shí)（一）、圖與網(wǎng)絡(luò)的基本概念

EADCB1、一個(gè)圖是由點(diǎn)和連線組成。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊）52可編輯pptv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例圖1一個(gè)圖是由點(diǎn)集和中元素的無序?qū)Φ囊粋€(gè)集合構(gòu)成的二元組，記為G=(V，E)，其中V中的元素

叫做頂點(diǎn)，V表示圖G

的點(diǎn)集合；E中的元素叫做邊，E表示圖G的邊集合。{}jvV=53可編輯ppt2、不帶箭頭的連線叫做邊。如果一個(gè)圖是由點(diǎn)和邊所構(gòu)成的，則稱其為無向圖，記作G=(V，E)，連接點(diǎn)的邊記作[vi,vj]，或者[vj,vi]。3、若點(diǎn)與點(diǎn)之間的連線有方向，稱為弧。如果一個(gè)圖是由點(diǎn)和弧所構(gòu)成的，那么稱它為有向圖，記作D=(V,A)，其中V表示有向圖D的點(diǎn)集合，A表示有向圖D的弧集合。一條方向從vi指向vj

的弧，記作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}圖254可編輯ppt4、一條邊的兩個(gè)端點(diǎn)是相同的,那么稱這條邊是環(huán)。5、如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱它們?yōu)槎嘀剡叀?、不含環(huán)和多重邊的圖稱為簡單圖；有多重邊的圖稱為多重圖。7、每一對(duì)頂點(diǎn)間都有邊相連的無向簡單圖稱為完全圖。有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。55可編輯pptv1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10次為零的點(diǎn)稱為弧立點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的關(guān)聯(lián)邊稱為懸掛邊。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)，次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。8、以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的次，記作。圖中

d(v1)=4，d(v6)=4（環(huán)計(jì)兩次）56可編輯ppt定理1所有頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。定理2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。

所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。有向圖中，以

vi為始點(diǎn)的邊數(shù)稱為點(diǎn)vi的出次，用表示；以

vi為終點(diǎn)的邊數(shù)稱為點(diǎn)vi的入次，用表示；vi點(diǎn)的出次和入次之和就是該點(diǎn)的次。57可編輯ppt9、設(shè)G=（V，E），G′=（V′,E′）如果V′

V,E′

E，稱G′是G的子圖；如果V′=V,E′

E，稱G′是G的生成子圖或支撐子圖。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖58可編輯ppt在實(shí)際應(yīng)用中，給定圖中每條邊，對(duì)應(yīng)一個(gè)數(shù)，稱之為“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。10、由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。如:v0，e1，v1，e2，v2，e3，v3,…,vn-1,en

，vn，

e3v1v2v3v4v5v6e7e8e1e2e4e5e6e9e1059可編輯ppt11、圖中任意兩點(diǎn)之間均至少有一條鏈相連，則稱此圖為連通圖。其鏈長為n

，其中v0，vn分別稱為鏈的起點(diǎn)和終點(diǎn)。所含的點(diǎn)、邊均不相同的鏈稱為初等鏈。起點(diǎn)和終點(diǎn)是同一個(gè)點(diǎn)的鏈稱為圈。60可編輯ppt（二）、圖的矩陣表示對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為n，構(gòu)造一個(gè)矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣。61可編輯ppt例權(quán)矩陣為：鄰接矩陣為：v5v1v2v3v4v6433225643762可編輯ppt

二、樹及最小樹問題

已知有六個(gè)城市，它們之間要架設(shè)電話線，要求任意兩個(gè)城市均可以互相通話，并且電話線的總長度最短。v1v2v3v4v5v61、一個(gè)連通的無圈的無向圖叫做樹。樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分支點(diǎn)。63可編輯ppt樹

的性質(zhì)：（1）數(shù)必連通，但無回路（圈）。（2）n個(gè)頂點(diǎn)的樹必有n-1條邊。（3）樹

中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。（4）樹

連通，但去掉任一條邊，必變?yōu)椴贿B通。（5）樹無回路（圈），但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)回路（圈）。v1v2v3v4v5v664可編輯ppt2、若圖G=(V,E)的生成子圖是一個(gè)樹,那么稱該樹

是G的一個(gè)生成樹（支撐樹），或簡稱為圖G的樹。圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊稱為弦。一個(gè)圖G有生成樹的充要條件是G

是連通圖。v1v2v3v4v5v1v2v3v4v565可編輯ppt（一）破圈法：在圖中任選一個(gè)圈，從這個(gè)圈中去掉一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。66可編輯ppt67可編輯ppt用破圈法求出下圖的一個(gè)生成樹。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e868可編輯ppt（二）避圈法：開始選一條邊，以后每一步中，總從未被選取的邊中選出一條與已選邊不構(gòu)成圈的邊，重復(fù)這個(gè)過程，直到不能進(jìn)行為止。69可編輯pptv1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v570可編輯ppt根據(jù)破圈法和避圈法兩種方式得到了圖的兩個(gè)不同的生成樹，由此可以看到連通圖的生成樹不是唯一的。71可編輯ppt3、最小生成樹問題

一棵生成樹所有樹枝上權(quán)的總和為這個(gè)生成樹的權(quán)。具有最小權(quán)的生成樹，稱為最小生成樹。求賦權(quán)圖G的最小支撐樹的方法也有兩種，“破圈法”和“避圈法”。

破圈法：在原圖中，任選一個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余下的圖中重復(fù)這個(gè)步驟，直到得到一不含圈的圖為止。655172344v1v2v3v4v5v672可編輯pptv1v7v4v3v2v5v62015916253281741233673可編輯pptv1v7v4v3v2v5v62015916253281741233674可編輯pptv1v7v4v3v2v5v620159162532817412375可編輯pptv1v7v4v3v2v5v620159162532817412376可編輯pptv1v7v4v3v2v5v6159162532817412377可編輯pptv1v7v4v3v2v5v6159162532817412378可編輯pptv1v7v4v3v2v5v692532817412379可編輯pptv1v7v4v3v2v5v692532817412380可編輯pptv1v7v4v3v2v5v6932817412381可編輯pptv1v7v4v3v2v5v6932817412382可編輯pptv1v7v4v3v2v5v693174123總造價(jià)=1+4+9+3+17+23=5783可編輯pptv1v2v3v4v514231352

避圈法：開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。84可編輯ppt某六個(gè)城市之間的道路網(wǎng)如圖

所示，要求沿著已知長度的道路聯(lián)結(jié)六個(gè)城市的電話線網(wǎng)，使電話線的總長度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v6123485可編輯ppt最短路的一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒有邊），為圖中任意兩點(diǎn)，求一條路，使它從到的所有路中總權(quán)最短。即：最小。(一)、狄克斯徹(Dijkstra)算法適用于wij≥0，給出了從vs到任意一個(gè)點(diǎn)vj的最短路。三、最短路問題86可編輯ppt算法步驟：1.給始點(diǎn)vs以P標(biāo)號(hào)，這表示從vs到vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號(hào)，。2.設(shè)節(jié)點(diǎn)vi為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中，且vj為T標(biāo)號(hào)。對(duì)vj的T標(biāo)號(hào)進(jìn)行如下修改：3.比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全部節(jié)點(diǎn)均為P標(biāo)號(hào)則停止，否則用代替vi，返回步驟（2）。87可編輯ppt例一：用Dijkstra算法求下圖從v1到v6的最短路。

v1v2v3v4v6v5352242421

解：（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（2）（3）（4）88可編輯ppt（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：v1v2v3v4v6v535224242189可編輯ppt（二）、逐次逼近法首先設(shè)任一點(diǎn)vi到任一點(diǎn)vj都有一條弧。顯然，從v1到vj的最短路是從v1出發(fā)，沿著這條路到某個(gè)點(diǎn)vi再沿弧(vi,vj)到vj。則v1到vi的這條路必然也是v1到vi的所有路中的最短路。設(shè)P1j表示從v1到vj的最短路長，P1i表示從v1到vi的最短路長，則有下列方程：

開始時(shí)，令即用v1到vj的直接距離做初始解。90可編輯ppt從第二步起，使用遞推公式：求，當(dāng)進(jìn)行到第t步，若出現(xiàn)則停止計(jì)算，即為v1到各點(diǎn)的最短路長。91可編輯ppt例二、

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v83766

0-5

-3

v8-5-55

0

-1

v7-1-1-1

7101

v6-3-31

0

-1

v5-7-7-73

2

0

8v4-2-2-2-2

1

-50-3

v3-5-5-5-1

2

06v20000

3-2-10v1P(4)P(3)P(2)P(1)v8v7v6v5v4v3v2v1求圖中v1到各點(diǎn)的最短路92可編輯ppt

－18v1v2v3v4v5－26－3－5－1－3－521－1211v6v7v837（0，0）（v3，-5）（v1，-2）（v3，-7）（v2，-3）（v4，-5）（v3，-1）（v6，6）93可編輯ppt例、求：5年內(nèi)，哪些年初購置新設(shè)備，使5年內(nèi)的總費(fèi)用最小。

第i年度

12345購置費(fèi)1111121213設(shè)備役齡0-11-22-33-44-5維修費(fèi)用

568111894可編輯ppt解：（1）分析：可行的購置方案（更新計(jì)劃）是很多的，如：1）每年購置一臺(tái)新的，則對(duì)應(yīng)的費(fèi)用為：

11+11+12+12+13+5+5+5+5+5=842)第一年購置新的，一直用到第五年年底，則總費(fèi)用為：11+5+6+8+11+18=59

顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。95可編輯ppt（2）方法：將此問題用一個(gè)賦權(quán)有向圖來描述，然后求這個(gè)賦權(quán)有向圖的最短路。求解步驟：1）畫賦權(quán)有向圖：設(shè)Vi

表示第i年初，(Vi,Vj)表示第i年初購買新設(shè)備用到第j年初（j-1年底），而Wij

表示相應(yīng)費(fèi)用，則5年的一個(gè)更新計(jì)劃相當(dāng)于從V1

到V6的一條路。2）求解（標(biāo)號(hào)法）96可編輯pptW12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6++8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+5=17W35=12+5+6=23W36=12+5+6+8=31v1v2v3v4v5v616221817171630415931234130222397可編輯pptv1v2v3v4v5v616221817171630415931234130222398可編輯ppt四、最大流問題（一）基本概念1、設(shè)一個(gè)賦權(quán)有向圖G=（V,E）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt

,其它的點(diǎn)叫做中間點(diǎn)。對(duì)于D中的每一個(gè)?。╲i

,vj）∈E,都有一個(gè)非負(fù)數(shù)cij,叫做弧的容量。我們把這樣的圖G叫做容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做G=（V，E，C）。網(wǎng)絡(luò)G上的流，是指定義在弧集合E上的一個(gè)函數(shù)其中f(vi

,vj)=fij

叫做弧(vi，vj)上的流量。

99可編輯ppt2、稱滿足下列條件的流為可行流：（1）容量條件：對(duì)于每一個(gè)?。╲i,vj）∈E 有 0≤

fij

≤

cij

。（2）平衡條件：對(duì)于發(fā)點(diǎn)vs，有對(duì)于收點(diǎn)vt

，有對(duì)于中間點(diǎn)，有可行流中fij＝cij

的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。100可編輯pptvsv1v2v4v3vt374556378S

3、容量網(wǎng)絡(luò)G=（V，E，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合使，則所有一點(diǎn)屬于，而另一點(diǎn)屬于的弧的集合，稱為由

決定的割集,記作。割集中所有始點(diǎn)在

，終點(diǎn)在的弧的容量之和，稱為這個(gè)割集的容量，記為。101可編輯ppt關(guān)于最大流問題的定理：最大流最小割定理：任一網(wǎng)絡(luò)中，最大流的流量等于最小割集的容量。102可編輯ppt

4、容量網(wǎng)絡(luò)G，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，上的弧凡與方向相同的稱為前向弧，凡與方向相反的稱為后向弧，其