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

例1最短路問題（SPP－shortestpathproblem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路。例2公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最小？例3運輸問題(transportationproblem)某種原材料有N個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往M個使用這些原材料的工廠。假定N個產(chǎn)地的產(chǎn)量和M家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？例4中國郵遞員問題（CPP－Chinesepostmanproblem）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。上述問題有兩個共同的特點： 一、它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題； 二、它們都易于用圖形的形式直觀地描述和表達，數(shù)學上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化（networkoptimization）問題。上面例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流（flow）為研究對象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（networkflows）或網(wǎng)絡(luò)流規(guī)劃等。

98年全國大學生數(shù)學建模競賽B題“最佳災今年(1998年)夏天某縣遭受水災.為考察災情、組織自救，縣領(lǐng)導決定，帶領(lǐng)有關(guān)部門負責人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.情巡視路線”中的前兩個問題是這樣的：

1）若分三組（路）巡視，試設(shè)計總路程最短且各組盡可能均衡的巡視路線.

2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時間T=2小時，在各村停留時間t=1小時，汽車行駛速度V=35公里/小時.要在24小時內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.公路邊的數(shù)字為該路段的公里數(shù).

2008年北京奧運會的建設(shè)工作已經(jīng)進入全面設(shè)計和實施階段。奧運會期間，在比賽主場館的周邊地區(qū)需要建設(shè)由小型商亭構(gòu)建的臨時商業(yè)網(wǎng)點，稱為迷你超市（MiniSupermarket,以下記做MS）網(wǎng)，以滿足觀眾、游客、工作人員等在奧運會期間的購物需求，主要經(jīng)營食品、奧運紀念品、旅游用品、文體用品和小日用品等。在比賽主場館周邊地區(qū)設(shè)置的這種MS，在地點、大小類型和總量方面有三個基本要求：滿足奧運會期間的購物需求、分布基本均衡和商業(yè)上贏利。2004年A題奧運會臨時超市網(wǎng)點設(shè)計2004A：奧運會臨時超市網(wǎng)點的設(shè)計問題題型：屬于社會事業(yè)問題,主要包括觀眾的出行、用餐和購物的規(guī)律,各商區(qū)人流分布規(guī)律,以及各商區(qū)的大小超市的設(shè)計數(shù)量等問題。特點：海量數(shù)據(jù)、數(shù)據(jù)冗余、結(jié)構(gòu)復雜，即時性、綜合性、實用性和開放性強。方法：主題方法數(shù)據(jù)的處理、統(tǒng)計分析、數(shù)據(jù)挖掘、數(shù)學規(guī)劃等。結(jié)果：不唯一，對結(jié)果沒有明確要求。1.問題引入與分析2.圖論的基本概念3.最短路問題及算法圖論模型4.最小生成樹及算法5.旅行售貨員問題6.模型建立與求解

18世紀東普魯士哥尼斯堡被普列戈爾河分為四塊,它們通過七座橋相互連接,如下圖.當時該城的市民熱衷于這樣一個游戲:“一個散步者怎樣才能從某塊陸地出發(fā)，經(jīng)每座橋一次且僅一次回到出發(fā)點？”ABCD哥尼斯堡七橋示意圖七橋問題的分析七橋問題看起來不難，很多人都想試一試，但沒有人找到答案。后來有人寫信告訴了當時的著名數(shù)學家歐拉。千百人的失敗使歐拉猜想，也許那樣的走法根本不可能。1876年，他證明了自己的猜想。Euler把南北兩岸和兩個島抽象成四個點，將連接這些陸地的橋用連接相應(yīng)兩點的一條線來表示，就得到如下一個簡圖:ABDC歐拉的結(jié)論歐拉指出:一個線圖中存在通過每邊一次僅一次回到出發(fā)點的路線的充要條件是:1)圖是連通的,即任意兩點可由圖中的一些邊連接起來;2)與圖中每一頂點相連的邊必須是偶數(shù).由此得出結(jié)論:七橋問題無解.

歐拉由七橋問題所引發(fā)的研究論文是圖論的開篇之作,因此稱歐拉為圖論之父.ABCDABDC歐拉指出：如果每塊陸地所連接的橋都是偶數(shù)座，則從任一陸地出發(fā)，必能通過每座橋恰好一次而回到出發(fā)地。七橋問題答案的是否定的因為圖中沒有偶度頂點一筆畫問題：歐拉通路或歐拉回路。歐拉圖定義

在無向連通簡單圖中，通過圖中每邊一次且僅一次并行遍每個結(jié)點的一條通路(回路)，稱為該圖的一條歐拉通路(回路)。存在歐拉回路的圖稱為歐拉圖。無歐拉通路或歐拉回路歐拉通路歐拉回路例下列圖是否可以一筆畫出來.AB×√√

問題2:哈密頓圈（環(huán)球旅行游戲）

十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圈（環(huán)球旅行游戲）問題2:哈密頓圈（環(huán)球旅行游戲）

十二面體的20個頂點代表世界上20個城市，能否從某個城市出發(fā)在十二面體上依次經(jīng)過每個城市恰好一次最后回到出發(fā)點？哈密頓圖定義

經(jīng)過圖中每個結(jié)點一次且僅一次的通路(回路)，稱為哈密頓通路(回路)。存在哈密頓回路的圖稱為哈密頓圖。哈密頓圖哈密頓圖無哈密頓通路存在哈密頓通路問題3(關(guān)鍵路徑問題):

一項工程任務(wù)，大到建造一座大壩，一座體育中心,小至組裝一臺機床,一架電視機,都要包括許多工序.這些工序相互約束，只有在某些工序完成之后,一個工序才能開始.即它們之間存在完成的先后次序關(guān)系，一般認為這些關(guān)系是預知的,而且也能夠預計完成每個工序所需要的時間.

這時工程領(lǐng)導人員迫切希望了解最少需要多少時間才能夠完成整個工程項目,影響工程進度的要害工序是哪幾個？圖的作用圖是一種表示工具，改變問題的描述方式,往往是創(chuàng)造性的啟發(fā)式解決問題的手段.一種描述方式就好比我們站在一個位置和角度觀察目標,有的東西被遮擋住了,但如果換一個位置和角度,原來隱藏著的東西就可能被發(fā)現(xiàn).采用一種新的描述方式,可能會產(chǎn)生新思想.圖論中的圖提供了一種直觀,清晰表達已知信息的方式.它有時就像小學數(shù)學應(yīng)用題中的線段圖一樣,能使我們用語言描述時未顯示的或不易觀察到的特征、關(guān)系,直觀地呈現(xiàn)在我們面前,幫助我們分析和思考問題,激發(fā)我們的靈感.圖的廣泛應(yīng)用圖的應(yīng)用是非常廣泛的,在工農(nóng)業(yè)生產(chǎn)、交通運輸、通訊和電力領(lǐng)域經(jīng)常都能看到許多網(wǎng)絡(luò),如河道網(wǎng)、灌溉網(wǎng)、管道網(wǎng)、公路網(wǎng)、鐵路網(wǎng)、電話線網(wǎng)、計算機通訊網(wǎng)、輸電線網(wǎng)等等。還有許多看不見的網(wǎng)絡(luò),如各種關(guān)系網(wǎng),像狀態(tài)轉(zhuǎn)移關(guān)系、事物的相互沖突關(guān)系、工序的時間先后次序關(guān)系等等,這些網(wǎng)絡(luò)都可以歸結(jié)為圖論的研究對象----圖.其中存在大量的網(wǎng)絡(luò)優(yōu)化問題需要我們解決.還有象生產(chǎn)計劃、投資計劃、設(shè)備更新等問題也可以轉(zhuǎn)化為網(wǎng)絡(luò)優(yōu)化的問題.基本的網(wǎng)絡(luò)優(yōu)化問題基本的網(wǎng)絡(luò)優(yōu)化問題有:最短路徑問題、最小生成樹問題、最大流問題和最小費用問題.圖論作為數(shù)學的一個分支,已經(jīng)有有效的算法來解決這些問題.當然這當中的有些問題也可以建立線性規(guī)劃的模型,但有時若變量特別多,約束也特別多,用線性規(guī)劃的方法求解效率不高甚至不能在可忍受的時間內(nèi)解決.而根據(jù)這些問題的特點,采用網(wǎng)絡(luò)分析的方法去求解可能會非常有效.例如,在1978年,美國財政部的稅務(wù)分析部門在對卡特爾稅制改革做評估的過程中,就有一個100,000個約束以上,25,000,000個變量的問題,若用普通的線性規(guī)劃求解,預計要花7個月的時間.他們利用網(wǎng)絡(luò)分析的方法,將其分解成6個子問題,利用特殊的網(wǎng)絡(luò)計算機程序,花了大約7個小時問題就得到了解決.

2.圖論的基本概念1)圖的概念2)賦權(quán)圖與子圖3)圖的矩陣表示4)圖的頂點度5)路和連通1)圖的概念

定義一個圖G是指一個二元組(V(G),E(G))，其中:其中元素稱為圖G的頂點.組成的集合，即稱為邊集,其中元素稱為邊.定義圖G的階是指圖的頂點數(shù)|V(G)|,用來表示；圖的邊的數(shù)目|E(G)|用來表示.也用來表示邊是非空有限集，稱為頂點集，1)2)E(G)是頂點集V(G)中的無序或有序的元素偶對表示圖，簡記用

定義

若圖G中的邊均為有序偶對,稱G為有向邊為無向邊，稱e連接和，頂點和稱圖.稱邊為有向邊或弧,稱是從連接的弧若圖G中的邊均為無序偶對，稱G為無向圖.稱為e的端點.

既有無向邊又有有向邊的圖稱為混合圖.，稱為e的尾，稱為e的頭.無向圖有向圖有向圖實例─道路圖對于一個圖G=(V,E),人們常用圖形來表示它,稱其為圖解.凡是有向邊,在圖解上都用箭頭標明其方向.例如,設(shè)V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4},則G=(V,E)是一個有4個頂點和6條邊的圖,G的圖解如下圖所示.一個圖會有許多外形不同的圖解,下面兩個圖表示同一個圖G=(V,E)的圖解.其中V={v1,v2,v3,v4},E={v1v2,v1v3,v1v4,v2v3,v2v4,v3v4}.今后將不計較這種外形上的差別,而用一個容易理解的、確定的圖解去表示一個圖.常用術(shù)語1)邊和它的兩端點稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個端點稱為相鄰的頂點，與同一個頂點點關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點重合為一點的邊稱為環(huán)，4)若一對頂點之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．5)既沒有環(huán)也沒有重邊的圖，稱為簡單圖．2)圖的頂點度定義

1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點v的

度或次數(shù)．2)圖的頂點度定義

1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點v的

度或次數(shù)．d(v1)=d(v3)=d(v4)=4,d(v2)=2.2)圖的頂點度定義

1)在無向圖G中，與頂點v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點為奇點，度為偶數(shù)的頂點為偶點.定理推論

任何圖中奇點的個數(shù)為偶數(shù)．圖中各點度數(shù)之和是邊數(shù)的2倍

握手定理

2)在有向圖中，從頂點v引出的邊的數(shù)目稱為頂點

v的出度，記為d+(v)，從頂點v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點v的

度或次數(shù)．定理圖中各點度數(shù)之和是邊數(shù)的2倍

握手定理

推論

任何圖中奇點的個數(shù)為偶數(shù)．由于所有偶數(shù)點的度數(shù)之和必然為偶數(shù)，所以所有奇點度數(shù)之和為偶數(shù)，而每個奇點的度數(shù)為奇數(shù)，所以奇點的個數(shù)必然為偶數(shù)。

圖中的每條邊均有兩個端點，所以在計算中所有頂點度數(shù)之和時，每條邊提供度數(shù)為2。我們今后只討論有限簡單圖：

(1)頂點個數(shù)是有限的;(2)任意一條邊有且只有兩個不同的點與它相互關(guān)聯(lián);(3)若是無向圖，則任意兩個頂點最多只有一條邊與之相聯(lián)結(jié);(4)若是有向圖，則任意兩個頂點最多只有兩條邊與之相聯(lián)結(jié)。當兩個頂點有兩條邊與之相聯(lián)結(jié)時，這兩條邊的方向相反。

如果某個有限圖不滿足(2)(3)(4)，可在某條邊上增設(shè)頂點使之滿足。定理2

連通有向圖G含有歐拉回路的充分必要條件是G中每個結(jié)點的入度等于出度；連通有向圖G含有歐拉通路的充分必要條件是除兩個結(jié)點外，其余每個結(jié)點的入度等于出度，這兩個結(jié)點中一個結(jié)點的入度比其出度多1，另一個結(jié)點的入度比其出度少1。3)賦權(quán)圖與子圖

定義若圖的每一條邊e

都賦以一個實數(shù)w(e)，稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖.

定義設(shè)和是兩個圖.若,稱是的一個子圖,記若，，則稱是的生成子圖.若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱為的由

導出的子圖，記為.若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由

導出的

邊導出的子圖，記為.

3)若，且，以為頂點集，以兩端點均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點集為頂點集的圖的子圖，稱為的由導出的邊導出的子圖，記為.為的由導出的子圖，記為.4)圖的矩陣表示鄰接矩陣:1)對無向圖，其鄰接矩陣，其中：(以下均假設(shè)圖為簡單圖).2)對有向圖

,其鄰接矩陣,其中：2)對有向圖

,其鄰接矩陣,其中：其中：3)對有向賦權(quán)圖

,其鄰接矩陣,其中：3)對有向賦權(quán)圖,其鄰接矩陣,對于無向賦權(quán)圖的鄰接矩陣可類似定義.關(guān)聯(lián)矩陣1)對無向圖，其關(guān)聯(lián)矩陣,其中：關(guān)聯(lián)關(guān)聯(lián)1)對無向圖，其關(guān)聯(lián)矩陣,其中：關(guān)聯(lián)關(guān)聯(lián)無向圖的關(guān)聯(lián)矩陣每列的元素中有且僅有兩個1.2)對有向圖，其關(guān)聯(lián)矩陣,其中：頭頭2)對有向圖，其關(guān)聯(lián)矩陣,其中：頭頭有向圖的關(guān)聯(lián)矩陣每列元素中有且僅有一個1,有且僅有一個-1.5)路和連通定義1)無向圖G的一條途徑（或通道或鏈）是指一個有限非空序列，它的項交替地為頂點和邊，使得對，的端點是和,稱W是從到的一條途徑，或一條途徑.整數(shù)k稱為W的長.頂點和分別稱為的起點和終點

,而稱為W的內(nèi)部頂點.

2)若途徑W的邊互不相同但頂點可重復，則稱W為跡或簡單鏈.

3)若途徑W的頂點和邊均互不相同，則稱W為路或路徑.一條起點為,終點為的路稱為路記為定義

1)途徑中由相繼項構(gòu)成子序列稱為途徑W的節(jié).

2)起點與終點重合的途徑稱為閉途徑.

3)起點與終點重合的的路稱為圈(或回路)，長為k的圈稱為k階圈，記為Ck.

4)若在圖G中存在(u,v)路，則稱頂點u和v在圖G中連通.

5)若在圖G中頂點u和v是連通的，則頂點u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長；若沒沒有路連接u和v，則定義為無窮大.

6)圖G中任意兩點皆連通的圖稱為連通圖．

7)對于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：途徑或鏈：跡或簡單鏈：路或路徑：圈或回路：用圖論思想求解以下各題例、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。解：用四維0-1向量表示（人，狼，羊，菜）的在西岸狀態(tài)，（在西岸則分量取1，否則取0）共24

=

16種狀態(tài)，由題設(shè)，狀態(tài)（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允許的，從而對應(yīng)狀態(tài)（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允許的，例、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。人在河西：（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）人在河東：以十個向量作為頂點，將可能互相轉(zhuǎn)移的狀態(tài)連線，則得10個頂點的偶圖。問題：如何從狀態(tài)（1,1,1,1）轉(zhuǎn)移到（0,0,0,0）？方法：從（1,1,1,1）開始，沿關(guān)聯(lián)邊到達沒有到達的相鄰頂點，到（0,0,0,0）終止，得到有向圖即是。將10個頂點分別記為A1,A2,…,A10,則渡河問題化為在該圖中求一條從A1到A10的路.

從圖中易得到兩條路：A1A6A3A7A2A8A5A10;A1A6A3A9A4A8A5A10.3．最短路問題及算法最短路問題是圖論應(yīng)用的基本問題，很多實際問題，如線路的布設(shè)、運輸安排、運輸網(wǎng)絡(luò)最小費用流等問題，都可通過建立最短路問題模型來求解。最短路的定義最短路問題的兩種方法：Dijkstra和Floyd算法.求賦權(quán)圖中從給定點到其余頂點的最短路.求賦權(quán)圖中任意兩點間的最短路.結(jié)構(gòu)程序設(shè)計之父第七位圖靈獎(1972年)獲得者。E.W.Dijkstra1930年5月11日出身于theNetherlands(荷蘭)Rotterdam.去世于2002年8月6日于Nuenen,theNetherlands.年輕時代，Dijkstra在UniversityofLeiden,theNetherlands.Leiden大學是荷蘭最古老的大學。學習理論物理，但很快他就意識到其興趣不在于理論物理雖然獲得了其數(shù)學和理論物理的學位。后來，Dijkstra獲得了其博士學位從

UniversityofAmsterdam.1952年-1962年，E.W.Dijkstra是

MaterematischCentrum,Amsterdam的一個程序員。

1962年-1984年，作為一個數(shù)學教授任職于

EindhovenUnviersityofTechnology.1984年至1999年，作為計算機系系主任任職與美國UTAustin分校，并于1999年退休。2002年8月6日在荷蘭Nuenen自己的家中與世長辭

Dijkstra最短路徑算法被廣泛的應(yīng)用在網(wǎng)絡(luò)協(xié)議方面，如OSPF。

EdsgerDijkstra是1950年代ALGOL語言的一個主要貢獻者。ALGOL高級編程語言已經(jīng)成為結(jié)構(gòu)清晰，數(shù)學基礎(chǔ)嚴謹?shù)囊粋€典范。E.W.Dijkstra是現(xiàn)代編程語言的主要貢獻者之一，為我們理解程序語言的結(jié)構(gòu)，表示方法與實現(xiàn)做出了巨大的貢獻。E.W.Dijkstra15年的學術(shù)著作覆蓋了圖論的理論工作，教育手冊，解釋文章和編程語言領(lǐng)域的哲學思考。在現(xiàn)代編程語言方面，E.W.Dijkstra也以他著名的反對(過分)使用GOTO語句的文章而著名。1968年，E.W.Dijkstra撰寫了其“GoToStatementConsideredHarmful”一文。這篇文章被認為是現(xiàn)代編程語言逐漸不鼓勵使用GOTO語句，而使用編程控制結(jié)構(gòu)，如whileloop等等的一個分水嶺

2)在賦權(quán)圖G中，從頂點u到頂點v的具有最小權(quán)定義1)若H是賦權(quán)圖G的一個子圖，則稱H的各邊的權(quán)和為H的權(quán).類似地，稱為路P的權(quán)．若P(u,v)是賦權(quán)圖G中從u到v的路,稱的路P*(u,v)，稱為u到v的最短路．

3)把賦權(quán)圖G中一條路的權(quán)稱為它的長，把(u,v)路的最小權(quán)稱為u和v之間的距離，并記作d(u,v).

如圖所示的單行線交通網(wǎng)，每個弧旁邊的數(shù)字表示這條單行線的長度?，F(xiàn)在一個人要從v1出發(fā)，經(jīng)過這個交通網(wǎng)到達v8，要尋求是總路程最短的線路。1)賦權(quán)圖中從給定點到其余頂點的最短路636234102312624101v3從v1到v8的路線是很多的。比如從v1出發(fā)，經(jīng)過v2,v5到達v8或者從v1出發(fā)，經(jīng)過v4，v6，v7到達v8等。但不同的路線，經(jīng)過的總長度是不同的。例如，按照第一個線路，總長度是6+1+6=13單位，按照第二個路線，總長度是1+10+2+4=17單位。v4v2v8v7v6v5v963623410231262410v11v3

一般意義下的最短路問題：設(shè)一個賦權(quán)有向圖D=（V，A），對于每一個弧a=（vi,vj），相應(yīng)地有一個權(quán)wij。vs

，vt

是

D

中的兩個頂點，P是D中從vs

到vt

的任意一條路，定義路的權(quán)是P中所有弧的權(quán)的和，記作S(p)。最短路問題就是要在所有從vs

到

vt的路P

中，尋找一個權(quán)最小的路P0，亦即S(P0)

=

min

S(p)。P0叫做從

vs到

vt

的最短路。P0的權(quán)S(P0)叫做從vs到vt的距離，記作d（vs，vt）。由于D是有向圖，很明顯

d（vs，vt）與d（vt，vs）一般不相等。Dijkstra算法

下面介紹在一個賦權(quán)有向圖中尋求最短路的方法—Dijkstra算法，它是1959年提出來的。目前公認，在所有的權(quán)wij

≥0時，這個算法是尋求最短路問題最好的算法。并且，這個算法實際上給出了尋求從一個始定點vs到任意一個點vj的最短路。尋求從一固定起點u0

到其余各點的最短路的最有效算法之一是Dijkstra算法,1959年由Dijkstra提出。這個算法是一種迭代算法,它依據(jù)的是一個重要而明顯的性質(zhì)：最短路是一條路，最短路上的任一子段也是最短路。Dijkstra算法的基本思想是：按距v0

從近到遠為順序，依次求得v0

到圖G

的各頂點的最短路和距離，直至頂點v0（或直至圖G

的所有頂點）。Dijkstra算法的基本思想:

從vs出發(fā)，逐步向外尋找最短路。在運算過程中，與每個點對應(yīng)，記錄一個數(shù)，叫做一個點的標號。它或者表示從vs到該點的最短路權(quán)（叫做P標號），或者表示從vs到該點最短路權(quán)的上界（叫做T標號）。算法的每一步是去修改T標號，把某一個具有T標號的點改變?yōu)榫哂蠵標號的點，使圖D中具有P標號的頂點多一個。這樣，至多經(jīng)過P-1步，就可求出從vs到各點vj的最短路。

P(v1)636234102312624101v4v2v6v7v8v9v5v3以例1為例說明這個基本思想。在例1中，S=1。因為wij

≥0，d（v1,v1）=0。這時，v1是具有P標號的點。現(xiàn)在看從v1出發(fā)的三條?。╲1,v2）,（v1,v3）,（v1,v4）。如果一個人從

v1

出發(fā)沿（v1,v2）到達

v2，路程：d（v1,v1）+w12=6單位。v1如果從v1出發(fā)，沿（v1,v3）到達v3，則是d（v1,v1）+w13=3單位。同理，沿（v1,v4）到達v4，是d（v1,v1）+

w14

=

1單位。故他從v1出發(fā)到達v4的最短路必是（v1,v4），d（v1,v4）=

1。這是因為從v1到達v4的任一條路，假如是（v1,v4），則必先沿（v1,v2）到達

v2，或者沿（v1,v3）到達

v3，而這時路程已是6或者3單位。P(v1)636234102312624101v4v2v6v7v8v9v5v3v1看從v1出發(fā)的三條?。╲1,v2），（v1,v3）,（v1,v4），min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}=d（v1,v4）=1。P(v1)63623410231262410v11v4v2v6v7v8v9v5v3由于所有的權(quán)

wij

≥0,因此,不論他如何再從v2或者v3

到達

v4，所經(jīng)過的總路程都不會比1少，于是就有d（v1,v4）=1。這樣就使v4變成具有P標號的點。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4)現(xiàn)在看從

v1

和

v4

指向其余點的弧.如上所述，從v1出發(fā)，分別沿（v1,v2）,（v1,v3）到達v2,v3，經(jīng)過的路程是6或者3單位.從v4出發(fā)沿（v4,v6）到達v6，經(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ù)同樣的理由，可以斷定，從v1到達v3的最短路是（v1,v3），d（v1,v3）=3。這樣，又使點v3變?yōu)榫哂蠵

標號的點，不斷重復以上過程，就可以求出從vs到達任一點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最短路：V1-(V4-)V3-V2-V5-(V6-V7-)V8算法步驟：1.給始點vs

以P標號，這表示從vs到vs的最短距離為0，其余節(jié)點均給T標號，2.設(shè)節(jié)點vi

為剛得到P標號的點，考慮點vj，其中，且vj

為T標號。對vj的T標號進行如下修改3.比較所有具有T標號的節(jié)點，把最小者改為P標號，即：當存在兩個以上最小者時，可同時改為P標號。若全部節(jié)點均為P標號，則停止，否則用vk代替vi，返回步驟（2）。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,4}min{d12,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,4}min{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,6}min{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=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{d23,dc25,d75,d78}=

min{2+6,2+5,3+3,3+8}=

min{8,7,6,11}=

6

X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{d23,d53,d58,d78}=

min{2+6,6+9,6+4,3+8}=

min{8,15,10,11}=

8

X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8237184566134105275934682X={1,2,3,4,6,7}min{d38,d58,d78}=

min{8+6,6+4,3+7}=

min{14,10,11}

=

10

X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10求從V1

到V8

的最短路線。V1V2V3V4V5V6V7V8①P=0T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞T=+∞②P=T=3T=+∞T=7T=+∞T=+∞T=+∞T=+∞

③T=6T=7P=T=5T=+∞T=+∞T=+∞

④P=T=6T=6

T=8T=+∞T=+∞

⑤P=T=6

T=8T=9T=12

⑥P=T=8T=10T=10

⑦P=T=9T=11再無其它T標號，所以T(V8)=P(V8)=10;minL(μ)=10⑧P=T=10由此看到，此方法不僅求出了從V1

到V8

的最短路長，同時也求出了從V1

到任意一點的最短路長。將從V1

到任一點的最短路權(quán)標在圖上，即可求出從V1

到任一點的最短路線。本例中V1

到V8

的最短路線是：

v1→v2→v5→v6→v8

∞243523512246421用Dijkstra算法求下圖從v1到v6的最短路。

v1v2v3v4v6v5352242421

解

（1）首先給v1以P標號，給其余所有點T標號。（2）（3）（4）v1v2v3v4v6v5352242421（5）（6）（7）（8）（9）（10）反向追蹤得v1到v6的最短路為：求下面賦權(quán)圖中頂點u0到其余頂點的最短路．算法步驟：求所示的圖G

中v1

到其余各頂點的最短路及其距離。解：(1)初始標號。i=0。S0={v1}，v1=u0，參見圖(a)。(a)(2)用u0=v1

對各頂點的標號進行更新。i=1。={v2,v3,v4,v5,v6}，v，由算法有： l(v2)=min{,0+7}=7， l(v3)=min{,0+4}=4， l(v4)=min{,0+}=， l(v5)=min{,0+}=， l(v6)=min{,0+2}=2。由于v2，v3，v6的標號被v1更新，故這三個頂點的父節(jié)點為v1，即z(v2)=z(v3)=z(v6)=v1，參見圖(b)，數(shù)字邊方框中的符號表示父節(jié)點。又由于=l(v6)=2，故u1=v6，S1={v1,v6}。參見圖(c)。

(b)(c)(3)用u1=v6

對各頂點的標號進行更新。i=2。={v2,v3,v4,v5}，v，由算法有： l(v2)=min{7,2+}=7， l(v3)=min{4,2+1}=3， l(v4)=min{,2+5}=7， l(v5)=min{,2+5}=7。

在此次迭代中，v2的標號不變，v3，v4，v5的標號被v6更新，故v2

的父節(jié)點不變，v3，v4，v5的父節(jié)點為v6，即z(v2)=v1，z(v3)=z(v4)=z(v5)=v6。參見圖(d)。又由于=l(v3)=3，故u2=v3，S2={v1,v6,v3}。參見圖(e)。(d)(e)

(4)用u2=v3

對各頂點的標號進行更新。i=3。={v2,v4,v5}，v，由算法有： l(v2)=min{7,3+3}=6， l(v4)=min{7,3+1}=4， l(v5)=min{7,3+}=7。

在此次迭代中，v5

的標號不變，v2

和v4

的標號被v3

更新，故v5

的父節(jié)點不變，v2

和v4

的父節(jié)點為v3，即z(v5)=v6，z(v2)=z(v4)=v3。參見圖(f)。又由于=l(v4)=4，故u3=v4，S3={v1,v6,v3,v4}。參見圖(g)。(f)(g)(5)用u3=v4

對各頂點的標號進行更新。i=4。={v2,v5}，v，由算法有： l(v2)=min{6,4+}=6， l(v5)=min{7,4+2}=6。

在此次迭代中，v2

的標號不變，v5標號被v4更新，故v2

的父節(jié)點不變，v5

的父節(jié)點為v4，即z(v2)=v3，z(v5)=v4。參見圖(h)。又由于=l(v5)=6，故u4=v5，S4={v1,v6,v3,v4,v5}。參見圖(i)。(h)(i)

(6)用u4=v5

對各頂點的標號進行更新。i=5。={v2}，v={v2}，由算法有：l(v2)=min{6,6+}=6。在此次迭代中，v2

的標號不變，故v2

的父節(jié)點不變，即z(v2)=v3。參見圖(i)。又由于=l(v2)=6，故u5=v2，S5={v1,v6,v3,v4,v5,v2}。(h)(i)(7)由于i=5=n

1，停止。注：①迭代的終止條件也可使用Sn1={v1,…,vn}，或者=。②若尋找v1

到某點v的最短路的路由，則由v開始追溯父節(jié)點直至v1。例如，尋找v1

到v5

的最短路的路由，根據(jù)圖(i)，從v5

開始追溯父節(jié)點：v5

的父節(jié)點為v4，v4的父節(jié)點為v3，v3

的父節(jié)點為v6，v6

的父節(jié)點為v1。于是v1

到v5

的最短路為：v1v6v3v4v5。再如，v1

到v2

的最短路為：v1v6v3v2。③若求v1到某點v的距離，則直接由l(v)的終值確定。例如，根據(jù)圖(i)，由于l(v5)=6，故v1

到v5的距離為6。再如，由于l(v2)=6，故v1

到v2

的距離也為6。

TOMATLAB(road1)

1

2

34

5

6

7

8尋求賦權(quán)圖中各對頂點之間最短路，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復執(zhí)行次這樣的操作，就可得到每對頂點之間的最短路。但這樣做需要大量重復計算，效率不高。R.W.Floyd（弗洛伊德）另辟蹊徑，提出了比這更好的算法，操作方式與Dijkstra算法截然不同。2)求賦權(quán)圖中任意兩頂點間的最短路算法的基本思想（I）求距離矩陣的方法.（II）求路徑矩陣的方法.（III）查找最短路路徑的方法

Floyd算法：求任意兩頂點間的最短路.舉例說明

算法的基本思想

（I）求距離矩陣的方法.D(0)=[dij(0)]nn=A：是帶權(quán)鄰接矩陣，dij(0)

表示從vi

到vj

的、中間不插入任何點的路徑，即邊vivj

的權(quán)值；D(1)=[dij(1)]nn，其中dij(1)=min{dij(0)，di1(0)

d1j(0)}：dij(1)

表示從vi

到vj

的、中間最多只允許v1

作為插入點的路徑中最短路的長度；D(2)=[dij(2)]nn，其中dij(2)=min{dij(1)，di2(1)d2j(1)}：dij(2)

表示從vi

到vj

的、中間最多只允許v1

和v2

作為插入點的路徑中最短路的長度；…………D(n)=[dij(n)]nn，其中dij(n)=min{dij(n1)，di,n1(n1)

dn1,j(n1)}：dij(n)

表示從vi

到vj

的、中間最多只允許v1,v2,…,vn1

作為插入點的路徑中最短路的長度，即vi

和vj

之間的距離。（II）求路徑矩陣的方法.在建立距離矩陣的同時可建立路徑矩陣R．（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找．若：（IV）Floyd算法：求任意兩頂點間的最短路.例求下圖中加權(quán)圖的任意兩點間的距離與路徑.插入點v1，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.插入點v2，得：矩陣中帶“=”的項為經(jīng)迭代比較以后有變化的元素.插入點v3，得：插入點v4，得：插入點v5，得：插入點v6，得：故從v5到v2的最短路為8由v5向v6追溯:由v6向v2追溯:所以從到的最短路徑為：二、選址問題一、可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題例1設(shè)備更新問題：企業(yè)使用一臺設(shè)備，每年年初，企業(yè)領(lǐng)導就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費用；若繼續(xù)使用，則需支付一定的維修費用.現(xiàn)要制定一個五年之內(nèi)的設(shè)備更新計劃，使得五年內(nèi)總的支付費用最少.分析：可行的購置方案（更新計劃）是很多的，如：1）每年購置一臺新的，則對應(yīng)的費用為：

11+11+12+12+13+5+5+5+5+5=842)第一年購置新的，一直用到第五年年底，則總費用為：11+5+6+8+11+18=59

顯然不同的方案對應(yīng)不同的費用。第i年度12345購置費1111121213設(shè)備役齡0-11-22-33-44-5維修費用5681118這樣上述設(shè)備更新問題就變?yōu)椋涸谟邢蛸x權(quán)圖G=(V,E,F)(圖解如下)中求v1到v6的最短路問題.（2）方法：將此問題用一個賦權(quán)有向圖來描述，然后求這個賦權(quán)有向圖的最短路。求解步驟：1）畫賦權(quán)有向圖：設(shè)Vi

表示第i年初，(Vi,Vj)表示第i

年初購買新設(shè)備用到第j年初（j-1年底），而Wij

表示相應(yīng)費用，則5年的一個更新計劃相當于從V1

到V6的一條路。2）求解（標號法）由實際問題可知，設(shè)備使用三年后應(yīng)當更新，因此刪除該圖中v1到v5，v1到v6，v2到v6的連線；又設(shè)備使用一年后就更新則不劃算，因此再刪除該圖中v1v2，v2v3，v3v4，v4v5，v5v6五條連線后得到從上圖中容易得到v1到v6只有兩條路：v1v3v6

和v1v4v6.而這兩條路都是v1到v6的最短路.

選址問題--中心問題S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處。

選址問題--重心問題最小生成樹及算法1)樹的定義與樹的特征定義連通且不含圈的無向圖稱為樹．常用T表示.樹中的邊稱為樹枝.樹中度為1的頂點稱為樹葉.孤立頂點稱為平凡樹.平凡樹定理2設(shè)G是具有n個頂點的圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最小連通圖）；6)G中任意兩頂點間有唯一一條路.2）圖的生成樹定義若T是包含圖G的全部頂點的子圖,它又是樹,則稱T是G的生成樹.圖G中不在生成樹的邊叫做弦.定理3

圖G=(V,E)有生成樹的充要條件是圖G是連通的.（II）找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法

B破圈法A避圈法

定理3的充分性的證明提供了一種構(gòu)造圖的生成樹的方法.這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種方法可稱為“避圈法”或“加邊法”在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.a)深探法若這樣的邊的另一端均已有標號，就退到標號為步驟如下：i)在點集V中任取一點u,ii)若某點v已得標號，檢端是否均已標號.若有邊vw之w未標號,則給w代v，重復ii).i-1的r點,以r代v,重復ii),直到全部點得到標號為止.給以標號0.查一端點為v的各邊，另一w以標號i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

圖1001234567891011121313a)深探法圖100123456789101112步驟如下：若這樣的邊的另一端均已有標號，就退到標號為i)在點集V中任取一點u,ii)若某點v已得標號，檢端是否均已標號.若有邊vw之w未標號,則給w代v，重復ii).i-1的r點,以r代v,重復ii),直到全部點得到標號為止.給u以標號0.查一端點為v的各邊，另一w以標號i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

3b)廣探法步驟如下：i)在點集V中任取一點u,ii)令所有標號i的點集為是否均已標號.對所有未標號之點均標以i+1,記下這些

iii)對標號i+1的點重復步步驟ii)，直到全部點得到給u以標號0.Vi,檢查[Vi,V\Vi]中的邊端點邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標號為止.圖103b)廣探法步驟如下：i)在點集V中任取一點u,ii)令所有標號i的點集為是否均已標號.對所有未標號之點均標以i+1,記下這些

iii)對標號i+1的點重復步步驟ii)，直到全部點得到給u以標號0.Vi,檢查[Vi,V\Vi]中的邊端點邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標號為止.顯然圖10的生成樹不唯一.B破圈法相對于避圈法，還有一種求生成樹的方法叫做“破圈法”.這種方法就是在圖G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復這個步驟直到圖G中沒有圈為止.例用破圈法求出下圖的一棵生成樹.B破圈法例用破圈法求出下圖的另一棵生成樹.不難發(fā)現(xiàn)，圖的生成樹不是唯一的.3)最小生成樹與算法介紹最小樹的兩種算法：Kruskal算法（或避圈法）和破圈法.AKruskal算法（或避圈法）步驟如下：

1)選擇邊e1，使得w(e1)盡可能?。?)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)是滿足i)的盡可能小的權(quán)，

3)當?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.例10用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條在中選取權(quán)值最小的邊中權(quán)值最小邊有,從中選任取一條邊會與已選邊構(gòu)成圈,故停止,得中選取在中選取中選取.但與都B破圈法算法2

步驟如下：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中立即生成一個圈.去掉此圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復2)再檢查剩余的弦，直到全部弦檢查完畢為止.例11用破圈法求下圖的最小樹.先求出上圖的一棵生成樹.

加以弦e2,得到的圈v1v3v2v1,去掉最大的權(quán)邊e2,得到一棵新樹仍是原來的樹；

再加上弦e7，得到圈v4v5v2v4,去掉最大的