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

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

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

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

5、為無向圖（也簡稱圖）。,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,基 本 概 念,如果一個圖D是由點及弧所構(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)（邊與點的關(guān)系）：若e是v1、v2兩點間 的邊，

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