管理科學(xué)-圖與網(wǎng)絡(luò)分析-0.ppt

1、1,第3章 圖與網(wǎng)絡(luò)分析,最 小 支 撐 樹 最 短 路 問 題 最 大 流 問 題,2,引 言,圖論是專門研究圖的理論的一門數(shù)學(xué)分支，屬于離散數(shù)學(xué)范疇，與運(yùn)籌學(xué)有交叉，它有200多年歷史，大體可劃分為三個(gè)階段。,3,引 言,第一階段是從十八世紀(jì)中葉到十九世紀(jì)中葉，處于萌芽階段，多數(shù)問題圍繞游戲而產(chǎn)生，最有代表性的工作是所謂的哥尼斯堡七橋問題，即一筆畫問題。,4,引 言,哥尼斯堡（現(xiàn)名加里寧格勒）是歐洲一個(gè)城市，普雷格爾河把該城分成兩部分，河中有兩個(gè)小島，十八世紀(jì)時(shí)，河兩邊及小島之間共有七座橋，當(dāng)時(shí)人們這樣的問題：有沒有辦法從某處（如A）出發(fā)，經(jīng)過各橋一次且僅一次最后回到原地呢？,5,引 言,

2、第二階段是從十九世紀(jì)中葉到二十世紀(jì)中葉，這時(shí)，圖論問題大量出現(xiàn)，如地圖染色的四色問題以及可平面性問題等，這時(shí)，也出現(xiàn)用圖解決實(shí)際問題，如Cayley把樹應(yīng)用于化學(xué)領(lǐng)域，Kirchhoff用樹去研究電網(wǎng)絡(luò)等.,6,引 言,7,引 言,四色問題的發(fā)現(xiàn) 1852年，剛從倫敦大學(xué)畢業(yè)的弗南希斯在對(duì)英國(guó)的地圖著色時(shí)，發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象：無論多么復(fù)雜的地圖，只需要用四種顏色就能將它區(qū)分開來，也就是說，用四種顏色著色就能保證不會(huì)有兩個(gè)相鄰地區(qū)的顏色相同。 弗南希斯將自己的發(fā)現(xiàn)告訴給哥哥弗德雷克，引起了弗德雷克的濃厚興趣，他深信弟弟所發(fā)現(xiàn)的這個(gè)結(jié)論是正確的，并企圖從數(shù)學(xué)的角度對(duì)這個(gè)結(jié)論給予證明，但所有的努力

3、都失敗了。在百思不得其解的情況下，只得專程去請(qǐng)教他的老師、英國(guó)著名的 數(shù)學(xué)家德摩根教授。摩根教授絞盡腦汁研究這個(gè)問題，可也一無所獲。后來，他將這一猜想寫信告訴了在都柏林的著名數(shù)學(xué)家哈密爾頓，于是“四色猜想”首次以 數(shù)學(xué)的形式提了出來。,8,引 言,四色問題的證明 本世紀(jì)70年代中期，美國(guó)伊利諾斯州立大學(xué)的數(shù)學(xué)家阿佩爾和哈肯獨(dú)樹一幟，利用高速計(jì)算機(jī)對(duì)“四色猜想”進(jìn)行證明。他們運(yùn)用了一種“不可避免性”理論，從一萬多張地圖中挑選了近兩千張上機(jī)檢驗(yàn)，對(duì)每一張地圖都使用了二十萬種可能的方法著色，計(jì)算機(jī)作了兩百億個(gè)邏輯判定，經(jīng)過1200小時(shí)的計(jì)算，終于在1976年6月證明了這個(gè)數(shù)學(xué)名題。伊利諾斯數(shù)學(xué)雜志的

4、審稿人，對(duì)阿佩爾與哈肯證明的審查，也是通過計(jì)算機(jī)來實(shí)現(xiàn)的。 阿佩爾與哈肯的工作，使延續(xù)了124年之久的四色問題得到證明，成為四色定理。,9,引 言,第三階段是二十世紀(jì)中葉以后，由生產(chǎn)管理、軍事、交通、運(yùn)輸、計(jì)算機(jī)網(wǎng)絡(luò)等方面提出實(shí)際問題，以及大型計(jì)算機(jī)使大規(guī)模問題的求解成為可能，特別是以Ford和Fulkerson建立的網(wǎng)絡(luò)流理論，與線性規(guī)劃、動(dòng)態(tài)規(guī)劃等優(yōu)化理論和方法相互滲透，促進(jìn)了圖論對(duì)實(shí)際問題的應(yīng)用。,10,基 本 概 念,一個(gè)圖是由一些點(diǎn)及一些點(diǎn)之間的連線（不帶箭頭或帶箭頭）所組成的。,不帶箭頭的聯(lián)線稱為邊。,帶箭頭的聯(lián)線稱為弧。,11,基 本 概 念,如果一個(gè)圖G是由點(diǎn)及邊所構(gòu)成，則稱之

5、為無向圖（也簡(jiǎn)稱圖）。,e3,e5,e6,e2,e1,e4,v3,v2,v4,v1,G=（V,E）,V=v1,v2,v3,v4,E=e1,e2,e3,e4,e5,e6,e7,12,基 本 概 念,如果一個(gè)圖D是由點(diǎn)及弧所構(gòu)成，則稱之為有向圖。,a8,a3,a4,a6,a7,a5,v4,v5,v2,v3,D=（V,A）,V=v1,v2,v3,v4,v5,v6,v7,A=a1,a2,a3,a4, a5,a6,a7 ,a8,a9,a10,v1,v7,v6,a9,a10,a1,a2,13,基 本 概 念,e1 V2 V1 e2 V3,v1 e v2,關(guān)聯(lián)（邊與點(diǎn)的關(guān)系）：若e是v1、v2兩點(diǎn)間 的邊，

6、記e=v1，v2 ，稱v1、v2 與e關(guān)聯(lián)。,相鄰（邊與邊、點(diǎn)與點(diǎn)的關(guān)系）： 點(diǎn)v1與v2有公共邊，稱點(diǎn)v1與v2相鄰； 邊e1與e2 有公共點(diǎn)，稱邊e1與e2相鄰。,14,基 本 概 念,在圖G中某個(gè)邊e的兩個(gè)端點(diǎn)相同，稱e為環(huán)。若兩個(gè)點(diǎn)之間有多于一條的邊，稱為多重邊。一個(gè)無環(huán)、無多重邊的圖稱為簡(jiǎn)單圖，一個(gè)無環(huán)、允許有多重邊的圖稱為多重圖。,e3,e5,e6,e2,e1,e4,e7,v3,v2,v4,v1,e7是環(huán),e1,e2是多重邊,15,圈（Circuit） 封閉的鏈稱為圈 如：=(1,2),(2,4),(3,4),(1,3),鏈:由圖G中的某些點(diǎn)與邊相間構(gòu)成的序列 V1,e1,V2,e2, ,Vk,ek,若滿足 ,則稱此 點(diǎn)邊序列為G中的一條鏈。 如： =(1,2),(3,2),(3,4),4,2,3,1,4,2,3,1,基 本 概 念,16,連通圖 任意兩個(gè)節(jié)點(diǎn)之間至少有一條鏈的圖稱為連通圖,4,2,3,1,網(wǎng)絡(luò),給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù)（如距離、費(fèi)用、容量等），則稱這樣的圖為網(wǎng)絡(luò)圖。,4,2,3,1,50 70 20 45,基 本 概 念,17,基