運籌學(xué)圖論概述

本章重點圖的基本概念常見的四個問題的求解方法圖的含義圖是一種模型如公路、鐵路交通圖，通訊網(wǎng)絡(luò)圖等圖是對現(xiàn)實的抽象很多問題都可以用頂點和邊來表示，一般頂點表示實體，邊(頂點與頂點之間的連線)表示實體之間的關(guān)系，頂點和邊的集合定義為圖圖論的提出(1)用圖來描述事物及其聯(lián)系，最早是由瑞士數(shù)學(xué)家歐拉(Euler)于1736年解決哥尼斯堡七橋問題時提出的如右圖所示，哥尼斯堡地區(qū)被河流分為了四個區(qū)域，四個區(qū)域之間有七座橋相連，問是否有一條路線，可以經(jīng)過所有的橋并且每座橋只經(jīng)過一次？BACD圖論的提出(2)用圖來表示這個問題用四個頂點表示四個地區(qū)用七條邊表示七座橋要尋找這樣的一條路線：經(jīng)過所有的邊并且每條邊只經(jīng)過一次該問題已經(jīng)證明無解圖的基本概念(1)圖：頂點和邊的集合點的集合用V表示，邊的集合用E表示，則圖可以表示為G=(V,E)如下圖G=(V,E)其中，V={A,B,C,D}E={e1,e2,e3,e4,e5,e6,e7}E中，e1=(A,D),e2=(B,D),e3=(C,D)e4=(B,C),e5=(A,C),e6=(A,C),e7=(B,C)e2e1e3e4e5e6e7圖的基本概念(2)邊都沒有方向的圖稱為無向圖，前面所講的圖就是無向圖。無向圖的邊eij=(vi,vj)=(vj,vi)=eji當(dāng)圖中的邊都有方向時，稱為有向圖。為了區(qū)別于無向圖，有向圖用G(V,A)表示在有向圖中，有向邊又稱為弧，用aij=(vi,vj)表示，(vi,vj)≠(vj,vi)，弧的方向用箭頭標(biāo)識既有邊又有弧的圖稱為混合圖下圖中從左向右依次為：無向圖，有向圖，混合圖圖的基本概念(3)集合V中元素的個數(shù)稱為圖G的頂點數(shù)，記作p(G)。前例中，p(G)=4集合E(或A)中元素的個數(shù)稱為圖G的邊數(shù)，記作q(G)。前例中，q(G)=7若e=(u,v)∈E(或a=(u,v)∈A)，則稱u和v為e(或a)的端點，e(或a)稱為頂點u和v的關(guān)聯(lián)邊，也稱u,v與邊e(或a)相關(guān)聯(lián)。前例中，A,B是邊e1的端點，e1是A,B的關(guān)聯(lián)邊若頂點u和v與同一條邊相關(guān)聯(lián)，則稱u和v為相鄰點若兩條邊ei和ej有同一個端點，則稱ei和ej為相鄰邊圖的基本概念(4)若一條邊的兩個端點是同一個頂點，則稱該邊為環(huán)若兩個端點之間有多于一條邊，則稱為重邊(書上稱為多重邊)，前例中，A,C之間和B,C之間都有兩條邊無環(huán)也無重邊的圖稱為簡單圖與頂點v相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點的“度”(書上稱為次)，記為d(v)度數(shù)為奇數(shù)的頂點稱為奇點，度數(shù)為偶數(shù)的頂點稱為偶點在有向圖中，由頂點指向外的弧的數(shù)目稱為正度，記為d+，指向該頂點的弧的數(shù)目稱為負(fù)度，記為d–度數(shù)為0的點稱為孤立點，度數(shù)為1的點稱為懸掛點圖的基本概念(5)與懸掛點連接的邊稱為懸掛邊若圖中所有的點都是孤立點，則稱為空圖定理6.1所有頂點的度數(shù)之和，等于所有邊數(shù)的兩倍原因：每條邊關(guān)聯(lián)兩個頂點，計算頂點的度數(shù)時，每條邊計算了2次定理6.2圖中奇點的個數(shù)總是偶數(shù)個原因：所有頂點的度數(shù)之和是偶數(shù)，偶點的度數(shù)之和也是偶數(shù)，因此，奇點的度數(shù)之和必為偶數(shù)，因此，奇點的個數(shù)必是偶數(shù)個圖的基本概念(6)點邊交錯序列v0,e1,v1,e2,v2,…,vn-1,en,vn稱為鏈。其中v0稱為路的起點，vn稱為路的終點若v0≠vn，稱為開鏈；反之，稱為閉鏈(對于無向圖而言，也稱為回路)若鏈中所含的邊均不相同，稱為簡單鏈若鏈中所含的頂點均不相同，稱為初等鏈(對于無向圖而言，也稱為通路)除起點和終點外均不相同的閉鏈，稱為圈(對于無向圖而言，也稱為初等回路)以上概念(除特別標(biāo)注的外)對無向圖和有向圖均適用圖的基本概念(7)在有向圖中，點邊交錯序列v0,e1,v1,e2,v2,…,vn-1,en,vn(其中ek=(vk-1,vk))稱為路若v0≠vn，稱為開路；反之，稱為回路(注意和無向圖的回路區(qū)分開來)若路中所含的邊均不相同，稱為簡單路若路中所含的頂點均不相同，稱為初等路除起點和終點外均不相同的回路，稱為初等回路(注意和無向圖的初等回路區(qū)分開來)本頁概念都是針對有向圖圖的基本概念(8)若一個圖(無向圖或有向圖)中任意兩點之間至少有一條初等鏈連接，則稱該圖為連通圖，否則稱為不連通圖在一個有向圖中，若任意兩點u和v，u到v和v到u之間都至少有一條初等路連接，則稱該圖為強連通圖，否則稱為非強連通圖圖的基本概念(9)子圖：設(shè)G1=(V1,E1)，G2=(V2,E2)，若V1V2，E1E2，則稱G1是G2的子圖注：生成子圖時，可以只選頂點不選與該頂點相關(guān)聯(lián)的邊，但不能只選邊不選與該邊相關(guān)聯(lián)的頂點如下圖，右圖是左圖的子圖圖的基本概念(10)如下圖，右圖是左圖的真子圖真子圖：若V1V2，E1E2，稱G1是G2的真子圖部分圖：若V1=V2，E1E2，稱G1是G2的部分圖圖的基本概念(11)導(dǎo)出子圖：若V1V2，E1={(ui,vj)E2|uiV1,vjV1}，稱G1是G2中由V1導(dǎo)出的導(dǎo)出子圖，記作G(V1)如下圖，右圖是左圖的導(dǎo)出子圖圖的基本概念(12)一個沒有圈的圖稱為無圈圖或稱為林一個連通的無圈圖稱為樹一個林的每個連通子圖都是一個樹定理6.3：關(guān)于樹的以下描述是等價的無圈連通圖(定義)無圈圖G，q(G)=p(G)-1(定義+對頂點個數(shù)用歸納法)連通圖G，q(G)=p(G)-1(定義+對頂點個數(shù)用歸納法)無圈，但增加一條邊可以得到唯一的圈(定義+對頂點個數(shù)用歸納法)連通，但去掉一條邊就不連通(反證法)每一對頂點之間有且僅有一條初等鏈(反證法)圖的基本概念(13)若T是圖G的部分圖，且T是樹，則稱T為G的生成樹(書上稱為部分樹)圖的存儲方式(1)計算機中存儲圖一般采用矩陣存儲常用的存儲方法有兩種鄰接矩陣關(guān)聯(lián)矩陣圖的存儲方式(2)對于無向圖，鄰接矩陣存儲方式如下若頂點vi和vj之間沒有邊，則aij=aji=0若頂點vi和vj之間存在n條邊，則aij=aji=n注：一般i≤jv1v2v3v4v5圖的存儲方式(3)v1v2v3v4v5對于有向圖，鄰接矩陣存儲方式如下若頂點vi和vj之間沒有弧，則aij=0若頂點vi和vj之間存在n條弧(vi,vj)，則aij=n注：允許i=j圖的存儲方式(4)對于無向圖，關(guān)聯(lián)矩陣存儲方式如下若頂點vi不和邊ej相關(guān)聯(lián)，則bij=0若頂點vi和邊ej相關(guān)聯(lián)，則bij=1v1v2v3v4v5e1e2e3e4e5e6e7e8e9e9關(guān)聯(lián)的頂點個數(shù)為1，是自環(huán)圖的存儲方式(5)對于有向圖，關(guān)聯(lián)矩陣存儲方式如下若頂點vi不和弧ej相關(guān)聯(lián)，則bij=0若頂點vi是弧ej的起點，則bij=1若頂點vi是弧ej的終點，則bij=-1若頂點vi既是弧ej的起點又是弧ej的終點，則bij=2v1v2v3v4v5e1e2e3e4e5e6e7e8e9簡單圖的權(quán)值矩陣(1)對于賦權(quán)簡單圖，權(quán)值矩陣存儲方式如下若頂點vi和vj之間沒有邊，則wij=0若頂點vi和vj之間有邊(vi,vj)，則wij=相應(yīng)邊的權(quán)值注：無向圖和有向圖均適用，有向圖要注意邊的方向簡單圖的權(quán)值矩陣(2)v1v2v3v4v5376245v1v2v3v4v5376245最短路線問題一般針對賦權(quán)連通圖(有向圖或無向圖皆可)，求兩點之間所經(jīng)路線權(quán)值之和為最小的路線求解該問題可以采用上一章介紹的動態(tài)規(guī)劃的方法該方法適用于無負(fù)初等回路(指所有邊的權(quán)值之和為負(fù)值的初等回路)的賦權(quán)連通圖(有向圖或無向圖皆可)；若有負(fù)初等回路，則不存在最短路線該方法需要人工劃分階段，適合人工計算書上介紹的三種算法，不需要明確的劃分階段，較為適合計算機運算狄克斯拉(Dijkstra)算法(1)該算法有兩個依據(jù)從v1到vn的最短路線也是從vn到v1的最短路線對于無向圖必定成立對于有向圖而言，vn到v1的最短路線是指將圖中弧的方向反過來，但權(quán)值不變時的最短路線以vn為起點，v1為終點應(yīng)用動態(tài)規(guī)劃的最優(yōu)性原理第一條依據(jù)保證了按這種方法求得的結(jié)果是從v1到vn的最短路線狄克斯拉(Dijkstra)算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令i=1，S1={v1}，S2={v2,v3,…,vn}，令P(v1)=0，T(vj)=∞（vj∈S2）令T(vj)=min{T(vj)，P(vi)+lij|vj∈S2}令vk=min{T(vj)|vj∈S2}，P(vk)=T(vk)若vk=vn，則已經(jīng)找到v1到vn的最短距離P(vk)否則，令i=k，從S2中刪去vi，轉(zhuǎn)上一步狄克斯拉(Dijkstra)算法(3)該算法適用于無負(fù)初等回路的賦權(quán)連通圖(有向圖或無向圖皆可)，但算法本身不能判定圖中是否存在負(fù)初等回路因此，該算法一般應(yīng)用于無負(fù)權(quán)值的賦權(quán)連通有向圖或無向圖示例(6.1-1)sabcdt5839149543路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試用Dijkstra算法求s到t的最短路線示例(6.1-2)sabcdt初始值T()第1次P()+lijT()第2次P()+lijT()第3次P()+lijT()第4次P()+lijT()第5次P()+lijT()0∞∞∞∞∞0+50+80+∞0+∞0+∞58∞∞∞5+∞5+35+95+∞8814∞8+∞8+48+∞812∞8+38+9111711+51612345示例(6.1-3)sabcdt5839149543海斯算法(1)該算法有兩個依據(jù)從v1到vn的最短路線也是從vn到v1的最短路線對于無向圖必定成立對于有向圖而言，vn到v1的最短路線是指將圖中弧的方向反過來，但權(quán)值不變時的最短路線若從vi到vj的最短路線經(jīng)過vk，則vi到vk、vk到vj的都是相應(yīng)的最優(yōu)路線第一條依據(jù)保證了從vi到vj的最短路線也是從vj到vi的最短路線則根據(jù)動態(tài)規(guī)劃最優(yōu)性原理，vk到vj和vk到vi都是相應(yīng)的最優(yōu)路線，由此得到上面的結(jié)論海斯算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令dij(0)=lij，i=1～n，j=1～ndij(t)表示從vi到vj的2t步距離當(dāng)dij(m-1)已知時，令

dij(m)=min{dik(m-1)+dkj(m-1)|k=1～n}當(dāng)對所有的i,j有dij(m)=dij(m-1)時，dij(m)是vi到vj的最短距離。否則，若2m-1＜n-1，m=m+1，轉(zhuǎn)上一步；若2m-1≥n-1，說明存在負(fù)初等回路，最短路線不存在，算法停止海斯算法(3)該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無向圖所得的結(jié)果矩陣中包含了圖中任意兩點之間的最短距離示例(6.2-1)sabcdt5839149543路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試用海斯算法求s到t的最短路線示例(6.2-2)示例(6.2-3)示例(6.2-4)由于D(3)=D(2)，停止計算s到t的最短路線長度為16由D(2)知s到t經(jīng)過c由D(1)知s到c經(jīng)過a，c到t經(jīng)過d則最短路線為sacdtsabcdt5839149543福德(Ford)算法(1)該算法和Dijkstra算法一樣有兩個依據(jù)從v1到vn的最短路線也是從vn到v1的最短路線對于無向圖必定成立對于有向圖而言，vn到v1的最短路線是指將圖中弧的方向反過來，但權(quán)值不變時的最短路線以vn為起點，v1為終點應(yīng)用動態(tài)規(guī)劃的最優(yōu)性原理第一條依據(jù)保證了按這種方法求得的結(jié)果是從v1到vn的最短路線福德(Ford)算法(2)算法步驟已知網(wǎng)絡(luò)的距離矩陣L=(lij)，lij表示vi到vj的弧上的距離權(quán)值令dj(1)=l1j，j=1～ndj(t)表示從v1到vj的步數(shù)不超過t的最短距離當(dāng)dj(k)已知時，令dj(k+1)=min{di(k)+lij|i=1～n}當(dāng)對所有的j有dj(k+1)=dj(k)時，dj(k)是v1到vj的最短距離。否則，若k＜n-1，k=k+1，轉(zhuǎn)上一步；若k≥n-1，說明存在負(fù)初等回路，最短路線不存在，算法停止福德(Ford)算法(3)該算法可以判斷是否存在負(fù)初等回路，適用于任意權(quán)值的賦權(quán)連通有向圖或無向圖所得的結(jié)果中包含了從v1到其他任意點的最短距離示例(6.3-1)sabcdt5839149543路線圖如下所示，箭頭表示通行方向，線上數(shù)字表示道路長度，試用Ford算法求s到t的最短路線示例(6.3-2)abcdd示例(6.3-3)由于dj(4)=dj(3)(j=s,a,b,c,d,t)，停止計算s到t的最短路線長度為16最短路線為sacdtsabcdt5839149543最小生成樹問題一般針對賦權(quán)連通圖，求該圖權(quán)值之和為最小的生成樹求解該問題一般有兩種方法破圈法生長法破圈法求最小生成樹假設(shè)原圖為賦權(quán)連通圖破圈法依據(jù)樹的定義給出求最小生成樹算法破圈法步驟如下在圖中找到一個圈，進入下一步；若無圈則停止，此時的圖就是原圖的最小生成樹查看該圈與其它圈是否有公共邊若沒有公共邊，在該圈中選權(quán)值最大的邊，去掉該邊；對新的圖返回上一步若有公共邊，將這些有公共邊的若干個圈合在一起看作一個回路，在該回路中選權(quán)值最大的邊，去掉該邊；對新的圖返回上一步示例(6.4-1)3354726432用破圈法求下圖的最小生成樹生長法求最小生成樹(1)生長法依據(jù)根據(jù)動態(tài)規(guī)劃最優(yōu)性原理，劃分n-1個階段x1=S1從圖中任選一點vi，令S1={vi}，S2=V-S1，k=1uk為k階段選中的權(quán)值最小的邊(vi,vj)，vi∈S1，vj∈S2xk+1=xk+{uk}+{vj}S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}xn狀態(tài)結(jié)束此時，S1就是要求的最小生成樹的點邊集合，S2是空集生長法求最小生成樹(2)假設(shè)原圖為賦權(quán)連通圖生長法步驟如下從圖中任選一點vi，令S1={vi}，S2=V-S1從S1中的各點到S2中各點的邊中選擇權(quán)值最小的邊(vi,vj)，vi∈S1，vj∈S2令S1=S1+{(vi,vj)}+{vj}，S2=S2-{vj}若S2是空集，則停止，S1就是要求的最小生成樹的點邊集合；否則轉(zhuǎn)第二步示例(6.5-1)3354726432用生長法求下圖的最小生成樹作業(yè)(17)書上218頁5-1的(b)補充：3和8之間權(quán)值為13破圈法或生長法皆可最大流問題(1)一般針對賦權(quán)連通有向圖，每條弧的權(quán)值表示該弧允許流過的最大流量，每個頂點的流入量之和等于流出量之和，求圖上兩定點之間允許流過的最大流量最大流-最小割定理最大流量等于最小割集(容量最小的割集)的容量注：將圖G中頂點集合V分為兩個集合S1和S2，其中起點vs∈S1、終點vt∈S2，且S1∪S2=V、S1∩S2=，則把集合C={(vi,vj)|vi∈S1,vj∈S2}稱為圖G的一個割集割集中弧的權(quán)值之和稱為該割集的容量最大流問題(2)利用最大流-最小割定理，福德和富克遜提出了求解最大流問題的標(biāo)號法可行流最大流結(jié)束改變流量是否最大流問題(3)標(biāo)號法相關(guān)概念若弧(vi,vj)上的流量xij=bij，則稱該弧為飽和弧，否則稱為非飽和弧若弧(vi,vj)上的流量xij=0，則稱該弧為零流弧，否則稱為非零流弧在一條從vs到vt的點邊交錯序列中，與vs到vt方向一致的弧稱為正向弧，與vs到vt方向相反的弧稱為逆向弧若從vs到vt的某個點邊交錯序列中，正向弧均為非飽和弧，逆向弧均為非零流弧，則稱該點邊交錯序列為一條流量增廣鏈最大流問題(4)流量增廣鏈的作用它是用來增加正向總流量的使增廣鏈上正向弧的流量增大使增廣鏈上逆向弧的流量減小若找不到，表示不能再增大正向總流量，即當(dāng)前的正向總流量就是最大流量最大流問題(5)標(biāo)號法步驟如下分配vi到vj的初始流xij尋找增廣鏈，若不存在，則已經(jīng)最優(yōu)；否則進入下一步調(diào)整。尋找增廣鏈方法如下將vs標(biāo)記上(-,∞)，S1={vs}，S2=V-S1若存在以S1中點為起點、以S2中點為終點的非飽和弧(vi,vj)，則為vj標(biāo)記上(vi+,zj)，zj=min{zi,bij-xij}，S1=S1+{vj}，S2=S2-{vj}若存在以S2中點為起點、以S1中點為終點的非零流弧(vj,vi)，則為vj標(biāo)記上(vi-,zj)，zj=min{zi,xji}，S1=S1+{vj}，S2=S2-{vj}若S1中已包含vt

，則已找到一條增廣鏈，否則轉(zhuǎn)向第二步最大流問題(6)調(diào)整流量，方法如下設(shè)vt

上的標(biāo)記為(vk+,zt)，則整個增廣鏈上最大的調(diào)整量為z=zt由vt

上的標(biāo)記可以得到增廣鏈上的前一個頂點vk

，依次向前可以找到整個增廣鏈在增廣鏈上，正向弧流量增加z，逆向弧流量減少z返回第二步繼續(xù)尋找下一個增廣鏈?zhǔn)纠?6.6-1)(9)(8)(3)(7)(4)(4)(2)(6)(11)711106915543vsvtv2v3v4v5(-,∞)(vs+,7)(v2-,3)(v3+,1)(v3+,3)(v5+,3)用標(biāo)號法求出從vs到vt的最大流示例(6.6-2)調(diào)整流量，得711106915543vsvtv2v3v4v5(11)(0)(9)(7)(4)(4)(5)(9)(11)(-,∞)(vs+,4)找不到增廣鏈，則當(dāng)前流量20為最優(yōu)最小費用-最大流問題(1)一般情況下，最大流量是唯一的，而相應(yīng)的每條弧上的流量分布卻是不唯一的如果已知流過弧(vi,vj)的單位流量要發(fā)生cij的費用，要求使得總費用為最小的最大流流量分配方案，這種問題稱為最小費用-最大流問題可以使用對偶法解決這個問題最小費用-最大流問題(2)對偶法原理對原圖求出從vs到vt的所有初等路將這些初等路按照單位流量費用之和從小到大排序，編號1,2,3,…,m使第1號初等路上的流量為最大在余下的允許流量中，使第2號初等路上的流量為最大在余下的允許流量中，使第3號初等路上的流量為最大…在余下的允許流量中，使第m號初等路上的流量為最大此時，圖中的流量分布即為最小費用-最大流在實際使用時，要對原圖求出從vs到vt的所有初等路有一定的難度，容易遺漏最小費用-最大流問題(3)因此，對偶法在實際操作時求出最大流量，以0流為初始可行流對原圖求出從vs到vt的單位流量費用之和為最小的初等路調(diào)整使得該初等路上的流量為最大，若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費用-最大流，否則進入下一步對當(dāng)前可行流生成擴展費用圖。在擴展費用圖中，從原圖的允許流量中去掉當(dāng)前可行流的流量，將圖中某些弧的單位流量費用調(diào)整為∞(這些弧的允許流量已經(jīng)減小為0，使得此弧不通)在該擴展費用圖中，求出新的從vs到vt的單位流量費用之和為最小的初等路，轉(zhuǎn)向第三步最小費用-最大流問題(4)對偶法步驟用標(biāo)號法求出最大流量將原圖作為初始擴展費用圖，以0流作為初始可行流在擴展費用圖上，用Ford算法求出從vs到vt的單位流量費用之和為最小的初等路作為增廣鏈按前面標(biāo)號法中調(diào)整流量的方法調(diào)整流量，得到一個新的可行流若當(dāng)前可行流的流量等于最大流量，則當(dāng)前可行流就是最小費用-最大流，否則進入下一步對當(dāng)前可行流生成新的擴展費用圖，轉(zhuǎn)向第三步最小費用-最大流問題(5)擴展費用圖的生成在弧(vi,vj)上若xij=0，則原弧不變?nèi)?＜xij＜bij

，則把弧(vi,vj)改造成如下的兩條弧若xij=bij

，則把弧(vi,vj)改造成方向相反的另一條弧vivj(bij-xij,cij)(xij,-cij)vivj(bij,cij)在生成增廣鏈時用不到反向弧(vj,vi)

，這樣就去掉了當(dāng)前可行流的流量同理，使得弧(vi,vj)不通，將其單位流量費用調(diào)整為∞示例(6.7-1)求出從vs到vt的最小費用-最大流，圖中弧上數(shù)字含義為(bij,cij)vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)(11,3)示例(6.7-2)由示例(6.6)，如下圖，已知從vs到vt的最大流量為20vsvtv2v4v3v5(15,2)(9,6)(3,3)(5,5)(4,9)(7,8)(6,3)(10,1)