高中奧數(shù)專題——圖論

1、例1 最短路問題（SPPshortest path problem） 一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2 公路連接問題 某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？例3 運(yùn)輸問題(transportation problem

2、) 某種原材料有N個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往M個(gè)使用這些原材料的工廠。假定N個(gè)產(chǎn)地的產(chǎn)量和M家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？例4 中國郵遞員問題（CPPChinese postman problem） 一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5 旅行商問題（TSPtraveling salesman problem） 一名推銷員準(zhǔn)備前往若干城市推

3、銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。上述問題有兩個(gè)共同的特點(diǎn)： 一、 它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題； 二、 它們都易于用圖形的形式直觀地描述和表達(dá) ， 數(shù) 學(xué) 上 把 這 種 與 圖 相 關(guān) 的 結(jié) 構(gòu) 稱 為 網(wǎng) 絡(luò)（network）。 與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是。 上面例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流（flow）為研究對(duì)象，因此網(wǎng)絡(luò)優(yōu)化又常常

4、被稱為等。 98年全國大學(xué)生數(shù)學(xué)建模競(jìng)賽年全國大學(xué)生數(shù)學(xué)建模競(jìng)賽B題題“最佳災(zāi)最佳災(zāi) 今年今年(1998年年)夏天某縣遭受水災(zāi)夏天某縣遭受水災(zāi). 為考察災(zāi)情、為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視全縣各鄉(xiāng)（鎮(zhèn)）、村巡視. 巡視路線指從縣政府巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線府所在地的路線.情巡視路線情巡視路線”中的前兩個(gè)問題是這樣的：中的前兩個(gè)問題是這樣的： 1）若分三組（路）巡視，試設(shè)計(jì)總路程最）若分三組（路）巡視，試設(shè)計(jì)總路程最短

5、且各組盡可能均衡的巡視路線短且各組盡可能均衡的巡視路線. 2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間小時(shí)，在各村停留時(shí)間t =1小時(shí)，汽車行駛速度小時(shí)，汽車行駛速度V=35公里公里/小時(shí)小時(shí). 要在要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線幾組；給出這種分組下最佳的巡視路線.公路邊的數(shù)字為該路段的公里數(shù)公路邊的數(shù)字為該路段的公里數(shù). . 20082008年北京奧運(yùn)會(huì)的建設(shè)工作已經(jīng)進(jìn)入全面設(shè)計(jì)年北京奧運(yùn)會(huì)的建設(shè)工作已經(jīng)進(jìn)入全面設(shè)計(jì)和實(shí)施階段。奧運(yùn)會(huì)期間，在比賽主場(chǎng)館的周邊地區(qū)和實(shí)施階段。奧運(yùn)會(huì)期

6、間，在比賽主場(chǎng)館的周邊地區(qū)需要建設(shè)由小型商亭構(gòu)建的臨時(shí)商業(yè)網(wǎng)點(diǎn)，稱為迷你需要建設(shè)由小型商亭構(gòu)建的臨時(shí)商業(yè)網(wǎng)點(diǎn)，稱為迷你超市（超市（Mini Supermarket, Mini Supermarket, 以下記做以下記做MSMS）網(wǎng)，以滿足）網(wǎng)，以滿足觀眾、游客、工作人員等在奧運(yùn)會(huì)期間的購物需求，觀眾、游客、工作人員等在奧運(yùn)會(huì)期間的購物需求，主要經(jīng)營(yíng)食品、奧運(yùn)紀(jì)念品、旅游用品、文體用品和主要經(jīng)營(yíng)食品、奧運(yùn)紀(jì)念品、旅游用品、文體用品和小日用品等。小日用品等。 在比賽主場(chǎng)館周邊地區(qū)設(shè)置的這種在比賽主場(chǎng)館周邊地區(qū)設(shè)置的這種MSMS，在地點(diǎn)、大小類型和總量方面有三個(gè)基本要求：滿足在地點(diǎn)、大小類型和總量方

7、面有三個(gè)基本要求：滿足奧運(yùn)會(huì)期間的購物需求、分布基本均衡和商業(yè)上贏利。奧運(yùn)會(huì)期間的購物需求、分布基本均衡和商業(yè)上贏利。20042004年年A題題 奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)2004A：奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)的設(shè)計(jì)問題：奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)的設(shè)計(jì)問題 題型：題型：屬于社會(huì)事業(yè)問題屬于社會(huì)事業(yè)問題,主要包括觀眾的出行、用餐主要包括觀眾的出行、用餐和購物的規(guī)律和購物的規(guī)律,各商區(qū)人流分布規(guī)律各商區(qū)人流分布規(guī)律,以及各商區(qū)的大小以及各商區(qū)的大小超市的設(shè)計(jì)數(shù)量等問題。超市的設(shè)計(jì)數(shù)量等問題。 特點(diǎn)：特點(diǎn)：海量數(shù)據(jù)、數(shù)據(jù)冗余、結(jié)構(gòu)復(fù)雜，即時(shí)性、綜海量數(shù)據(jù)、數(shù)據(jù)冗余、結(jié)構(gòu)復(fù)雜，即時(shí)性、綜合性、實(shí)用

8、性和開放性強(qiáng)。合性、實(shí)用性和開放性強(qiáng)。 方法：方法：主題方法數(shù)據(jù)的處理、統(tǒng)計(jì)分析、數(shù)據(jù)挖掘、主題方法數(shù)據(jù)的處理、統(tǒng)計(jì)分析、數(shù)據(jù)挖掘、數(shù)學(xué)規(guī)劃等。數(shù)學(xué)規(guī)劃等。 結(jié)果：結(jié)果：不唯一，對(duì)結(jié)果沒有明確要求。不唯一，對(duì)結(jié)果沒有明確要求。1. 1. 問題引入與分析問題引入與分析2. 2. 圖論的基本概念圖論的基本概念3. 3. 最短路問題及算法最短路問題及算法 圖論模型圖論模型4. 4. 最小生成樹及算法最小生成樹及算法 5. 5. 旅行售貨員問題旅行售貨員問題6. 6. 模型建立與求解模型建立與求解 18世紀(jì)東普魯士哥尼斯堡被普列戈?duì)柡臃譃樗膲K世紀(jì)東普魯士哥尼斯堡被普列戈?duì)柡臃譃樗膲K, 它們通過七座橋相

9、互連接它們通過七座橋相互連接,如下圖如下圖.當(dāng)時(shí)該城的市民當(dāng)時(shí)該城的市民 熱衷于這樣一個(gè)游戲熱衷于這樣一個(gè)游戲:“一個(gè)散步者怎樣才能從某塊一個(gè)散步者怎樣才能從某塊 陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點(diǎn)？”ABCD哥尼斯堡七橋示意圖哥尼斯堡七橋示意圖七橋問題的分析七橋問題的分析 七橋問題看起來不難，很多人都想試一試七橋問題看起來不難，很多人都想試一試，但沒有人但沒有人找到答案找到答案。后來有人寫信告訴了當(dāng)時(shí)的著名數(shù)學(xué)家歐拉后來有人寫信告訴了當(dāng)時(shí)的著名數(shù)學(xué)家歐拉。千百人的失敗使歐拉猜想千百人的失敗使歐拉猜想，也許那樣的走法根本不可能也許那樣的走法根本不

10、可能。1876年年，他證明了自己的猜想他證明了自己的猜想。 Euler把南北兩岸和兩個(gè)島抽象成四個(gè)點(diǎn)把南北兩岸和兩個(gè)島抽象成四個(gè)點(diǎn)，將連接這些將連接這些陸地的橋用連接相應(yīng)兩點(diǎn)的一條線來表示陸地的橋用連接相應(yīng)兩點(diǎn)的一條線來表示，就得到如下一就得到如下一個(gè)簡(jiǎn)圖個(gè)簡(jiǎn)圖:ABDC歐拉的結(jié)論歐拉的結(jié)論 歐拉指出歐拉指出:一個(gè)線圖中存在通過每邊一次僅一次回到一個(gè)線圖中存在通過每邊一次僅一次回到出發(fā)點(diǎn)的路線的充要條件是出發(fā)點(diǎn)的路線的充要條件是: 1)圖是連通的圖是連通的,即任意兩點(diǎn)可由圖中的一些邊連接起來即任意兩點(diǎn)可由圖中的一些邊連接起來; 2)與圖中每一頂點(diǎn)相連的邊必須是偶數(shù)與圖中每一頂點(diǎn)相連的邊必須是偶

11、數(shù). 由此得出結(jié)論由此得出結(jié)論:七橋問題無解七橋問題無解. 歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父因此稱歐拉為圖論之父.ABCDABDC 歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。出發(fā)地。七橋問題七橋問題答案答案的的是是因?yàn)閳D中沒有偶度頂點(diǎn)因?yàn)閳D中沒有偶度頂點(diǎn) 一筆畫問題：歐拉通路或歐拉回路。歐拉圖定義 在無向連通簡(jiǎn)單圖中，通過圖中每邊一次且僅一次并行遍每個(gè)結(jié)點(diǎn)的一條通路(回

12、路)， 稱為該圖的一條歐拉通路(回路)。存在歐拉回路的圖稱為歐拉圖。無歐拉通路或歐拉回路歐拉通路歐拉回路例 下列圖是否可以一筆畫出來.AB3121145678910121314151617181920 問題問題2:哈密頓圈（環(huán)球旅行游戲）哈密頓圈（環(huán)球旅行游戲） 十二面體的十二面體的20個(gè)頂個(gè)頂點(diǎn)代表世界上點(diǎn)代表世界上20個(gè)城個(gè)城市市，能否從某個(gè)城市能否從某個(gè)城市出發(fā)在十二面體上依出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？一次最后回到出發(fā)點(diǎn)？哈密頓圈（環(huán)球旅行游戲）問題問題2:哈密頓圈（環(huán)球旅行游戲）哈密頓圈（環(huán)球旅行游戲） 十二面體的十二面體的20個(gè)頂個(gè)頂點(diǎn)代

13、表世界上點(diǎn)代表世界上20個(gè)城個(gè)城市市，能否從某個(gè)城市能否從某個(gè)城市出發(fā)在十二面體上依出發(fā)在十二面體上依次經(jīng)過每個(gè)城市恰好次經(jīng)過每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？一次最后回到出發(fā)點(diǎn)？哈密頓圖定義 經(jīng)過圖中每個(gè)結(jié)點(diǎn)一次且僅一次的通路(回路)，稱為哈密頓通路(回路)。存在哈密頓回路的圖稱為哈密頓圖。哈密頓圖哈密頓圖無哈密頓通路存在哈密頓通路問題問題3(關(guān)鍵路徑問題關(guān)鍵路徑問題): 一項(xiàng)工程任務(wù)，大到建造一座大壩，一座體育中心一項(xiàng)工程任務(wù)，大到建造一座大壩，一座體育中心,小至組裝一臺(tái)機(jī)床小至組裝一臺(tái)機(jī)床,一架電視機(jī)一架電視機(jī), 都要包括許多工序都要包括許多工序.這些這些工序相互約束，只有在某些工序完成之

14、后工序相互約束，只有在某些工序完成之后, 一個(gè)工序才能一個(gè)工序才能開始開始. 即它們之間存在完成的先后次序關(guān)系，一般認(rèn)為這即它們之間存在完成的先后次序關(guān)系，一般認(rèn)為這些關(guān)系是預(yù)知的些關(guān)系是預(yù)知的, 而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間時(shí)間. 這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目能夠完成整個(gè)工程項(xiàng)目, 影響工程進(jìn)度的要害工序是哪幾影響工程進(jìn)度的要害工序是哪幾個(gè)？個(gè)？ 圖的作用圖的作用 圖是一種表示工具圖是一種表示工具，改變問題的描述方式改變問題的描述方式,往往是創(chuàng)造性的往往是創(chuàng)造性的啟

15、發(fā)式解決問題的手段啟發(fā)式解決問題的手段.一種描述方式就好比我們站在一個(gè)位一種描述方式就好比我們站在一個(gè)位置和角度觀察目標(biāo)置和角度觀察目標(biāo),有的東西被遮擋住了有的東西被遮擋住了,但如果換一個(gè)位置和但如果換一個(gè)位置和角度角度,原來隱藏著的東西就可能被發(fā)現(xiàn)原來隱藏著的東西就可能被發(fā)現(xiàn).采用一種新的描述方式采用一種新的描述方式,可能會(huì)產(chǎn)生新思想可能會(huì)產(chǎn)生新思想.圖論中的圖提供了一種直觀圖論中的圖提供了一種直觀,清晰表達(dá)已知清晰表達(dá)已知信息的方式信息的方式.它有時(shí)就像小學(xué)數(shù)學(xué)應(yīng)用題中的線段圖一樣它有時(shí)就像小學(xué)數(shù)學(xué)應(yīng)用題中的線段圖一樣,能使能使我們用語言描述時(shí)未顯示的或不易觀察到的特征、關(guān)系我們用語言描述

16、時(shí)未顯示的或不易觀察到的特征、關(guān)系,直觀直觀地呈現(xiàn)在我們面前地呈現(xiàn)在我們面前,幫助我們分析和思考問題幫助我們分析和思考問題,激發(fā)我們的靈感激發(fā)我們的靈感.圖的廣泛應(yīng)用圖的廣泛應(yīng)用 圖的應(yīng)用是非常廣泛的圖的應(yīng)用是非常廣泛的,在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、在工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò)通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò),如河道網(wǎng)、灌如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計(jì)算機(jī)溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計(jì)算機(jī)通訊網(wǎng)、輸電線網(wǎng)等等通訊網(wǎng)、輸電線網(wǎng)等等。還有許多看不見的網(wǎng)絡(luò)還有許多看不見的網(wǎng)絡(luò),如各如各種關(guān)系網(wǎng)種關(guān)系網(wǎng),像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系

17、、工像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時(shí)間先后次序關(guān)系等等序的時(shí)間先后次序關(guān)系等等,這些網(wǎng)絡(luò)都可以歸結(jié)為圖這些網(wǎng)絡(luò)都可以歸結(jié)為圖論的研究對(duì)象論的研究對(duì)象-圖圖.其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要我們解決我們解決.還有象生產(chǎn)計(jì)劃、投資計(jì)劃、設(shè)備更新等問還有象生產(chǎn)計(jì)劃、投資計(jì)劃、設(shè)備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題.基本的網(wǎng)絡(luò)優(yōu)化問題基本的網(wǎng)絡(luò)優(yōu)化問題 基本的網(wǎng)絡(luò)優(yōu)化問題有基本的網(wǎng)絡(luò)優(yōu)化問題有: :最短路徑問題、最小生成樹問題、最短路徑問題、最小生成樹問題、最大流問題和最小費(fèi)用問題最大流問題和最小費(fèi)用問題. .圖論作為數(shù)學(xué)的一個(gè)分支

18、圖論作為數(shù)學(xué)的一個(gè)分支, ,已經(jīng)有有已經(jīng)有有效的算法來解決這些問題效的算法來解決這些問題. .當(dāng)然這當(dāng)中的有些問題也可以建立線性當(dāng)然這當(dāng)中的有些問題也可以建立線性規(guī)劃的模型規(guī)劃的模型, ,但有時(shí)若變量特別多但有時(shí)若變量特別多, ,約束也特別多約束也特別多, ,用線性規(guī)劃的用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時(shí)間內(nèi)解決方法求解效率不高甚至不能在可忍受的時(shí)間內(nèi)解決. .而根據(jù)這些而根據(jù)這些問題的特點(diǎn)問題的特點(diǎn), ,采用網(wǎng)絡(luò)分析的方法去求解可能會(huì)非常有效采用網(wǎng)絡(luò)分析的方法去求解可能會(huì)非常有效. . 例如例如, ,在在19781978年年, ,美國財(cái)政部的稅務(wù)分析部門在對(duì)卡特爾稅制美國財(cái)政部

19、的稅務(wù)分析部門在對(duì)卡特爾稅制改革做評(píng)估的過程中改革做評(píng)估的過程中, ,就有一個(gè)就有一個(gè)100,000100,000個(gè)約束以上個(gè)約束以上,25,000,000,25,000,000個(gè)個(gè)變量的問題變量的問題, ,若用普通的線性規(guī)劃求解若用普通的線性規(guī)劃求解, ,預(yù)計(jì)要花預(yù)計(jì)要花7 7個(gè)月的時(shí)間個(gè)月的時(shí)間. .他他們利用網(wǎng)絡(luò)分析的方法們利用網(wǎng)絡(luò)分析的方法, ,將其分解成將其分解成6 6個(gè)子問題個(gè)子問題, ,利用特殊的網(wǎng)絡(luò)計(jì)利用特殊的網(wǎng)絡(luò)計(jì)算機(jī)程序算機(jī)程序, ,花了大約花了大約7 7個(gè)小時(shí)問題就得到了解決個(gè)小時(shí)問題就得到了解決. . 2.圖論的基本概念1) 1) 圖的概念圖的概念2) 2) 賦權(quán)圖與子

20、圖賦權(quán)圖與子圖3) 3) 圖的矩陣表示圖的矩陣表示4) 4) 圖的頂點(diǎn)度圖的頂點(diǎn)度5) 5) 路和連通路和連通1) 圖的概念 定義定義 一個(gè)一個(gè)圖圖G是指一個(gè)二元組是指一個(gè)二元組(V(G),E(G)，其中，其中: 其中元素稱為圖其中元素稱為圖G的的頂點(diǎn)頂點(diǎn).組成的集合，即稱為組成的集合，即稱為邊集邊集,其中元素稱為其中元素稱為邊邊.),(jivv 定義定義 圖圖G的的階階是指圖的頂點(diǎn)數(shù)是指圖的頂點(diǎn)數(shù)|V(G)|, 用用 來表示；來表示；v圖的邊的數(shù)目圖的邊的數(shù)目|E(G)|用用來表示來表示. 也用也用來表示邊來表示邊jivv).,(jivv,)(21vvvGV是非空有限集，稱為是非空有限集，稱

21、為頂點(diǎn)集頂點(diǎn)集，1)2) E(G)是頂點(diǎn)集是頂點(diǎn)集V(G)中的無序或有序的元素偶對(duì)中的無序或有序的元素偶對(duì)).,(EVG )(),(GEGVG 表示圖，簡(jiǎn)記表示圖，簡(jiǎn)記 用用 定義定義 若圖若圖G中的邊均為中的邊均為有序有序偶對(duì)偶對(duì),稱稱G為為有向有向),(jivv邊邊 為為無向邊無向邊，稱，稱e連接連接 和和 ，頂點(diǎn)，頂點(diǎn) 和和 稱稱圖圖. 稱邊稱邊為為有向邊有向邊或或弧弧,稱稱),(jivve 是從是從),(jivve iv連接連接 的弧的弧jv 若圖若圖G中的邊均為無序偶對(duì)中的邊均為無序偶對(duì) ，稱，稱G為為無向圖無向圖.稱稱jivv為為e的的端點(diǎn)端點(diǎn). jivve ivjvivjv 既有

22、無向邊又有有向邊的圖稱為既有無向邊又有有向邊的圖稱為混合圖混合圖.，稱，稱 為為e的的尾尾，稱，稱 為為e的的頭頭. ivjv無向圖無向圖有向圖有向圖有向圖實(shí)例 道路圖 對(duì)于一個(gè)圖對(duì)于一個(gè)圖G = (V, E ), 人們常用圖形來表示它人們常用圖形來表示它, 稱其稱其為為圖解圖解. 凡是有向邊凡是有向邊, 在圖解上都用箭頭標(biāo)明其方向在圖解上都用箭頭標(biāo)明其方向. 例如例如, 設(shè)設(shè)V = v1 , v2 , v3 , v4, E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4, 則則G = (V, E ) 是一個(gè)有是一個(gè)有4個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和6條邊的圖條邊的圖,

23、G的圖解如下圖所示的圖解如下圖所示. 一個(gè)圖會(huì)有許多外形不同的圖解一個(gè)圖會(huì)有許多外形不同的圖解, 下面兩個(gè)圖表示同下面兩個(gè)圖表示同一個(gè)圖一個(gè)圖G = (V, E )的圖解的圖解.其中其中V = v1 , v2 , v3 , v4,E = v1v2 , v1v3 , v1v4 , v2v3 , v2v4 , v3v4. 今后將不計(jì)較這種外形上的差別今后將不計(jì)較這種外形上的差別,而用一個(gè)容易理解而用一個(gè)容易理解的、確定的圖解去表示一個(gè)圖的、確定的圖解去表示一個(gè)圖.常用術(shù)語1)邊和它的兩端點(diǎn)稱為互相邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián)關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為為相鄰相鄰的

24、頂點(diǎn)，與同一個(gè)頂點(diǎn)的頂點(diǎn)，與同一個(gè)頂點(diǎn) 點(diǎn)關(guān)聯(lián)的兩條邊稱為點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰相鄰的邊的邊. 3) 端點(diǎn)重合為一點(diǎn)的邊稱為端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)環(huán)，4) 若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊 稱為稱為重邊重邊5) 既沒有環(huán)也沒有重邊的圖，稱為既沒有環(huán)也沒有重邊的圖，稱為簡(jiǎn)單圖簡(jiǎn)單圖 2) 圖的頂點(diǎn)度定義定義 1) 在無向圖在無向圖G中，與頂點(diǎn)中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(環(huán)環(huán)算兩次算兩次),稱為頂點(diǎn)稱為頂點(diǎn)v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v).稱度為奇數(shù)的頂點(diǎn)為稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為，度

25、為偶數(shù)的頂點(diǎn)為偶點(diǎn)偶點(diǎn).2) 在有向圖中，從頂點(diǎn)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)引出的邊的數(shù)目稱為頂點(diǎn) v的的出度出度，記為，記為d+(v)，從頂點(diǎn)，從頂點(diǎn)v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v). 稱稱d(v)= d+(v)+d -(v)為頂點(diǎn)為頂點(diǎn)v的的 度度或或次數(shù)次數(shù)4)(1vd1)(3ud2)(3ud3)(3ud2) 圖的頂點(diǎn)度定義定義 1) 在無向圖在無向圖G中，與頂點(diǎn)中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(環(huán)環(huán)算兩次算兩次),稱為頂點(diǎn)稱為頂點(diǎn)v的的度度或或次數(shù)次數(shù)，記為，記為d(v)或或 dG(v).稱度為奇數(shù)的頂點(diǎn)為稱度為奇數(shù)的

26、頂點(diǎn)為奇點(diǎn)奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為，度為偶數(shù)的頂點(diǎn)為偶點(diǎn)偶點(diǎn).2) 在有向圖中，從頂點(diǎn)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)引出的邊的數(shù)目稱為頂點(diǎn) v的的出度出度，記為，記為d+(v)，從頂點(diǎn)，從頂點(diǎn)v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v). 稱稱d(v)= d+(v)+d -(v)為頂點(diǎn)為頂點(diǎn)v的的 度度或或次數(shù)次數(shù)d(v1)= d(v3)= d(v4)=4,d(v2)=2.2) 圖的頂點(diǎn)度定義定義 1) 在無向圖在無向圖G中，與頂點(diǎn)中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目關(guān)聯(lián)的邊的數(shù)目(環(huán)環(huán)算兩次算兩次),稱為頂點(diǎn)稱為頂點(diǎn)v的的度度或或次數(shù)次數(shù)，記為，記為d(v)

27、或或 dG(v).稱度為奇數(shù)的頂點(diǎn)為稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為，度為偶數(shù)的頂點(diǎn)為偶點(diǎn)偶點(diǎn).定理定理.2)(Vvvd推論推論 任何圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)任何圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)圖中各點(diǎn)度數(shù)之和是邊數(shù)的2倍 握手定理握手定理 2) 在有向圖中，從頂點(diǎn)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)引出的邊的數(shù)目稱為頂點(diǎn) v的的出度出度，記為，記為d+(v)，從頂點(diǎn)，從頂點(diǎn)v引入的邊的數(shù)目稱為引入的邊的數(shù)目稱為 v的的入度入度，記為，記為d -(v). 稱稱d(v)= d+(v)+d -(v)為頂點(diǎn)為頂點(diǎn)v的的 度度或或次數(shù)次數(shù)定理定理.2)(Vvvd圖中各點(diǎn)度數(shù)之和是邊數(shù)的2倍 握手定理

28、握手定理 推論推論 任何圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù)任何圖中奇點(diǎn)的個(gè)數(shù)為偶數(shù))()()(所有偶點(diǎn)所有奇點(diǎn)jkvjpivkivdvdvd12 由于所有偶數(shù)點(diǎn)的度數(shù)之和必然為偶數(shù)，所以所有奇點(diǎn)度數(shù)之和為偶數(shù)，而每個(gè)奇點(diǎn)的度數(shù)為奇數(shù)，所以奇點(diǎn)的個(gè)數(shù)必然為偶數(shù)。 圖中的每條邊均有兩個(gè)端點(diǎn)，所以在計(jì)算中所有頂點(diǎn)度數(shù)之和時(shí)，每條邊提供度數(shù)為2。 我們今后只討論我們今后只討論有限簡(jiǎn)單圖有限簡(jiǎn)單圖： (1) 頂點(diǎn)個(gè)數(shù)是有限的頂點(diǎn)個(gè)數(shù)是有限的; (2) 任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián)任意一條邊有且只有兩個(gè)不同的點(diǎn)與它相互關(guān)聯(lián); (3) 若是無向圖，則任意兩個(gè)頂點(diǎn)最多只有一條邊與若是無向圖，則任意兩個(gè)頂點(diǎn)最多

29、只有一條邊與之相聯(lián)結(jié)之相聯(lián)結(jié); (4) 若是有向圖，則任意兩個(gè)頂點(diǎn)最多只有兩條邊與若是有向圖，則任意兩個(gè)頂點(diǎn)最多只有兩條邊與之相聯(lián)結(jié)。當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí)，這兩條之相聯(lián)結(jié)。當(dāng)兩個(gè)頂點(diǎn)有兩條邊與之相聯(lián)結(jié)時(shí)，這兩條邊的方向相反。邊的方向相反。 如果某個(gè)有限圖不滿足如果某個(gè)有限圖不滿足(2)(3)(4)，可在某條邊上增設(shè)，可在某條邊上增設(shè)頂點(diǎn)使之滿足。頂點(diǎn)使之滿足。定理2 連通有向圖G含有歐拉回路的充分必要條件是G中每個(gè)結(jié)點(diǎn)的入度等于出度；連通有向圖G含有歐拉通路的充分必要條件是除兩個(gè)結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)的入度等于出度，這兩個(gè)結(jié)點(diǎn)中一個(gè)結(jié)點(diǎn)的入度比其出度多1，另一個(gè)結(jié)點(diǎn)的入度比其出度少1。

30、3) 賦權(quán)圖與子圖 定義定義 若圖若圖 的每一條邊的每一條邊e 都賦以都賦以)(),(GEGVG 一個(gè)實(shí)數(shù)一個(gè)實(shí)數(shù)w(e)，稱，稱w(e)為邊為邊e的的權(quán)權(quán)，G 連同邊上的權(quán)連同邊上的權(quán)稱為稱為賦權(quán)圖賦權(quán)圖. 定義定義 設(shè)設(shè) 和和 是兩個(gè)圖是兩個(gè)圖.),(EVG ),(EVG 若若 , 稱稱 是是 的一個(gè)的一個(gè)子圖子圖,記記 EEVV,GG.GG 若若 ， ，則稱，則稱 是是 的的生成子圖生成子圖.VV EE GG 若若 ，且，且 ，以，以 為頂點(diǎn)集，以兩端點(diǎn)為頂點(diǎn)集，以兩端點(diǎn) VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG 為為 的由的由 導(dǎo)出

31、的子圖導(dǎo)出的子圖，記為，記為 .GVVG 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點(diǎn)的端點(diǎn)EE EEE 集為頂點(diǎn)集的圖集為頂點(diǎn)集的圖 的子圖，稱為的子圖，稱為 的由的由 導(dǎo)出的導(dǎo)出的GGE 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EG,321vvvG,6543eeeeG 3) 若若 ，且，且 ，以，以 為頂點(diǎn)集，以兩端點(diǎn)為頂點(diǎn)集，以兩端點(diǎn) VV VV 均在均在 中的邊的全體為邊集的圖中的邊的全體為邊集的圖 的子圖，稱的子圖，稱 VG4) 若若 ，且，且 ，以，以 為邊集，以為邊集，以 的端點(diǎn)的端點(diǎn)EE EEE 集為頂點(diǎn)集的圖集為頂點(diǎn)集的圖 的子圖，稱為的子圖，稱為 的由的由 導(dǎo)出

32、的導(dǎo)出的GGE 邊導(dǎo)出的子圖邊導(dǎo)出的子圖，記為，記為 . EGGVVG 為為 的由的由 導(dǎo)出的子圖導(dǎo)出的子圖，記為，記為 .4) 圖的矩陣表示 鄰接矩陣鄰接矩陣:1) 對(duì)對(duì)無向圖無向圖 ，其鄰接矩陣，其鄰接矩陣 ，其中：，其中： G)(ijaAijijijvvavv1,0,. 若若 與與相相鄰鄰若若 與與 不不相相鄰鄰54321543210010000100110110010100110vvvvvAvvvvv(以下均假設(shè)圖為簡(jiǎn)單圖以下均假設(shè)圖為簡(jiǎn)單圖).2) 對(duì)對(duì)有向圖有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )(ijaA),(EVG ijijijv vEav vE1,(,),0,(,)

33、. 若若若若432143210100001000001110uuuuAuuuu2) 對(duì)對(duì)有向圖有向圖 ,其鄰接矩陣其鄰接矩陣 ,其中：其中： )(ijaA),(EVG ijijijv vEav vE1,(,),0,(,). 若若若若0101100101001010A其中：其中：3) 對(duì)對(duì)有向賦權(quán)圖有向賦權(quán)圖 , 其鄰接矩陣其鄰接矩陣 ,)(ijaA),(EVG ijijijijijwv vEwa0ijv vE,(,),(,). 若若且且為為其其權(quán)權(quán)，若若43214321040608730uuuuAuuuu其中：其中：3) 對(duì)有向賦權(quán)圖對(duì)有向賦權(quán)圖 , 其鄰接矩陣其鄰接矩陣 ,)(ijaA),(

34、EVG ijijijijijwv vEwa0ijv vE,(,),(,). 若若且且為為其其權(quán)權(quán)，若若05420370860A對(duì)于無向賦權(quán)圖的鄰接矩陣可類似定義對(duì)于無向賦權(quán)圖的鄰接矩陣可類似定義. 關(guān)聯(lián)矩陣 1) 對(duì)無向圖對(duì)無向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：54321543211000001000111100010100011vvvvvMeeeeeijijijvemve1,0,. 若若 與與相相 若若 與與 不不相相 關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)1) 對(duì)無向圖對(duì)無向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：ijijijvemve1,0,.

35、 若若 與與相相 若若 與與 不不相相 關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)關(guān)聯(lián)110100101010011001000111A 無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個(gè)1. 2) 對(duì)有向圖對(duì)有向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：43215432111000101100001101101uuuuMeeeeeijijijijvemveve1,1,0,. 若若 是是 的的尾尾若若 是是 的的 若若 不不是是 的的 與 與尾尾頭頭頭頭2) 對(duì)有向圖對(duì)有向圖 ，其關(guān)聯(lián)矩陣，其關(guān)聯(lián)矩陣 ,),(EVG )(ijmM其中：其中：ijijijijvemveve1,1,0,. 若若 是是 的的尾

36、尾若若 是是 的的 若若 不不是是 的的 與 與尾尾頭頭頭頭1101100011011000000111011001A有向圖的關(guān)聯(lián)矩陣每列元素中有且僅有一個(gè)1,有且僅有一個(gè) - 1. 5) 路和連通 定義定義1) 無向圖無向圖G的一條的一條途徑途徑（或（或通道通道或或鏈鏈）是指）是指一個(gè)有限非空序列一個(gè)有限非空序列 ，它的項(xiàng)交替，它的項(xiàng)交替kkveevevW2110地為頂點(diǎn)和邊，使得對(duì)地為頂點(diǎn)和邊，使得對(duì) ， 的端點(diǎn)是的端點(diǎn)是 和和 ,ki 1ie1iviv稱稱W是從是從 到到 的一條的一條途徑途徑，或一條，或一條 途徑途徑. 整整0vkv),(0kvv數(shù)數(shù)k稱為稱為W的的長(zhǎng)長(zhǎng). 頂點(diǎn)頂點(diǎn) 和

37、和 分別稱為的分別稱為的起點(diǎn)起點(diǎn)和和終點(diǎn)終點(diǎn) ,0vkv而而 稱為稱為W的的內(nèi)部頂點(diǎn)內(nèi)部頂點(diǎn).121,kvvv 2) 若途徑若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱的邊互不相同但頂點(diǎn)可重復(fù)，則稱W為為跡跡或或簡(jiǎn)單鏈簡(jiǎn)單鏈. 3) 若途徑若途徑W的頂點(diǎn)和邊均互不相同，則稱的頂點(diǎn)和邊均互不相同，則稱W為為路路或或路徑路徑. 一條起點(diǎn)為一條起點(diǎn)為 ,終點(diǎn)為終點(diǎn)為 的路稱為的路稱為 路路0vkv),(0kvv記為記為).,(0kvvP 定義定義 1) 途徑途徑 中由相繼項(xiàng)構(gòu)成子序列中由相繼項(xiàng)構(gòu)成子序列kkvevevW.110 稱為途徑稱為途徑W的的節(jié)節(jié).jjiiivevev.11 2) 起點(diǎn)與終點(diǎn)重合的

38、途徑稱為起點(diǎn)與終點(diǎn)重合的途徑稱為閉途徑閉途徑. 3) 起點(diǎn)與終點(diǎn)重合的的路稱為起點(diǎn)與終點(diǎn)重合的的路稱為圈圈(或或回路回路)，長(zhǎng)，長(zhǎng)為為k的圈稱為的圈稱為k階圈階圈，記為，記為Ck. 4) 若在圖若在圖G中存在中存在(u,v)路，則稱頂點(diǎn)路，則稱頂點(diǎn)u和和v在圖在圖G中中連通連通. 5) 若在圖若在圖G中頂點(diǎn)中頂點(diǎn)u和和v是連通的，則頂點(diǎn)是連通的，則頂點(diǎn)u和和v之之之間的之間的距離距離d(u,v)是指圖是指圖G中最短中最短(u,v)路的長(zhǎng)；若沒路的長(zhǎng)；若沒沒有路連接沒有路連接u和和v，則定義為無窮大，則定義為無窮大. 6) 圖圖G中任意兩點(diǎn)皆連通的圖稱為中任意兩點(diǎn)皆連通的圖稱為連通圖連通圖 7)

39、 對(duì)于有向圖對(duì)于有向圖G，若，若 ，且，且 有有kkveevevW2110ie 類似地，可定義類似地，可定義有向跡有向跡，有向路有向路和和有向圈有向圈.頭頭 和尾和尾 ，則稱，則稱W為為有向途徑有向途徑.iv1iv 例例 在右圖中：在右圖中： 途徑或鏈：途徑或鏈： 跡或簡(jiǎn)單鏈：跡或簡(jiǎn)單鏈： 路或路徑：路或路徑： 圈或回路：圈或回路：wugyexeyfxcyvbwcxdvauguavdxcwuuavbwcxfyg用圖論思想求解以下各題用圖論思想求解以下各題 例例 、一擺渡人欲將一只狼，一頭羊，一籃菜從河西、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并渡過

40、河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。解：解： 用四維用四維0-1向量表示（人，狼，羊，菜）的在西岸向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取狀態(tài)，（在西岸則分量取1，否則取，否則取0） 共共24 = 16種狀態(tài)，種狀態(tài)， 由題設(shè)，狀態(tài)（由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，是不允許的， 從而對(duì)應(yīng)狀態(tài)（從而對(duì)應(yīng)狀態(tài)（1,0,0,1），），(1,1,0,0),(1,0,0,0)也是不允許的，也是不允許的，例例 、一擺渡人欲將一只狼，一頭羊，一籃菜從河西

41、、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并渡過河到河?xùn)|，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。且，狼與羊，羊與菜不能獨(dú)處，給出渡河方法。人在河西：人在河西：（1,1,1,1） （1,1,1,0） （1,1,0,1） （1,0,1,1）（1,0,1,0）（0,1,0,1） （0,1,0,0） （0,0,1,0） （0,0,0,1） （0,0,0,0）人在河?xùn)|：人在河?xùn)|： 以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)連線，以十個(gè)向量作為頂點(diǎn)，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得則得10個(gè)頂點(diǎn)的偶圖。個(gè)頂點(diǎn)的偶圖。問題：如何從狀

42、態(tài)（問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（）轉(zhuǎn)移到（0,0,0,0）？）？方法：從（方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達(dá)沒有到達(dá)）開始，沿關(guān)聯(lián)邊到達(dá)沒有到達(dá)的相鄰頂點(diǎn)，到（的相鄰頂點(diǎn)，到（0,0,0,0）終止，得到有向圖即是。）終止，得到有向圖即是。 將將10個(gè)頂點(diǎn)分別記為個(gè)頂點(diǎn)分別記為A1, A2, , A10 ,則渡河問題化為則渡河問題化為在該圖中求一條從在該圖中求一條從A1到到A10的的路路. 從圖中易得到兩條從圖中易得到兩條路路：A1 A6 A3 A7 A2 A8 A5 A10;A1 A6 A3 A9 A4 A8 A5 A10.3最短路問題及算法結(jié)構(gòu)程序設(shè)計(jì)之父第七位圖 靈

43、 獎(jiǎng) (1972年 ) 獲 得 者 。E. W. Dijkstra 1930年5月11日出身于the Netherlands(荷蘭)Rotterdam. 去世于2002年8月6日于Nuenen, the Netherlands.年輕時(shí)代，Dijkstra在University of Leiden, the Netherlands. Leiden大學(xué)是荷蘭最古老的大學(xué)。 學(xué)習(xí)理論物理，但很快他就意識(shí)到其興趣不 在于理論物理雖然獲得了其數(shù)學(xué)和理論物理 的學(xué)位。后來，Dijkstra獲得了其博士學(xué)位從 University of Amsterdam. 1952年-1962年，E. W. Dijkst

44、ra是 Materematisch Centrum, Amsterdam的一 個(gè)程序員。 1962年-1984年，作為一個(gè)數(shù)學(xué)教授任職于 Eindhoven Unviersity of Technology.1984年至1999年，作為計(jì)算機(jī)系系主任任職與美國UT Austin分校，并于1999年退休。2002年8月6日在荷蘭Nuenen自己的家中與世長(zhǎng)辭 Dijkstra 最短路徑算法被廣泛的應(yīng)用在網(wǎng)絡(luò)協(xié)議方面，如OSPF。 Edsger Dijkstra是1950年代ALGOL 語言的一個(gè)主要貢獻(xiàn)者。ALGOL高級(jí)編程語言已經(jīng)成為結(jié)構(gòu)清晰，數(shù)學(xué)基 礎(chǔ)嚴(yán)謹(jǐn)?shù)囊粋€(gè)典范。E. W. Dijkst

45、ra是現(xiàn)代編程語言的主要貢獻(xiàn)者之一，為我們理解程序語言的結(jié)構(gòu)，表示方法與實(shí)現(xiàn)做出了巨大的貢獻(xiàn)。 E. W. Dijkstra 15年的學(xué)術(shù)著作覆蓋了圖論的理論工作，教育手冊(cè)，解釋文章和編程語言領(lǐng)域的哲學(xué)思考。 在現(xiàn)代編程語言方面，E. W. Dijkstra也以 他著名的反對(duì)(過分)使用GOTO語句的文章 而著名。1968年，E. W. Dijkstra撰寫了其 “Go To Statement Considered Harmful”一文。這篇文章被認(rèn)為是現(xiàn)代編程語言逐漸不鼓勵(lì)使用GOTO 語句，而使用編程控制結(jié)構(gòu)，如while loop等等的一個(gè)分水嶺 2) 在賦權(quán)圖在賦權(quán)圖G中，從頂點(diǎn)中，

46、從頂點(diǎn)u到頂點(diǎn)到頂點(diǎn)v的具有最小權(quán)的具有最小權(quán)定義定義 1) 若若H是賦權(quán)圖是賦權(quán)圖G的一個(gè)子圖，則稱的一個(gè)子圖，則稱H的各的各邊的權(quán)和邊的權(quán)和 為為H的的權(quán)權(quán). 類似地，類似地，)()()(HEeewHw稱為路稱為路P的的權(quán)權(quán)若若P(u,v)是賦權(quán)圖是賦權(quán)圖G中從中從u到到v的路的路,稱稱)()()(PEeewPw 的路的路P*(u,v)，稱為，稱為u到到v的的最短路最短路 3) 把賦權(quán)圖把賦權(quán)圖G中一條路的權(quán)稱為它的中一條路的權(quán)稱為它的長(zhǎng)長(zhǎng)，把，把(u,v)路的最小權(quán)稱為路的最小權(quán)稱為u和和v之間的之間的距離距離，并記作，并記作 d(u,v). 如圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表如

47、圖所示的單行線交通網(wǎng)，每個(gè)弧旁邊的數(shù)字表示這條單行線的長(zhǎng)度。現(xiàn)在一個(gè)人要從示這條單行線的長(zhǎng)度?，F(xiàn)在一個(gè)人要從v1出發(fā)，經(jīng)過出發(fā)，經(jīng)過這個(gè)交通網(wǎng)到達(dá)這個(gè)交通網(wǎng)到達(dá)v8，要尋求是總路程最短的線路。，要尋求是總路程最短的線路。1) 賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路636234102312624101v39v5v2v1v4v6v7v8v 從從v1到到v8的路線是很多的。比如從的路線是很多的。比如從v1出發(fā)，經(jīng)過出發(fā)，經(jīng)過v2,v5到達(dá)到達(dá)v8或者從或者從v1出發(fā)，經(jīng)過出發(fā)，經(jīng)過v4，v6，v7到達(dá)到達(dá)v8等。等。但不但不同的路線，經(jīng)過的總長(zhǎng)度是不同的同的路線，經(jīng)過的

48、總長(zhǎng)度是不同的。例如，按照第一。例如，按照第一個(gè)線路，總長(zhǎng)度是個(gè)線路，總長(zhǎng)度是6+1+6=13單位，按照第二個(gè)路線，單位，按照第二個(gè)路線，總長(zhǎng)度是總長(zhǎng)度是1+10+2+4=17單位。單位。v4v2v8v7v6v5v963623410231262410v11v3 一般意義下的最短路問題：一般意義下的最短路問題： 設(shè)一個(gè)賦權(quán)有向圖設(shè)一個(gè)賦權(quán)有向圖D =（V，A），對(duì)于每一個(gè)弧對(duì)于每一個(gè)弧a =（vi ,vj），相應(yīng)地有一個(gè)權(quán)相應(yīng)地有一個(gè)權(quán)wij 。vs ，vt 是是 D 中的兩中的兩個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，P是是D中從中從vs 到到vt 的任意一條路，定義路的權(quán)的任意一條路，定義路的權(quán)是是P 中所有弧的權(quán)

49、的和，記作中所有弧的權(quán)的和，記作S(p)。 最短路問題就是要在所有從最短路問題就是要在所有從vs 到到 vt的路的路P 中，尋找中，尋找一個(gè)權(quán)最小的路一個(gè)權(quán)最小的路P0，亦即亦即S(P0) = min S(p)。P0叫做從叫做從 vs到到 vt 的的最短路最短路。P0的權(quán)的權(quán) S(P0)叫做從叫做從vs到到vt的的距離距離，記，記作作d（vs，vt）。由于）。由于D是有向圖，很明顯是有向圖，很明顯 d（vs，vt）與）與d（vt，vs）一般不相等。）一般不相等。Dijkstra算法 下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的下面介紹在一個(gè)賦權(quán)有向圖中尋求最短路的方法方法Dijkstra算法，它是算

50、法，它是1959年提出來的。目前年提出來的。目前公認(rèn)，公認(rèn)，在所有的權(quán)在所有的權(quán)wij 0時(shí)時(shí)，這個(gè)算法是尋求最短，這個(gè)算法是尋求最短路問題最好的算法。并且，這個(gè)算法實(shí)際上給出路問題最好的算法。并且，這個(gè)算法實(shí)際上給出了尋求從一個(gè)始定點(diǎn)了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)到任意一個(gè)點(diǎn)vj的最短路。的最短路。 尋求從一固定起點(diǎn)尋求從一固定起點(diǎn) u0 到其余各點(diǎn)的最短路的到其余各點(diǎn)的最短路的最有效算法之一是最有效算法之一是Dijkstra算法算法,1959 年由年由 Dijkstra 提出。這個(gè)算法是一種迭代算法提出。這個(gè)算法是一種迭代算法,它依據(jù)的是一個(gè)它依據(jù)的是一個(gè)重要而明顯的性質(zhì)：重要而明顯的

51、性質(zhì)：最短路是一條路，最短路上最短路是一條路，最短路上的任一子段也是最短路。的任一子段也是最短路。 Dijkstra 算法的基本思想是：按距算法的基本思想是：按距 v0 從近到從近到遠(yuǎn)為順序，依次求得遠(yuǎn)為順序，依次求得 v0 到圖到圖 G 的各頂點(diǎn)的最短路的各頂點(diǎn)的最短路和距離，直至頂點(diǎn)和距離，直至頂點(diǎn) v0（或直至圖（或直至圖 G 的所有頂點(diǎn)）。的所有頂點(diǎn)）。Dijkstra算法的基本思想: 從從vs出發(fā)，逐步向外尋找最短路。在運(yùn)算過程中，出發(fā)，逐步向外尋找最短路。在運(yùn)算過程中，與每個(gè)點(diǎn)對(duì)應(yīng)，記錄一個(gè)數(shù)，叫做一個(gè)點(diǎn)的與每個(gè)點(diǎn)對(duì)應(yīng)，記錄一個(gè)數(shù)，叫做一個(gè)點(diǎn)的標(biāo)號(hào)標(biāo)號(hào)。它。它或者表示從或者表示從v

52、s到該點(diǎn)的最短路權(quán)（叫做到該點(diǎn)的最短路權(quán)（叫做P 標(biāo)號(hào)標(biāo)號(hào)），或者），或者表示從表示從vs到該點(diǎn)最短路權(quán)的上界（叫做到該點(diǎn)最短路權(quán)的上界（叫做T 標(biāo)號(hào)標(biāo)號(hào)）。算法）。算法的每一步是去修改的每一步是去修改T 標(biāo)號(hào)，把某一個(gè)具有標(biāo)號(hào)，把某一個(gè)具有T 標(biāo)號(hào)的點(diǎn)改標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂凶優(yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，使圖標(biāo)號(hào)的點(diǎn)，使圖D 中具有中具有P 標(biāo)號(hào)的頂點(diǎn)多一標(biāo)號(hào)的頂點(diǎn)多一個(gè)。這樣，至多經(jīng)過個(gè)。這樣，至多經(jīng)過P -1步，就可求出從步，就可求出從 vs到各點(diǎn)到各點(diǎn)vj的的最短路。最短路。 P(v1)636234102312624101v4v2v6v7v8v9v5v3以例以例1為例說明這個(gè)基本思想。為例說明這個(gè)

53、基本思想。 在例在例1中，中，S=1。因?yàn)?。因?yàn)閣ij 0，d（v1,v1）= 0。這時(shí)，。這時(shí)，v1是是具有具有P標(biāo)號(hào)的點(diǎn)?，F(xiàn)在看從標(biāo)號(hào)的點(diǎn)?，F(xiàn)在看從v1出發(fā)的三條弧（出發(fā)的三條?。╲1,v2）,（v1,v3）,（v1,v4）。如果一個(gè)人從）。如果一個(gè)人從 v1 出發(fā)沿（出發(fā)沿（v1,v2）到達(dá)）到達(dá) v2，路程：，路程：d（v1,v1）+ w12= 6單位。單位。 v1 如果從如果從v1出發(fā)，沿（出發(fā)，沿（v1,v3）到達(dá)）到達(dá)v3，則是，則是d（v1,v1）+w13=3單位。同理，沿（單位。同理，沿（v1,v4）到達(dá)）到達(dá)v4，是，是d（v1,v1）+ w14 = 1單位。單位。故他故他

54、從從v1出發(fā)到達(dá)出發(fā)到達(dá)v4的最短路必是（的最短路必是（v1,v4），），d（v1,v4）= 1。這是因?yàn)閺倪@是因?yàn)閺膙1到達(dá)到達(dá)v4的任一條路，假如是（的任一條路，假如是（v1,v4），則必先沿），則必先沿（v1,v2）到達(dá)）到達(dá) v2，或者沿（，或者沿（v1,v3）到達(dá)）到達(dá) v3，而這時(shí)路程已是，而這時(shí)路程已是6或者或者3單位。單位。P(v1)636234102312624101v4v2v6v7v8v9v5v3v1看從看從v1出發(fā)的三條?。ǔ霭l(fā)的三條?。╲1,v2），（），（v1,v3）,（v1,v4），），mind(v1,v1)+w12 ,d(v1,v1)+w13 , d(v1,v1)

55、+w14 = d（v1,v4）=1。P(v1)63623410231262410v11v4v2v6v7v8v9v5v3 由于所有的權(quán)由于所有的權(quán) wij 0,因此因此,不論他如何再從不論他如何再從v2或者或者v3 到達(dá)到達(dá) v4，所經(jīng)過的總路程都不會(huì)比，所經(jīng)過的總路程都不會(huì)比1少，于是就有少，于是就有d（v1,v4）=1。這樣就使。這樣就使v4變成具有變成具有P標(biāo)號(hào)的點(diǎn)。標(biāo)號(hào)的點(diǎn)。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4) 現(xiàn)在看從現(xiàn)在看從 v1 和和 v4 指向其余點(diǎn)的弧指向其余點(diǎn)的弧.如上所述，從如上所述，從v1出發(fā)，分別沿（出發(fā)，分別沿（v1,v

56、2）,（v1,v3）到達(dá)）到達(dá)v2,v3，經(jīng)過的路，經(jīng)過的路程是程是6或者或者3單位單位.從從v4出發(fā)沿（出發(fā)沿（v4,v6）到達(dá)）到達(dá)v6，經(jīng)過的，經(jīng)過的路程是路程是d（v1,v4）+ w46 =1+10=11單位。單位。 而而min d（v1,v1）+ w12，d（v1,v1）+ w13， d（v1,v4）+ w46 = d（v1,v1）+ w13 = 3單位。單位。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4) 根據(jù)同樣的理由，可以斷定，從根據(jù)同樣的理由，可以斷定，從v1到達(dá)到達(dá)v3的最短路的最短路是（是（v1,v3），），d（v1,v3）= 3。

57、這樣，又使點(diǎn)這樣，又使點(diǎn)v3變?yōu)榫哂凶優(yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以標(biāo)號(hào)的點(diǎn)，不斷重復(fù)以上過程，就可以求出從上過程，就可以求出從vs到達(dá)任一點(diǎn)到達(dá)任一點(diǎn)vj的最短路。的最短路。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4)P(v3)v4v2v8v7v6v5v963623410231262410P(V6)=10P(V7)=9 (V1)=0P(V1)=0P(V4)=1 (V4)=1 (V6)=5 (V5)=2P(V2)=5P(V5)=6P(V8)=12 (V7)=5 (V2)=3 (V8)=5T(V9)=+ (V9)=MP(V3)=3 (V3)=11最短路最短

58、路：V1-(V4-)V3-V2-V5-(V6-V7-)V8算法步驟：算法步驟：1.給始點(diǎn)給始點(diǎn) vs 以以P標(biāo)號(hào)標(biāo)號(hào) ，這表示從，這表示從vs到到vs的最短的最短距離為距離為0，其余節(jié)點(diǎn)均給，其余節(jié)點(diǎn)均給T標(biāo)號(hào)，標(biāo)號(hào)， 2.設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn) vi 為剛得到為剛得到P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)標(biāo)號(hào)的點(diǎn)，考慮點(diǎn)vj，其中其中 ，且，且 vj 為為T標(biāo)號(hào)。對(duì)標(biāo)號(hào)。對(duì)vj的的T標(biāo)號(hào)進(jìn)行如下修改標(biāo)號(hào)進(jìn)行如下修改3.比較所有具有比較所有具有T標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為標(biāo)號(hào)的節(jié)點(diǎn)，把最小者改為P標(biāo)號(hào)，標(biāo)號(hào)，即：即： 當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)。若全標(biāo)號(hào)。若全部節(jié)點(diǎn)均為部節(jié)點(diǎn)均

59、為P標(biāo)號(hào)，則停止，否則用標(biāo)號(hào)，則停止，否則用vk代替代替vi，返回步驟返回步驟（2）。）。0)( svP( )(2,3, )iT vin Evvji ),()min (),( )jjii jT vT vP v )(min)(ikvTvP 237184566134105275934682求從求從1到到8的最短路徑的最短路徑237184566134105275934682X=1, w1= 0min d12,d14,d16 = min 0+2,0+1,0+3= min 2,1,3 = 1 X=1,4, p4=1p4=1p1=0237184566134105275934682X=1,4min d12,

60、d16,d42,d47 = min 0+2,0+3,1+10,1+2= min 2,3,11,3 = 2 X=1,2,4, p2=2p1=0p4=1p2=2237184566134105275934682X=1,2,4min d13,d23,d25,d47= min 0+3,2+6,2+5,1+2= min 3,8,7,3=3 X=1,2,4,6, p6=3p2=2p4=1p1=0p6=3237184566134105275934682X=1,2,4,6min d23,d25,d47,d67= min 2+6,2+5,1+2,3+4= min 8,7,3,7=3 X=1,2,4,6,7, p7