運(yùn)籌學(xué)-圖與網(wǎng)絡(luò)模型以及最小費(fèi)用最大流教學(xué)課件

Chapterll圖與網(wǎng)絡(luò)分析GraphTheoryandNetworkAnalysis本章主要內(nèi)容:圖與網(wǎng)絡(luò)的基本概念與模型最短路問題最小生成樹問題最大流問題9最小費(fèi)用最大流問題圖與網(wǎng)絡(luò)的基本概念與模型漢漢陽漢口長江您能從武漢理工大學(xué)出發(fā)走過每座橋且只走一次然后回到學(xué)武昌校嗎?圖與網(wǎng)絡(luò)的基本概念與模型近代圖論的歷史可追溯到18世紀(jì)的七橋問題一穿過Konigsberg城的七座橋,要求每座橋通過一次且僅通過一次。這就是著名的“哥尼斯堡7橋”難題。Euler1736年證明了不可能存在這樣的路線。三H月1K6nigsberg橋?qū)?yīng)的圖圖與網(wǎng)絡(luò)的基本概念與模型·圖論中圖是由點(diǎn)和邊構(gòu)成,可以反映一些對象之間的關(guān)系。般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直,對于反映對象之間的關(guān)系并不是重要的圖的定義P230)若用點(diǎn)表示研究的對象,用邊表示這些對象之間的聯(lián)系,則圖G可以定義為點(diǎn)和邊的集合,記作:G=,EN其中:V——點(diǎn)集E—邊集※圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。圖與網(wǎng)絡(luò)的基本概念與模型例如:在一個(gè)人群中,對相互認(rèn)識這個(gè)關(guān)系我們可以用圖來表示。(v7)陳(v6)吳(v2)錢李(v2)錢孫(v3)李(v)周(vs)吳(v6)可見圖論中的圖與幾何圖、工程圖是不一樣的?！?圖與網(wǎng)絡(luò)的基本概念如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識”的關(guān)系,那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了,這是我們引入一個(gè)帶箭頭的聯(lián)線,稱為弧。圖11-3就是一個(gè)反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。()錢(v1)a14a15李(v3)孫(V7)陳(s)大10(V6吳周6圖113圖與網(wǎng)絡(luò)的基本概念與模型定義:圖中的點(diǎn)用V表示,邊用e表示。對每條邊可用它所連接的點(diǎn)表示,記作:e1=[1,1:e2=Ⅳ1V2】Q端點(diǎn)關(guān)聯(lián)邊相鄰若有邊可表示為e={vy,稱和y是邊e的端點(diǎn),反之稱邊e為點(diǎn)v或v的關(guān)聯(lián)邊。若點(diǎn)"與同一條邊關(guān)聯(lián),稱點(diǎn)v和y相鄰;若邊和具有公共的端點(diǎn),稱邊e和e相鄰。圖與網(wǎng)絡(luò)的基本概念與模型φ環(huán)多重邊簡單圖如果邊e的兩個(gè)端點(diǎn)相重,稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條,稱為多重邊,如右圖中的e4和e5,對無環(huán)、無多重邊的圖稱作簡單圖。圖與網(wǎng)絡(luò)的基本概念與模型鏈,圈,連通圖(P231圖中某些點(diǎn)和邊的交替序列,若其中各邊互不相同,且對任意v-1,Vi和ⅵ+1均相鄰稱為鏈。用p表示u=vo,e,V,,A,ek,Vk起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對頂點(diǎn)之間至少存在一條鏈,稱這樣的圖為連通圖,否則稱圖不連通。圖與網(wǎng)絡(luò)的基本概念與模型網(wǎng)絡(luò)(賦權(quán)圖)(P232設(shè)圖G=(V,E),對G的每一條邊(vj)相應(yīng)賦予數(shù)量指標(biāo)w,w稱為邊(ⅵ,v的權(quán)賦予權(quán)的圖