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

1、運籌學(xué)及應(yīng)用運籌學(xué)講稿1第八章 圖與網(wǎng)絡(luò)1）圖的分類8.1 圖與網(wǎng)絡(luò)的基本知識ABDEC甲已AB定義一一個圖是由點集V=vi和V中元素的無序?qū)Φ囊粋€集合E=ek所構(gòu)成的二元組，記G=V，E，V中的元素vi稱為頂點，E中的元素ek稱為邊。 當V、E為有限集合時，稱G為有限圖；否則稱G為無限圖。第八章 圖與網(wǎng)絡(luò)v1v2v3v5v4e1e3e4e2e5e6e7e8e9v1v2v3v4e1e2e3e4相鄰點， 如v1 、 v2 ， 同時它們也稱為邊e1的端點邊相鄰， 如e1 、e2 (有公共端點) ，同時它們也稱為點v1的關(guān)聯(lián)邊無向邊端點無序， 如圖1 中e1 、e2等有向邊端點有序， 如圖2 中e1

2、 、e2等圖1圖2環(huán)（自回路）邊的各個端點相同， 如圖1 中e9有向圖邊是有向的， 如圖2無向圖邊是無向的， 如圖1第八章 圖與網(wǎng)絡(luò)v1e1v3v2e2e3e4e5圖3多重邊， 如圖3 中v2 、 v3 ， 同時有兩條邊e4、e5定義二一個圖既不含環(huán)、也不含多重邊，則該圖稱為簡單圖；一個圖含多重邊，則該圖稱為多重圖。第八章 圖與網(wǎng)絡(luò)定義三每一對頂點都有且只有一條無向（有向）邊相連的簡單圖稱為完全圖；定義四設(shè)G=V，E，X、Y V，且XYV，XY=，任意邊ek=（ Vi ，Vj ）E，有Vi X， Vj Y或者Vi Y， Vj X ，稱為二部圖（偶圖）；ABCDABCD第八章 圖與網(wǎng)絡(luò)定義五以點

3、v為端點的邊數(shù)叫做點v的次（度），記d(v)定理1任何圖中，頂點的次數(shù)的總和等于邊數(shù)的2倍定理2任何圖中，頂點的次為奇數(shù)的頂點（奇點）數(shù)為偶數(shù)定義六有向圖中，以v為起始的邊數(shù)叫做點v的出次（度），記d+(v)以v為終點的邊數(shù)叫做點v的入次（度），記d-(v)定義七設(shè)G=V，E，X V，E E，且E中的邊僅與X中的頂點相關(guān)聯(lián)， 則稱G=X，E為G的子圖；如X=V，稱G為G的生成子圖定義八設(shè)G=V，E，如果任意ek=（ Vi ，Vj ）E，f是E到正實數(shù)集上的一個函數(shù)，則稱G為加權(quán)圖，其中f(ei) 稱為ei 的權(quán)第八章 圖與網(wǎng)絡(luò)定義九設(shè)G=V，E，如G中的某些邊與點的交替序列可以排成（vi0,

4、ei1, vi1, ei1 ，vik-1, eik, vik），且eil=（ vil-1, vil ）(l=1,2k),則稱該序列為一條鏈， 鏈長為k (注意，對于有向圖時不考慮邊的方向)定義十在無向圖中，如果一條鏈的起始與終點相同時，稱該鏈為圈定義十一設(shè)G=V，E，任意v1、v2 V，都存在一條鏈，稱該圖為連通圖；定義十在有向圖中，如果一條鏈的所有邊的方向相同時，稱該鏈為道路；同樣圈中所有邊的方向相同時，稱該圈為回路。任意不連通的圖，都可以分成若干個連通子圖，每個子圖稱為原圖的分圖第八章 圖與網(wǎng)絡(luò)2）圖的表示類v1v2v3v4v5976548324A=aij =wij (vj , vj) E

5、0 其它0 9 2 4 79 0 3 4 02 3 0 8 54 4 8 0 67 0 5 6 0權(quán)矩陣令所有權(quán)為1A=0 1 1 1 11 0 1 1 01 1 0 1 11 1 1 0 11 0 1 1 0鄰接矩陣第八章 圖與網(wǎng)絡(luò)A=0 1 1 0 0 00 0 1 0 0 00 1 0 0 1 00 1 0 0 0 10 1 0 1 0 10 0 0 0 1 0v1v2v3v4v5v6其鄰接矩陣為：第八章 圖與網(wǎng)絡(luò)3）歐拉回路定義十二連通圖G中，如存在一條路，經(jīng)過每一邊且僅一次，則稱這條路為歐拉路，如該路為一條回路，稱歐拉回路。具有歐拉回路的圖稱為歐拉圖。定理3無向圖G是歐拉圖的充分必要

6、條件為G中沒有奇點推論1無向圖G是歐拉圖，當且僅當G的邊集可以劃分成若干個初等回路推論2無向圖G有歐拉路，當且僅當G的中有兩個奇點定理3有向圖G是歐拉圖的充分必要條件為G每個頂點的入次等于出次第八章 圖與網(wǎng)絡(luò)4）樹定義十三連通且不含圈的無向圖稱為樹。樹中次為1的點稱葉，否則稱分枝點定理6T是樹T無圈且m=n-1(其中n為頂點數(shù)，m為邊數(shù)，下同)T連通且m=n-1T無圈，但加一條新邊即得唯一一個圈T連通，但舍去任一邊則不連通T中任意兩點有唯一鏈相連定義十四無向圖G中，如生成圖為樹，則該樹為圖G的生成樹定理無向圖G中有生成樹充分必要條件：G是連通圖第八章 圖與網(wǎng)絡(luò)4）生成樹最小生成樹算法：1）Kr

7、uskal 2）破圈法第八章 圖與網(wǎng)絡(luò)最小生成樹算法避圈法（Kruskal）6445843557256vs6445843557256破圈法（Kruskal）ABFGECD例：從某供氣站要向A、B、C、D E、F、G小區(qū)供氣，問如何鋪設(shè) 煤氣管道，使的需要鋪設(shè)管道 的總長度最短第八章 圖與網(wǎng)絡(luò)最短路算法 DijKstra算法例：從油田鋪設(shè)管道，把原油從A地 運到G地，要求管道必須按照圖中 給定的道路鋪設(shè)，問如何鋪設(shè) 煤氣管道，使的需要鋪設(shè)管道 的長度最短AGBCDEF52241382655325254465510510142751326ABDFEC142751326014142751326018

8、63142751326018431427513260171043142751326017943第八章 圖與網(wǎng)絡(luò)4）網(wǎng)絡(luò)最大流（1）基本概念某煤礦（A）的煤需要運往B地，現(xiàn)可以提供的鐵路網(wǎng)及能提供的運量如右圖。問如何進行調(diào)度，才能充分利用能夠提供的運量，使盡可能的煤運往B地？210313589474容量網(wǎng)絡(luò)：加權(quán)有向連通圖，僅有一個入次為0的點，有一個出次為0的點。 記G=V，E，C權(quán)容量入次為0的點發(fā)點出次為0的點收點流：G中任意邊上的非負數(shù)，記fij110274222120可行流：2）對中間點Vi， fij fki= 01） 0 fij Cij最大流：0流：如果所有fji= 0最大的可行流第

9、八章 圖與網(wǎng)絡(luò)最大的可行流，如何求？飽和邊：如果fij = Cij不飽和邊：如果fij Cij增廣鏈（增流鏈）：如果存在從發(fā)點到收點一條鏈lst,如果所有前向邊都為非 飽和邊，而反向邊為非零流邊。零流邊：如果fij = 0非零流邊：如果fij 0前向邊：如果鏈lst , 如果方向與s-t同向，稱前向邊；否則稱為反向邊最大流最小割定理頂點的流量： fij fji割集：設(shè)G=（V，E，C），V1 V2 =V，V1V2=且發(fā)點s V1，收點t V2割集的容量： fij，vi V1, vj V2， 記C（V1，V2）第八章 圖與網(wǎng)絡(luò)定理4-1: 設(shè)G=（V，E，C），V1， V2為割集， fij為G的

10、任一可行流，W為其流量，必有 CV1，V2）W最大流最小割定理: 設(shè)G=（V，E，C），V1， V2為割集， fij為為最大流充分必要條件 W=min（C（V1，V2）| V1，V2 為G的割集）定理4-2: 設(shè)G=（V，E，C）， fij為為最大流充分必要條件不存在增廣鏈利用該定理求最大流，如何求？枚舉法把求最大流轉(zhuǎn)化為求是否存在增廣鏈問題第八章 圖與網(wǎng)絡(luò)如何求增廣鏈？最大流的標號算法算法： （前提條件為已經(jīng)存在可行流）1）從發(fā)點開始標號（）2）選擇一個已經(jīng)標號頂點vi，對于與頂點vi相鄰而未標號的頂點（vj）進行如下處理： （1）若（ vi ， vj） E，且fij0，則令j = min(

11、fji, i)，并給vj標以（-vi, j)3）重復(fù)（2）直到收點vt或不再有頂點可標記為止。一、標號過程二、調(diào)整過程 其實，這是尋找增廣鏈的過程，如果不能把vt進行標號時，即不存在增廣鏈，根據(jù)定理，初始流就是最大流，結(jié)束，否則轉(zhuǎn)第二步1）令fij = fij + t 前向邊f(xié)ij t 后向邊f(xié)ij 其他2擦除所有標號，重新開始第八章 圖與網(wǎng)絡(luò)例15 P2715）非標準網(wǎng)絡(luò)的最大流問題（1）發(fā)點不唯一 （2）收點不唯一 （3）收發(fā)點都不唯一P2736）最大匹配問題（2）匹配定義：（1）背景：簡介工作安排二部圖G=（X，Y，E），若M中任意兩條邊都沒有公共端點P274第八章 圖與網(wǎng)絡(luò)7）最小費用流問題（1）費用：定理：已知網(wǎng)絡(luò)G=（V，E，C，d），f 是可行流， 為從vs到vt的一條可增廣鏈，則稱當（vi, vj）Ed(f) =鏈 的費用若f是流量為W(