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

2、 、e2等圖1圖2環(huán)（自回路）邊的各個(gè)端點(diǎn)相同， 如圖1 中e9有向圖邊是有向的， 如圖2無向圖邊是無向的， 如圖1第八章 圖與網(wǎng)絡(luò)v1e1v3v2e2e3e4e5圖3多重邊， 如圖3 中v2 、 v3 ， 同時(shí)有兩條邊e4、e5定義二一個(gè)圖既不含環(huán)、也不含多重邊，則該圖稱為簡單圖；一個(gè)圖含多重邊，則該圖稱為多重圖。第八章 圖與網(wǎng)絡(luò)定義三每一對頂點(diǎn)都有且只有一條無向（有向）邊相連的簡單圖稱為完全圖；定義四設(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ò)定義五以點(diǎn)

3、v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次（度），記d(v)定理1任何圖中，頂點(diǎn)的次數(shù)的總和等于邊數(shù)的2倍定理2任何圖中，頂點(diǎn)的次為奇數(shù)的頂點(diǎn)（奇點(diǎn)）數(shù)為偶數(shù)定義六有向圖中，以v為起始的邊數(shù)叫做點(diǎn)v的出次（度），記d+(v)以v為終點(diǎn)的邊數(shù)叫做點(diǎn)v的入次（度），記d-(v)定義七設(shè)G=V，E，X V，E E，且E中的邊僅與X中的頂點(diǎn)相關(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è)函數(shù)，則稱G為加權(quán)圖，其中f(ei) 稱為ei 的權(quán)第八章 圖與網(wǎng)絡(luò)定義九設(shè)G=V，E，如G中的某些邊與點(diǎn)的交替序列可以排成（vi0,

4、ei1, vi1, ei1 ，vik-1, eik, vik），且eil=（ vil-1, vil ）(l=1,2k),則稱該序列為一條鏈， 鏈長為k (注意，對于有向圖時(shí)不考慮邊的方向)定義十在無向圖中，如果一條鏈的起始與終點(diǎn)相同時(shí)，稱該鏈為圈定義十一設(shè)G=V，E，任意v1、v2 V，都存在一條鏈，稱該圖為連通圖；定義十在有向圖中，如果一條鏈的所有邊的方向相同時(shí)，稱該鏈為道路；同樣圈中所有邊的方向相同時(shí)，稱該圈為回路。任意不連通的圖，都可以分成若干個(gè)連通子圖，每個(gè)子圖稱為原圖的分圖第八章 圖與網(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中沒有奇點(diǎn)推論1無向圖G是歐拉圖，當(dāng)且僅當(dāng)G的邊集可以劃分成若干個(gè)初等回路推論2無向圖G有歐拉路，當(dāng)且僅當(dāng)G的中有兩個(gè)奇點(diǎn)定理3有向圖G是歐拉圖的充分必要條件為G每個(gè)頂點(diǎn)的入次等于出次第八章 圖與網(wǎng)絡(luò)4）樹定義十三連通且不含圈的無向圖稱為樹。樹中次為1的點(diǎn)稱葉，否則稱分枝點(diǎn)定理6T是樹T無圈且m=n-1(其中n為頂點(diǎn)數(shù)，m為邊數(shù)，下同)T連通且m=n-1T無圈，但加一條新邊即得唯一一個(gè)圈T連通，但舍去任一邊則不連通T中任意兩點(diǎn)有唯一鏈相連定義十四無向圖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地 運(yùn)到G地，要求管道必須按照圖中 給定的道路鋪設(shè)，問如何鋪設(shè) 煤氣管道，使的需要鋪設(shè)管道 的長度最短AGBCDEF52241382655325254465510510142751326ABDFEC142751326014142751326018

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

9、八章 圖與網(wǎng)絡(luò)最大的可行流，如何求？飽和邊：如果fij = Cij不飽和邊：如果fij Cij增廣鏈（增流鏈）：如果存在從發(fā)點(diǎn)到收點(diǎn)一條鏈lst,如果所有前向邊都為非 飽和邊，而反向邊為非零流邊。零流邊：如果fij = 0非零流邊：如果fij 0前向邊：如果鏈lst , 如果方向與s-t同向，稱前向邊；否則稱為反向邊最大流最小割定理頂點(diǎn)的流量： fij fji割集：設(shè)G=（V，E，C），V1 V2 =V，V1V2=且發(fā)點(diǎn)s V1，收點(diǎn)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ò)如何求增廣鏈？最大流的標(biāo)號(hào)算法算法： （前提條件為已經(jīng)存在可行流）1）從發(fā)點(diǎn)開始標(biāo)號(hào)（）2）選擇一個(gè)已經(jīng)標(biāo)號(hào)頂點(diǎn)vi，對于與頂點(diǎn)vi相鄰而未標(biāo)號(hào)的頂點(diǎn)（vj）進(jìn)行如下處理： （1）若（ vi ， vj） E，且fij0，則令j = min(

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