運(yùn)籌學(xué)課件 51圖論

第五章第五章圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析圖是最直觀圖是最直觀的模型的模型引言引言圖論的起源和發(fā)展圖論的起源和發(fā)展加里寧格勒加里寧格勒普雷格河普雷格河？這個(gè)問題看起來似乎不難，但人們始終沒有能找到答案，最這個(gè)問題看起來似乎不難，但人們始終沒有能找到答案，最后問題提到了瑞士大數(shù)學(xué)家歐拉那里。歐拉以深邃的洞察力后問題提到了瑞士大數(shù)學(xué)家歐拉那里。歐拉以深邃的洞察力很快證明了很快證明了郵冊郵冊LeonhardEuler(1707-1783)“圖論之父圖論之父”From a German stampSwissFrom a Russian stampGermanGerman陸地看作陸地看作4個(gè)節(jié)個(gè)節(jié)點(diǎn)，橋看作點(diǎn)，橋看作7條條邊作邊作圖圖是否可以是否可以一筆畫？一筆畫？35332421331u一次走完所有的橋，不重復(fù)，除起點(diǎn)與終點(diǎn)外，其余一次走完所有的橋，不重復(fù)，除起點(diǎn)與終點(diǎn)外，其余點(diǎn)必須有偶數(shù)條邊，所以七橋問題無解。點(diǎn)必須有偶數(shù)條邊，所以七橋問題無解。u 18751875年年,B,B與與C C 之間新建了一條橋解決了該問題！之間新建了一條橋解決了該問題！歐拉歐拉把七橋問題概括為數(shù)學(xué)模型，開啟了數(shù)學(xué)圖論把七橋問題概括為數(shù)學(xué)模型，開啟了數(shù)學(xué)圖論,將圖將圖抽象為頂點(diǎn)與邊的集合。抽象為頂點(diǎn)與邊的集合。u圖論是網(wǎng)絡(luò)研究的基礎(chǔ)圖論是網(wǎng)絡(luò)研究的基礎(chǔ)18561856年，英國數(shù)學(xué)家年，英國數(shù)學(xué)家哈密爾頓哈密爾頓HamiltonianHamiltonian 由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都由于運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化為哈密頓問題，從而引起廣泛的注意和研究。可以化為哈密頓問題，從而引起廣泛的注意和研究。發(fā)明發(fā)明“環(huán)球旅行環(huán)球旅行”游戲游戲 十二面體的十二面體的2020個(gè)頂點(diǎn)代表世界上個(gè)頂點(diǎn)代表世界上2020個(gè)城市，個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？城市恰好一次最后回到出發(fā)點(diǎn)？即即“環(huán)球旅行環(huán)球旅行”?！八纳孪胨纳孪搿眴栴}（問題（18521852年年）:圖論的歷史上最具有傳圖論的歷史上最具有傳奇色彩的問題奇色彩的問題歷史上許許多多數(shù)學(xué)猜想之一。歷史上許許多多數(shù)學(xué)猜想之一。人們在長期為地圖人們在長期為地圖(平面圖平面圖)上色時(shí)發(fā)現(xiàn)，對任何一上色時(shí)發(fā)現(xiàn)，對任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國家染不同的顏色，張地圖進(jìn)行著色，兩個(gè)共同邊界的國家染不同的顏色，則只需要四種顏色就夠了則只需要四種顏色就夠了.四色猜想的證明一直沒有解決，直到一百多年后，四色猜想的證明一直沒有解決，直到一百多年后，在計(jì)算機(jī)出現(xiàn)以后，于在計(jì)算機(jī)出現(xiàn)以后，于19761976年用計(jì)算機(jī)算了年用計(jì)算機(jī)算了12001200多小多小時(shí)，才證明了四色猜想問題。時(shí)，才證明了四色猜想問題。02013118471847年，德國物理學(xué)家年，德國物理學(xué)家kirchhoffkirchhoff，發(fā)表了關(guān)于發(fā)表了關(guān)于“樹樹”的第一篇論文，電網(wǎng)絡(luò)的第一篇論文，電網(wǎng)絡(luò)中的求解聯(lián)立方程的問題中的求解聯(lián)立方程的問題18571857年，英國數(shù)學(xué)家年，英國數(shù)學(xué)家A.GayleyA.Gayley，“樹樹”，有機(jī)化合物的分子結(jié)構(gòu)中的同分異，有機(jī)化合物的分子結(jié)構(gòu)中的同分異構(gòu)問題構(gòu)問題凱萊凱萊1964年，華羅庚，年，華羅庚，統(tǒng)籌方法平話統(tǒng)籌方法平話。1956年，杜邦公司，年，杜邦公司，CPM，關(guān)鍵路線法；關(guān)鍵路線法；1958年，美國海軍部，年，美國海軍部，PERT，計(jì)劃評審技術(shù)；計(jì)劃評審技術(shù)；1962年，管梅谷，年，管梅谷，中國郵路問題中國郵路問題；1936年，匈牙利數(shù)學(xué)家哥尼格發(fā)表了第一本圖論專著年，匈牙利數(shù)學(xué)家哥尼格發(fā)表了第一本圖論專著有限圖有限圖與無限圖的理論與無限圖的理論20世紀(jì)世紀(jì)50年代年代圖論形成了兩個(gè)本質(zhì)上不同的發(fā)展方向圖論形成了兩個(gè)本質(zhì)上不同的發(fā)展方向圖論的代數(shù)方向圖論的代數(shù)方向圖論的最優(yōu)化方向圖論的最優(yōu)化方向圖的用處圖的用處n 圖則是一種直觀的模型，如公路、鐵路交通圖，通訊網(wǎng)圖則是一種直觀的模型，如公路、鐵路交通圖，通訊網(wǎng)絡(luò)圖等。絡(luò)圖等。n圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極圖論與網(wǎng)絡(luò)分析理論所研究的問題十分廣泛，內(nèi)容極其豐富。正如一位數(shù)學(xué)家所說：其豐富。正如一位數(shù)學(xué)家所說：“可以說，圖論為任何可以說，圖論為任何一個(gè)一個(gè)包含了某種二元關(guān)系包含了某種二元關(guān)系的系統(tǒng)提供了一種分析和描述的系統(tǒng)提供了一種分析和描述的模型。的模型?！睂ο蠹捌渎?lián)系對象及其聯(lián)系n在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从逞芯繉ο笾g在實(shí)際的生產(chǎn)和生活中，人們?yōu)榱朔从逞芯繉ο笾g的特定關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的的特定關(guān)系，常常在紙上用點(diǎn)和線來畫出各式各樣的示示意圖意圖。這就是圖論中的。這就是圖論中的“圖圖”，圖中的相對位置如何，圖中的相對位置如何，點(diǎn)與點(diǎn)之間線的長短曲直，對于反映研究對象之間的關(guān)點(diǎn)與點(diǎn)之間線的長短曲直，對于反映研究對象之間的關(guān)系，顯的并不重要。因此，圖論中的圖與幾何圖，工程系，顯的并不重要。因此，圖論中的圖與幾何圖，工程圖等本質(zhì)上是不同的。圖等本質(zhì)上是不同的。例例是北京、上海等十個(gè)城市間的鐵路交通圖。與此類似的還是北京、上海等十個(gè)城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。有電話線分布圖、煤氣管道圖、航空路線圖等。北京北京天津天津濟(jì)南濟(jì)南青島青島武漢武漢南京南京上海上海鄭州鄭州連云港連云港徐州徐州網(wǎng)絡(luò)結(jié)構(gòu)InternetDNS、內(nèi)網(wǎng)內(nèi)網(wǎng)WWW服務(wù)器服務(wù)器外網(wǎng)外網(wǎng)WWW服務(wù)器服務(wù)器樓層交換機(jī)樓層交換機(jī)防火墻防火墻網(wǎng)管工作站網(wǎng)管工作站OA骨干交換機(jī)骨干交換機(jī)樓層交換機(jī)樓層交換機(jī)用戶工作站用戶工作站CISCO路由器路由器骨干交換機(jī)骨干交換機(jī)PSTN移動辦公移動辦公DCN其它部門OA、EMAIL主機(jī)主機(jī)例例3“染色問題染色問題”儲存化學(xué)藥品可能因放太近易發(fā)生反應(yīng)而爆炸，其中某儲存化學(xué)藥品可能因放太近易發(fā)生反應(yīng)而爆炸，其中某些藥品不能存放在同一個(gè)庫房里。若我們想知道，最多有多些藥品不能存放在同一個(gè)庫房里。若我們想知道，最多有多少種化學(xué)品能存放在同一個(gè)庫房里。少種化學(xué)品能存放在同一個(gè)庫房里。碰!內(nèi)容框架內(nèi)容框架 一、一、圖的基本概念圖的基本概念（討論思路（討論思路）G=G=（V V，E E）子圖子圖含含元素的個(gè)數(shù)元素的個(gè)數(shù)點(diǎn)的次點(diǎn)的次邊邊特殊的圖特殊的圖點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系簡簡單單圖圖多多重重圖圖連通圖連通圖樹樹部分樹部分樹ji4312 圖：圖：由點(diǎn)及點(diǎn)之間的連線所組成。由點(diǎn)及點(diǎn)之間的連線所組成。點(diǎn)：表示所研究的對象，點(diǎn)的集合點(diǎn)：表示所研究的對象，點(diǎn)的集合V表示，表示，V=vi連線：表示對象間的特定關(guān)系，用兩點(diǎn)連線：表示對象間的特定關(guān)系，用兩點(diǎn)vi，vj表示表示E-邊集合，邊集合，E=ekek=vi,vjjiA弧集合，弧集合，A=akak=vi,vj4312無向圖無向圖G=（V，E）有向圖有向圖D=（V，A）Vv1、v2、v3、v4Ee1、e2、e3、e4、e5、e6、e7并且：并且：e1（v1、v2）e2（v1、v3）e3（v1、v4）e4（v2、v3）e5（v2、v3）e6（v2、v4）e7（v3、v4）V v1、v2、v3、v4 A a1、a2、a3、a4、a5、a6、a7并且：并且：a 1（v1、v2）a2（v1、v3）a3（v1、v4）a4（v2、v3）a 5（v2、v3）a6（v2、v4）a7（v3、v4）端點(diǎn)端點(diǎn)例：球隊(duì)比賽圖例：球隊(duì)比賽圖ABCDE 有有A、B、C、D、E 五個(gè)球隊(duì)舉行比賽，已知五個(gè)球隊(duì)舉行比賽，已知A隊(duì)與其它各隊(duì)與其它各隊(duì)都比賽過一次；隊(duì)都比賽過一次；B隊(duì)和隊(duì)和A、C 隊(duì)比賽過；隊(duì)比賽過；C隊(duì)和隊(duì)和A、B、D 隊(duì)賽隊(duì)賽過；過；D隊(duì)和隊(duì)和A、C、E比賽過；比賽過；E隊(duì)和隊(duì)和A、D 隊(duì)比賽過。隊(duì)比賽過。點(diǎn)：表示球隊(duì)點(diǎn)：表示球隊(duì)連線：表示兩球隊(duì)間比賽過連線：表示兩球隊(duì)間比賽過 比賽結(jié)果是：比賽結(jié)果是：A隊(duì)勝了隊(duì)勝了B、D、E隊(duì)；隊(duì)；B隊(duì)勝了隊(duì)勝了C隊(duì)；隊(duì)；C隊(duì)勝了隊(duì)勝了A、D隊(duì)；隊(duì)；D隊(duì)沒有勝過；隊(duì)沒有勝過；E隊(duì)勝了隊(duì)勝了D隊(duì)；隊(duì)；箭連線：箭尾表示獲勝球隊(duì)箭連線：箭尾表示獲勝球隊(duì)A隊(duì)三勝一負(fù)隊(duì)三勝一負(fù)B隊(duì)一勝一負(fù)隊(duì)一勝一負(fù)C隊(duì)兩勝一負(fù)隊(duì)兩勝一負(fù)D隊(duì)三戰(zhàn)三負(fù)隊(duì)三戰(zhàn)三負(fù)E隊(duì)一勝一負(fù)隊(duì)一勝一負(fù)G=G=（V V，E E）子圖子圖含含元素的個(gè)數(shù)元素的個(gè)數(shù)點(diǎn)的次點(diǎn)的次點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系連通圖連通圖樹樹邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹邊邊l l關(guān)聯(lián)邊關(guān)聯(lián)邊關(guān)聯(lián)邊關(guān)聯(lián)邊：和同一個(gè)端點(diǎn)相連和同一個(gè)端點(diǎn)相連的邊的邊,稱為該點(diǎn)的關(guān)聯(lián)邊稱為該點(diǎn)的關(guān)聯(lián)邊l l環(huán)環(huán)環(huán)環(huán)：兩個(gè)端點(diǎn)相同的兩個(gè)端點(diǎn)相同的邊邊l l多重邊：多重邊：多重邊：多重邊：兩個(gè)端點(diǎn)之間的邊兩個(gè)端點(diǎn)之間的邊數(shù)數(shù)2l l多重圖：多重圖：多重圖：多重圖：一個(gè)無環(huán)、但允許一個(gè)無環(huán)、但允許有多重邊的圖有多重邊的圖l l簡單圖：簡單圖：簡單圖：簡單圖：一個(gè)無環(huán)，無多重一個(gè)無環(huán)，無多重邊的圖邊的圖v1v2v3v4e1e2e3e4e5e6e7 G=G=（V V，E E）子圖子圖含含元素的個(gè)數(shù)元素的個(gè)數(shù)點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系連通圖連通圖樹樹點(diǎn)的次點(diǎn)的次邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹點(diǎn)點(diǎn)l l次次次次：一個(gè)端點(diǎn)一個(gè)端點(diǎn)v具有具有關(guān)聯(lián)邊的總數(shù)，記作關(guān)聯(lián)邊的總數(shù)，記作d(v)（每個(gè)環(huán)視作兩條邊）（每個(gè)環(huán)視作兩條邊）l l懸掛點(diǎn)：懸掛點(diǎn)：懸掛點(diǎn)：懸掛點(diǎn)：次為次為1的點(diǎn)的點(diǎn)l l懸掛邊：懸掛邊：懸掛邊：懸掛邊：懸掛點(diǎn)的關(guān)聯(lián)邊懸掛點(diǎn)的關(guān)聯(lián)邊l l孤立點(diǎn)：孤立點(diǎn)：孤立點(diǎn)：孤立點(diǎn)：次為次為0的點(diǎn)的點(diǎn)l l偶偶偶偶點(diǎn)：點(diǎn)：點(diǎn)：點(diǎn)：次為偶數(shù)的點(diǎn)次為偶數(shù)的點(diǎn)l l奇奇奇奇點(diǎn)：點(diǎn)：點(diǎn)：點(diǎn)：次為奇數(shù)的點(diǎn)次為奇數(shù)的點(diǎn)v1v2v3v4e1e2e3e4e5e6e7v5e8d(v4)=d(v2)=54v6兩個(gè)主要定理兩個(gè)主要定理定理定理定理定理1 1圖圖G中，所有頂點(diǎn)的次的和等于所有中，所有頂點(diǎn)的次的和等于所有邊數(shù)的邊數(shù)的2倍。即倍。即定理定理定理定理2 2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。證明要點(diǎn)：證明要點(diǎn)：（V1、V2分別是圖分別是圖G中次為奇數(shù)和偶數(shù)的頂點(diǎn)集合）中次為奇數(shù)和偶數(shù)的頂點(diǎn)集合）G=G=（V V，E E）子圖子圖含含元素的個(gè)數(shù)元素的個(gè)數(shù)點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系連通圖連通圖樹樹點(diǎn)的次點(diǎn)的次邊邊特殊的圖特殊的圖簡簡單單圖圖多多重重圖圖部分樹部分樹 母圖和子圖母圖和子圖l l子子子子圖：圖：圖：圖：設(shè)設(shè)G1=（V1,E1），），G2=（V2,E2）如果如果V2 V1,E2 E1稱稱G2是是G1的子圖的子圖l l支撐子圖：支撐子圖：支撐子圖：支撐子圖：如果如果V2=V1,E2 E1稱稱G2是是G1的部分圖或支的部分圖或支撐子圖撐子圖l l導(dǎo)出子圖（導(dǎo)出子圖（導(dǎo)出子圖（導(dǎo)出子圖（G-vG-v）：圖圖G去掉點(diǎn)去掉點(diǎn)v及及v的關(guān)聯(lián)邊的圖的關(guān)聯(lián)邊的圖.注意部分圖部分圖子圖子圖V4母圖母圖G1V1V2V3V5V6子圖子圖G2導(dǎo)出子圖導(dǎo)出子圖G-V6支撐子圖支撐子圖G2V2V1例：子圖例：子圖基礎(chǔ)圖基礎(chǔ)圖(母圖母圖)部分圖部分圖導(dǎo)出子圖導(dǎo)出子圖子圖子圖G=(V,E)邊邊e=u,v 關(guān)聯(lián)邊關(guān)聯(lián)邊 端點(diǎn)端點(diǎn) 重重重重合合合合環(huán)環(huán)自自自自回回回回路路路路多重邊多重邊平行邊平行邊平行邊平行邊多于多于1條邊條邊簡單圖簡單圖不含不含不含不含多重圖多重圖含含含含點(diǎn)的次點(diǎn)的次點(diǎn)的次點(diǎn)的次 01奇數(shù)奇數(shù)偶數(shù)偶數(shù)子圖子圖孤孤立立點(diǎn)點(diǎn)懸懸掛掛點(diǎn)點(diǎn)奇奇點(diǎn)點(diǎn)偶偶點(diǎn)點(diǎn)懸掛邊懸掛邊頂點(diǎn)數(shù)頂點(diǎn)數(shù)p邊數(shù)邊數(shù)q點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系各種鏈的概念各種鏈的概念子子圖圖支支撐撐子子圖圖導(dǎo)導(dǎo)出出子子圖圖二、二、圖的連通性圖的連通性（討論思路（討論思路）點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系各種鏈、路的概念各種鏈、路的概念通路通路樹樹(6個(gè)等價(jià)定義個(gè)等價(jià)定義)連通圖連通圖 鏈鏈一個(gè)點(diǎn)、邊交替的連續(xù)序列一個(gè)點(diǎn)、邊交替的連續(xù)序列=vi1,ei1,vi2,ei2,vikl l簡單鏈：簡單鏈：簡單鏈：簡單鏈：若鏈中各邊均不同若鏈中各邊均不同l l初等鏈：初等鏈：初等鏈：初等鏈：若鏈中各點(diǎn)均不同若鏈中各點(diǎn)均不同l l圈圈圈圈:起點(diǎn)和終點(diǎn)重合的鏈，起點(diǎn)和終點(diǎn)重合的鏈，即閉合的鏈即閉合的鏈l l初等圈：初等圈：初等圈：初等圈：若圈中各點(diǎn)均不同若圈中各點(diǎn)均不同l l簡單圈：簡單圈：簡單圈：簡單圈：若圈中各邊均不同若圈中各邊均不同 注意圈圈鏈鏈簡單鏈簡單鏈初等鏈初等鏈初等圈初等圈路：路：若鏈若鏈中每條弧的方向一致，則稱中每條弧的方向一致，則稱為路為路l l初等路：初等路：初等路：初等路：若路中各點(diǎn)均不同若路中各點(diǎn)均不同l l簡單路：簡單路：簡單路：簡單路：若路中各邊均不同若路中各邊均不同l l回路回路回路回路:起點(diǎn)和終點(diǎn)重合即閉合的路起點(diǎn)和終點(diǎn)重合即閉合的路l l初等回路：初等回路：初等回路：初等回路：若回路中各點(diǎn)均不同若回路中各點(diǎn)均不同l l簡單回路：簡單回路：簡單回路：簡單回路：若回路中各邊均不同若回路中各邊均不同v1v2v3v4e1e2e3e4e5e6注意v1,e1,v2,e3,v3v1,e2,v2,e3,v3v1,e2,v2,e1,v1 鏈鏈路路 路（通路）路（通路）初等路初等路簡單路簡單路各邊不同各邊不同各點(diǎn)不同各點(diǎn)不同起點(diǎn)起點(diǎn) 終點(diǎn)終點(diǎn)=回路回路初等回路初等回路簡單回路簡單回路各邊不同各邊不同各點(diǎn)不同各點(diǎn)不同連通：連通：在圖中，若頂點(diǎn)在圖中，若頂點(diǎn)vi與與vj之間存在鏈，則稱之間存在鏈，則稱vi與與vj是是連通的連通的。l l規(guī)規(guī)規(guī)規(guī)定：定：定：定：v vi i與自身是連通的與自身是連通的l l連通圖：連通圖：連通圖：連通圖：在圖中，任意兩點(diǎn)間至少存在著一條鏈；在圖中，任意兩點(diǎn)間至少存在著一條鏈；否則，為不連通圖。否則，為不連通圖。點(diǎn)邊關(guān)系點(diǎn)邊關(guān)系子子圖圖支支撐撐子子圖圖導(dǎo)導(dǎo)出出子子圖圖各種鏈的概念各種鏈的概念通路通路樹樹(6個(gè)等價(jià)定義個(gè)等價(jià)定義)連通圖連通圖 支撐樹支撐樹例例1 1：電話線網(wǎng)：電話線網(wǎng)已已知知有有六六個(gè)個(gè)城城市市，它它們們之之間間要要架架設(shè)設(shè)電電話話線線，要要求求任任意意兩兩個(gè)個(gè)城城市市均均可可以以互互相相通通話話，并并且且電電話話線的總長度最短。線的總長度最短。v1v2v3v4v5v6三、三、樹樹例例2 2：通訊網(wǎng)絡(luò)：通訊網(wǎng)絡(luò)例例3 3：紅樓夢紅樓夢中賈府人物之間的血統(tǒng)關(guān)系樹中賈府人物之間的血統(tǒng)關(guān)系樹賈演賈演賈源賈源賈代化賈代化賈代善賈代善賈放賈放賈敷賈敷賈珍賈珍賈蓉賈蓉賈赦賈赦賈政賈政賈璉賈璉賈寶玉賈寶玉賈環(huán)賈環(huán)賈珠賈珠賈蘭賈蘭（寧國府）（寧國府）（榮國府）（榮國府）例例4 4 某工廠的組織機(jī)構(gòu)如下圖所示某工廠的組織機(jī)構(gòu)如下圖所示廠廠長長行行政政辦辦公公室室生生產(chǎn)產(chǎn)辦辦公公室室生產(chǎn)計(jì)劃科生產(chǎn)計(jì)劃科技術(shù)科技術(shù)科設(shè)計(jì)組設(shè)計(jì)組工藝組工藝組供銷科供銷科財(cái)務(wù)科財(cái)務(wù)科行政科行政科車間車間鑄造工段鑄造工段鍛壓工段鍛壓工段二二車間車間三車間三車間四車間四車間該廠的該廠的組織機(jī)構(gòu)圖就是一個(gè)樹。組織機(jī)構(gòu)圖就是一個(gè)樹。樹：樹：無圈的連通圖，記作無圈的連通圖，記作Tl l性質(zhì)性質(zhì)性質(zhì)性質(zhì)l樹是邊數(shù)最多的樹是邊數(shù)最多的無圈無圈連通圖。連通圖。在樹中任加一條邊，就會形成在樹中任加一條邊，就會形成圈。圈。l樹是邊數(shù)最少的連通圖。樹是邊數(shù)最少的連通圖。n n 個(gè)個(gè)頂點(diǎn)的樹必有頂點(diǎn)的樹必有n-1 n-1 條邊條邊l在樹中任減一條邊，則不連通。在樹中任減一條邊，則不連通。d=1d=1葉子葉子葉子葉子d1d1分支點(diǎn)分支點(diǎn)分支點(diǎn)分支點(diǎn)l l 生成樹（支撐樹）：生成樹（支撐樹）：生成樹（支撐樹）：生成樹（支撐樹）：當(dāng)連通圖當(dāng)連通圖G=(V,E)的部分子圖為樹的部分子圖為樹T，則稱，則稱T為為G的的支撐樹，記作支撐樹，記作T=(V,E),其中其中E包含于包含于El 一個(gè)圖一個(gè)圖G 有生成樹的充要條件是有生成樹的充要條件是G 是連通圖。是連通圖。4231如何尋找如何尋找“支撐樹支撐樹”呢呢？網(wǎng)絡(luò)：網(wǎng)絡(luò)：規(guī)定了起點(diǎn)、終點(diǎn)和中間點(diǎn)的賦權(quán)圖規(guī)定了起點(diǎn)、終點(diǎn)和中間點(diǎn)的賦權(quán)圖l l權(quán)：權(quán)：權(quán)：權(quán)：邊邊e或弧或弧a上賦有的實(shí)數(shù)上賦有的實(shí)數(shù)wlw-根據(jù)實(shí)際背景可賦予不同含義，如距離、時(shí)間、費(fèi)用、根據(jù)實(shí)際背景可賦予不同含義，如距離、時(shí)間、費(fèi)用、容量等。容量等。l l賦權(quán)圖：賦權(quán)圖：賦權(quán)圖：賦權(quán)圖：圖圖G連同邊或弧上的權(quán)總體。連同邊或弧上的權(quán)總體。l l有向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、有向網(wǎng)絡(luò)、四、四、網(wǎng)絡(luò)網(wǎng)絡(luò)4231221543權(quán)權(quán)wij(dij)無向網(wǎng)絡(luò)、無向網(wǎng)絡(luò)、無向網(wǎng)絡(luò)、無向網(wǎng)絡(luò)、混合網(wǎng)絡(luò)混合網(wǎng)絡(luò)混合網(wǎng)絡(luò)混合網(wǎng)絡(luò)所謂所謂網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析:對網(wǎng)絡(luò)進(jìn)行定性和定量分析，以對網(wǎng)絡(luò)進(jìn)行定性和定量分析，以便為實(shí)現(xiàn)某種優(yōu)化目標(biāo)而尋求最優(yōu)方案便為實(shí)現(xiàn)某種優(yōu)化目標(biāo)而尋求最優(yōu)方案v 最短路問題最短路問題v 最大流問題最大流問題v 最小費(fèi)用最大流問題最小費(fèi)用最大流問題v 最短樹問題最短樹問題v 中心與重心問題中心與重心問題v 網(wǎng)絡(luò)計(jì)劃問題網(wǎng)絡(luò)計(jì)劃問題 5-2.最最短短路路問問題題圖中兩個(gè)頂點(diǎn)之間有圖中兩個(gè)頂點(diǎn)之間有 條路徑條路徑最短路徑：最短路徑：最短路徑：最短路徑：是路徑中邊（?。┑臋?quán)值總和最小的路徑是路徑中邊（弧）的權(quán)值總和最小的路徑一、問題的提法及應(yīng)用背景一、問題的提法及應(yīng)用背景多多多多一般提法為：設(shè)一般提法為：設(shè) 為連通圖，圖中各邊為連通圖，圖中各邊 有權(quán)有權(quán) （表示表示 之間沒有邊），之間沒有邊），為圖中任意兩點(diǎn)，求一條路為圖中任意兩點(diǎn)，求一條路 ，使它為從，使它為從 到到 的所有路中總權(quán)最小。即：的所有路中總權(quán)最小。即：應(yīng)用背景：應(yīng)用背景：應(yīng)用背景：應(yīng)用背景：某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題可以歸結(jié)為某些整數(shù)規(guī)劃和動態(tài)規(guī)劃問題可以歸結(jié)為求最短路的問題。求最短路的問題。l管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。管道鋪設(shè)、線路安排、廠區(qū)布局、設(shè)備更新等。一、什么是最短路問題？在連通圖中，尋找一條從始點(diǎn)到終點(diǎn)的路，該路的權(quán)之和最小。二、最短路算法：狄克斯屈拉算法二、最短路算法：狄克斯屈拉算法D D氏標(biāo)號法（氏標(biāo)號法（氏標(biāo)號法（氏標(biāo)號法（DijkstraDijkstra，荷蘭人，荷蘭人，荷蘭人，荷蘭人）-雙標(biāo)號法雙標(biāo)號法雙標(biāo)號法雙標(biāo)號法,1959,1959,1959,1959年年年年l基本思路：基本思路：基本思路：基本思路：如果如果v1v2v3v4是是v1v4的最短路的最短路徑，則徑，則v1v2v3一定是一定是v1v3的最短路徑。的最短路徑。v2v3v4一定是一定是v2v4的最短路徑。的最短路徑。從始點(diǎn)出發(fā)，從始點(diǎn)出發(fā)，逐步逐步順序地順序地向外探尋向外探尋，每向外延伸一步每向外延伸一步都要求是最短的。都要求是最短的。使用線性規(guī)劃的解法，但不能利用最短路問題的特點(diǎn)，使解法更有效。利用動態(tài)規(guī)劃的思路，即對于在始點(diǎn)到終點(diǎn)的總體最短路徑上的任意一點(diǎn)，從始點(diǎn)到該點(diǎn)的最短路在總體最短路徑上。根據(jù)上述第二點(diǎn)，可以用標(biāo)號法求解。S247l 選用標(biāo)號的意義選用標(biāo)號的意義：從始點(diǎn)到該節(jié)點(diǎn)的距離從始點(diǎn)到該節(jié)點(diǎn)的距離 標(biāo)號標(biāo)號 P P（固定標(biāo)號或永久性標(biāo)號）：固定標(biāo)號或永久性標(biāo)號）：從始從始點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)點(diǎn)到該標(biāo)號點(diǎn)的最短路權(quán)。標(biāo)號標(biāo)號 T T（臨時(shí)性標(biāo)號）：臨時(shí)性標(biāo)號）：從始點(diǎn)到該標(biāo)號從始點(diǎn)到該標(biāo)號點(diǎn)的路權(quán)點(diǎn)的路權(quán)。l l 使用條件使用條件 網(wǎng)絡(luò)中網(wǎng)絡(luò)中所有的弧權(quán)所有的弧權(quán)均均 非負(fù)非負(fù)，即，即 。算法的每一步：算法的每一步：標(biāo)號標(biāo)號 T T 標(biāo)號標(biāo)號 P P計(jì)算步驟及例計(jì)算步驟及例：1234567252315317557（1 1）標(biāo)號：）標(biāo)號：首先給首先給1以以P標(biāo)號，標(biāo)號，P(P(1)0 0，給給其余所有點(diǎn)其余所有點(diǎn)T標(biāo)號，標(biāo)號，T(vj)（j=2=2，3 3，7)7)(0)+（2）計(jì)算）計(jì)算T標(biāo)號：標(biāo)號：找與找與P標(biāo)號標(biāo)號的點(diǎn)相鄰的的點(diǎn)相鄰的T標(biāo)號標(biāo)號點(diǎn)，點(diǎn)，T(vj)=minT(vj)，P(vi)+wij（3）修改）修改T為為P：比較所有比較所有T標(biāo)號標(biāo)號點(diǎn)，點(diǎn)，T(vk)=minT(vj)，T(vk)T(vk)（4）重復(fù)）重復(fù)23步：步：全部點(diǎn)為全部點(diǎn)為P標(biāo)號，標(biāo)號，結(jié)束結(jié)束(2)2 25 53 39 94 4(3)8 8(4)7 7(7)+8 81414(8)(13)在在在在得得得得到到到到從從從從起起起起點(diǎn)點(diǎn)點(diǎn)點(diǎn)到到到到終終終終點(diǎn)點(diǎn)點(diǎn)點(diǎn)的的的的最最最最短短短短路路路路長長長長的的的的同同同同時(shí)時(shí)時(shí)時(shí)，還還還還能得到什麼附加信息能得到什麼附加信息能得到什麼附加信息能得到什麼附加信息？能能得得到到從從（起起點(diǎn)點(diǎn)）到到各各點(diǎn)點(diǎn)的的最最短短路線和最短路長。路線和最短路長。521658289972212102527 5111212105756 679 910106 3 3大家知道，法求最短路只適應(yīng)于權(quán) 0的情況，當(dāng)網(wǎng)絡(luò)中出現(xiàn)負(fù)權(quán)時(shí)，此法失效，如：一。帶負(fù)權(quán)的最短路問題：求 到 的最短路。下面通過例子來說明帶負(fù)權(quán)的網(wǎng)絡(luò)的最短路求法：逐次逼近法：1給標(biāo)號 （0）。畫弧。給 劃成彩線。劃第二個(gè)弧。給 標(biāo)號（-3）。給 劃成彩線。劃第三個(gè)弧。給 標(biāo)號（1）。給 劃成彩線。劃第四個(gè)弧。給 標(biāo)號（2）。給 劃成彩線。劃第五個(gè)弧。給 再次標(biāo)號（0）。去掉 彩線。分別給 劃成彩線。劃第六個(gè)弧。分別給 標(biāo)號（6）。給 劃成彩線。劃第七個(gè)弧。給 標(biāo)號（10）。給 劃成彩線。到達(dá) 已經(jīng)無負(fù)權(quán)，路程不可能再減少。給 標(biāo)號（9）。最短路徑為：距離：10。Ford算法Dijkstra算法不適用于負(fù)權(quán)網(wǎng)絡(luò)具有負(fù)權(quán)的網(wǎng)絡(luò)，應(yīng)當(dāng)用Ford（福特，美國人）算法，逐次逼近算法逐次逼近算法又叫修正標(biāo)號法修正標(biāo)號法的特點(diǎn)是：不但最小T標(biāo)號應(yīng)當(dāng)改為P標(biāo)號，P標(biāo)號也可以修改，修改后的P標(biāo)號再次改為T表好。算法的基本思路是：算法的基本思路是：v1到到vj的最短路總是沿著該路的最短路總是沿著該路從從v1先到達(dá)某一點(diǎn)先到達(dá)某一點(diǎn)vi，然后再沿邊（，然后再沿邊（vi，vj）達(dá)到達(dá)到vi，則，則v1到到vi的這條路必然也是的這條路必然也是v1到到vi的的最短路。若令最短路。若令P1j表示從表示從v1到到vj的最短路長，則的最短路長，則必有如下方程：必有如下方程：P1j=min（P1i+lij）采用迭代方法解上述方程。采用迭代方法解上述方程。（1）開始時(shí)令開始時(shí)令 P（1）1j=l1j（j=1，2，n），即以），即以v1 到到 vj 的直接距離的直接距離（經(jīng)過一步）做初始解，若（經(jīng)過一步）做初始解，若v1 與與 vj 間無邊，間無邊，則記則記 l1j=+。（2）從第二步起，使用從第二步起，使用迭代公式迭代公式 P（k）1j=min（P（k-1）1i+lij）（k=2，3，）當(dāng)進(jìn)行到第當(dāng)進(jìn)行到第 t 步時(shí)，若出現(xiàn)步時(shí)，若出現(xiàn) P（t）1j=P（t-1）1j，則算法停止，則算法停止，P（t）1j（對一切（對一切 j）即為）即為v1 到各到各點(diǎn)的最短路長點(diǎn)的最短路長當(dāng)進(jìn)行到第當(dāng)進(jìn)行到第 n 步時(shí)，若仍有步時(shí)，若仍有 P（n）1j P（n-1）1j，（對一切，（對一切 j），則算法停止，），則算法停止，此時(shí)可知網(wǎng)絡(luò)中含有負(fù)回路。此時(shí)可知網(wǎng)絡(luò)中含有負(fù)回路。Ford算法算例情形二：賦權(quán)有向圖中存在具有負(fù)權(quán)的弧情形二：賦權(quán)有向圖中存在具有負(fù)權(quán)的弧v1v2v3v4v5v6v7v8例例:求求v1到圖中其他各點(diǎn)的最短路。到圖中其他各點(diǎn)的最短路。6-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v4,1)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v6,0)(v4,-5)(v6,0)(v6,6)v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v1,-5)(v1,-7)(v1,-1)(v2,-3)(v4,-5)(v6,6)(v5,-4)(v7,-6)(v8,3)(v8,1)三、應(yīng)用舉例三、應(yīng)用舉例例例設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初都要決設(shè)備更新問題。某企業(yè)使用一臺設(shè)備，在每年年初都要決定是購置新設(shè)備還是繼續(xù)使用舊的。購置新設(shè)備要支付一定的定是購置新設(shè)備還是繼續(xù)使用舊的。購置新設(shè)備要支付一定的購置費(fèi)，使用舊設(shè)備則要支付維修費(fèi)。制定一個(gè)五年內(nèi)的設(shè)備購置費(fèi)，使用舊設(shè)備則要支付維修費(fèi)。制定一個(gè)五年內(nèi)的設(shè)備更新計(jì)劃，使得總支付費(fèi)用最少。更新計(jì)劃，使得總支付費(fèi)用最少。已知該設(shè)備在各年年初的價(jià)格為：已知該設(shè)備在各年年初的價(jià)格為：第一年第二年第三年第四年第五年1111121213已知使用不同時(shí)間的設(shè)備維修費(fèi)用為：已知使用不同時(shí)間的設(shè)備維修費(fèi)用為：使用年數(shù)0112233445維修費(fèi)用5681118設(shè)以設(shè)以vi(i=1,2,3,4,5)表示表示“第第i年初購進(jìn)年初購進(jìn)一臺新設(shè)備一臺新設(shè)備”這種狀態(tài)，以這種狀態(tài)，以v6表示表示“第第5年末年末”這種狀態(tài)；以弧這種狀態(tài)；以弧(vi,vj)表示表示“第第i年初購置年初購置的一臺設(shè)備一直使用到第的一臺設(shè)備一直使用到第j年初年初”這一方案，這一方案，以以wij表示這一方案所需購置費(fèi)和維修費(fèi)之和。表示這一方案所需購置費(fèi)和維修費(fèi)之和。這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可這樣，可建立本例的網(wǎng)絡(luò)模型。于是，該問題就可歸結(jié)為從圖中找出一條從歸結(jié)為從圖中找出一條從v1到到v6的最短路問題。的最短路問題。從圖中可以得出兩條最短路：從圖中可以得出兩條最短路：v1v3v6;v1v4v6v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)v1v2v3v5v6v4163022165941224130173123172318(0,0)(v1,16)(v1,22)(v1,30)(v1,41)(v3,53)(v4,53)例12/P264 設(shè)備更新問題某工廠使用一臺設(shè)備，每年年初工廠要作出決定：繼續(xù)使用，購買新的？如果繼續(xù)使用舊的，要負(fù)維修費(fèi)；若要購買一套新的，要負(fù)購買費(fèi)。試確定一個(gè)5年計(jì)劃，使總支出最小若已知設(shè)備在各年的購買費(fèi)，及不同機(jī)器役齡時(shí)的殘值與維修費(fèi)，如表所示.項(xiàng)目第1年第2年第3年第4年第5年購買費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210解：把這個(gè)問題化為最短路問題。用點(diǎn) 表示第i年初購進(jìn)一臺新設(shè)備，虛設(shè)一個(gè)點(diǎn) ，表示第5年底。邊 表示第i年購進(jìn)的設(shè)備一直使用到第j年初（即第j-1年底）。邊 上的數(shù)字表示第i年初購進(jìn)設(shè)備，一直使用到第j年初所需支付的購買費(fèi)、維修的全部費(fèi)用（可由表8-2計(jì)算得到）。這樣設(shè)備更新問題就變?yōu)椋呵髲?到 的最短路問題.給 劃成彩線。給 劃成彩線。給 劃成彩線。給 劃成彩線。給 劃成彩線。計(jì)算結(jié)果：最短路最短路路長為49。即：在第一年、第三年初各購買一臺新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。