運(yùn)籌學(xué)第八章2007課件

聯(lián)系電話：短號(hào)：

E-mail:《運(yùn)籌學(xué)教程》（第三版）運(yùn)籌學(xué)基礎(chǔ)胡運(yùn)權(quán)主編教材運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件圖與網(wǎng)絡(luò)分析第八章一、圖及其分類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為無限圖。第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)v1e1v3v2e2e3e4e5圖3多重邊，如圖3中v2、v3，同時(shí)有兩條邊e4、e5定義二一個(gè)圖既不含環(huán)、也不含多重邊，則該圖稱為簡單圖；一個(gè)圖含多重邊，則該圖稱為多重圖。第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)定義三每一對(duì)頂點(diǎn)都有且只有一條無向（有向）邊相連的簡單圖稱為完全圖；定義四設(shè)G={V，E}，X、YV，且X∪Y＝V，X∩Y=φ，任意邊ek=（ei，ej）∈E，有ei∈X，ej∈Y，稱為二部圖（偶圖）；第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)定義五以點(diǎn)v為端點(diǎn)的邊數(shù)叫做點(diǎn)v的次（度），記d(v)定理1任何圖中，頂點(diǎn)的次數(shù)的總和等于邊數(shù)的2倍定理2任何圖中，頂點(diǎn)的次為奇數(shù)的頂點(diǎn)數(shù)為偶數(shù)定義六有向圖中，以v為起始的邊數(shù)叫做點(diǎn)v的出次（度），記d+(v)以v為終點(diǎn)的邊數(shù)叫做點(diǎn)v的入次（度），記d-(v)定義七設(shè)G={V，E}，XV，E’E，如果ek=（ei，ej）∈E’，有ei、ej∈X，則；稱G’={X，E’}為G的子圖；如X=V，稱G’為G的生成子圖.定義八設(shè)G={V，E}，如果任意ek=（ei，ej）∈E，f是E到正實(shí)數(shù)集上的一個(gè)函數(shù)，則稱G為加權(quán)圖，其中f(ei)

稱為ei∈的權(quán)第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)二、圖的表示類v1v2v3v4v5976548324A=aij=wij(vj,vj)∈E0其它0924790340230854480670560權(quán)矩陣令所有權(quán)為1A=0111110110110111110110110鄰接矩陣第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)A=011000001000010010010001010101000010v1v2v3v4v5v6其鄰接矩陣為：第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)三、歐拉回路定義十二連通圖G中，如存在一條路，經(jīng)過每一邊且僅一次，則稱這條路為歐拉路，如該路為一條回路，稱歐拉回路。定理3無向圖G是歐拉圖的充分必要條件為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)的入次等于出次。第一節(jié)圖與網(wǎng)絡(luò)的基本知識(shí)第二節(jié)樹及其最小生成樹最小生成樹算法：1）Kruskal2）破圈法避圈法（Kruskal）6445843557256vs6445843557256破圈法（Kruskal）ABFGECD例：從某供氣站要向A、B、C、D、E、F、G小區(qū)供氣，問如何鋪設(shè)煤氣管道，使得需要鋪設(shè)管道的總長度最短第三節(jié)最短路問題及其算法最短路算法——DijKstra算法例：從油田鋪設(shè)管道，把原油從A地運(yùn)到G地，要求管道必須按照?qǐng)D中給定的道路鋪設(shè)，問如何鋪設(shè)煤氣管道，使的需要鋪設(shè)管道的長度最短。AGBCDEF52241382655325∞∞∞∞254465510510142751326ABDFE∞∞4142751326018∞63142751326018∞431427513260171043142751326017943第四節(jié)最大流問題一、基本概念某煤礦（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）∑fij=∑fji1）0≤fij≤Cij最大流：0流：如果所有fji=0最大的可行流例3）∑fsi=∑fjt定理4-1:設(shè)G=（V，E，C），V1，V2為割集，fij為G的任一可行流，W為其流量，必有CV1，V2）≥W最大流—最小割定理:設(shè)G=（V，E，C），E’=（V1，V2）為割集，fij為最大流充分必要條件W=min（C（V1，V2）|E’為G的割集）定理4-2:設(shè)G=（V，E，C），fij為為最大流充分必要條件不存在增廣鏈利用該定理求最大流，如何求？枚舉法把求最大流轉(zhuǎn)化為求是否存在增廣鏈問題第四節(jié)最大流問題如何求增廣鏈？最大流的標(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，對(duì)于與頂點(diǎn)vi相鄰而未標(biāo)號(hào)的頂點(diǎn)（vj）進(jìn)行如下處理：

（1）若（vi，vj）∈E，且fij<cij，則令δj=min(cij-fij,δi)，并給vj標(biāo)以（+vi,δj)（2）若（vj，vi）∈E，且fji>0，則令δj=min(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