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

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

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

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

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

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

7、面有三個基本要求：滿足奧運會期間的購物需求、分布基本均衡和商業上贏利。奧運會期間的購物需求、分布基本均衡和商業上贏利。20042004年年A題題 奧運會臨時超市網點設計奧運會臨時超市網點設計2004A：奧運會臨時超市網點的設計問題：奧運會臨時超市網點的設計問題 題型：題型：屬于社會事業問題屬于社會事業問題,主要包括觀眾的出行、用餐主要包括觀眾的出行、用餐和購物的規律和購物的規律,各商區人流分布規律各商區人流分布規律,以及各商區的大小以及各商區的大小超市的設計數量等問題。超市的設計數量等問題。 特點：特點：海量數據、數據冗余、結構復雜，即時性、綜海量數據、數據冗余、結構復雜，即時性、綜合性、實用

8、性和開放性強。合性、實用性和開放性強。 方法：方法：主題方法數據的處理、統計分析、數據挖掘、主題方法數據的處理、統計分析、數據挖掘、數學規劃等。數學規劃等。 結果：結果：不唯一，對結果沒有明確要求。不唯一，對結果沒有明確要求。1. 1. 問題引入與分析問題引入與分析2. 2. 圖論的基本概念圖論的基本概念3. 3. 最短路問題及算法最短路問題及算法 圖論模型圖論模型4. 4. 最小生成樹及算法最小生成樹及算法 5. 5. 旅行售貨員問題旅行售貨員問題6. 6. 模型建立與求解模型建立與求解 18世紀東普魯士哥尼斯堡被普列戈爾河分為四塊世紀東普魯士哥尼斯堡被普列戈爾河分為四塊, 它們通過七座橋相

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

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

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

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

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

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

15、發式解決問題的手段啟發式解決問題的手段.一種描述方式就好比我們站在一個位一種描述方式就好比我們站在一個位置和角度觀察目標置和角度觀察目標,有的東西被遮擋住了有的東西被遮擋住了,但如果換一個位置和但如果換一個位置和角度角度,原來隱藏著的東西就可能被發現原來隱藏著的東西就可能被發現.采用一種新的描述方式采用一種新的描述方式,可能會產生新思想可能會產生新思想.圖論中的圖提供了一種直觀圖論中的圖提供了一種直觀,清晰表達已知清晰表達已知信息的方式信息的方式.它有時就像小學數學應用題中的線段圖一樣它有時就像小學數學應用題中的線段圖一樣,能使能使我們用語言描述時未顯示的或不易觀察到的特征、關系我們用語言描述

16、時未顯示的或不易觀察到的特征、關系,直觀直觀地呈現在我們面前地呈現在我們面前,幫助我們分析和思考問題幫助我們分析和思考問題,激發我們的靈感激發我們的靈感.圖的廣泛應用圖的廣泛應用 圖的應用是非常廣泛的圖的應用是非常廣泛的,在工農業生產、交通運輸、在工農業生產、交通運輸、通訊和電力領域經常都能看到許多網絡通訊和電力領域經常都能看到許多網絡,如河道網、灌如河道網、灌溉網、管道網、公路網、鐵路網、電話線網、計算機溉網、管道網、公路網、鐵路網、電話線網、計算機通訊網、輸電線網等等通訊網、輸電線網等等。還有許多看不見的網絡還有許多看不見的網絡,如各如各種關系網種關系網,像狀態轉移關系、事物的相互沖突關系

17、、工像狀態轉移關系、事物的相互沖突關系、工序的時間先后次序關系等等序的時間先后次序關系等等,這些網絡都可以歸結為圖這些網絡都可以歸結為圖論的研究對象論的研究對象-圖圖.其中存在大量的網絡優化問題需要其中存在大量的網絡優化問題需要我們解決我們解決.還有象生產計劃、投資計劃、設備更新等問還有象生產計劃、投資計劃、設備更新等問題也可以轉化為網絡優化的問題題也可以轉化為網絡優化的問題.基本的網絡優化問題基本的網絡優化問題 基本的網絡優化問題有基本的網絡優化問題有: :最短路徑問題、最小生成樹問題、最短路徑問題、最小生成樹問題、最大流問題和最小費用問題最大流問題和最小費用問題. .圖論作為數學的一個分支

18、圖論作為數學的一個分支, ,已經有有已經有有效的算法來解決這些問題效的算法來解決這些問題. .當然這當中的有些問題也可以建立線性當然這當中的有些問題也可以建立線性規劃的模型規劃的模型, ,但有時若變量特別多但有時若變量特別多, ,約束也特別多約束也特別多, ,用線性規劃的用線性規劃的方法求解效率不高甚至不能在可忍受的時間內解決方法求解效率不高甚至不能在可忍受的時間內解決. .而根據這些而根據這些問題的特點問題的特點, ,采用網絡分析的方法去求解可能會非常有效采用網絡分析的方法去求解可能會非常有效. . 例如例如, ,在在19781978年年, ,美國財政部的稅務分析部門在對卡特爾稅制美國財政部

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、途徑稱為起點與終點重合的途徑稱為閉途徑閉途徑. 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)

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

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

41、、一擺渡人欲將一只狼，一頭羊，一籃菜從河西渡過河到河東，由于船小，一次只能帶一物過河，并渡過河到河東，由于船小，一次只能帶一物過河，并且，狼與羊，羊與菜不能獨處，給出渡河方法。且，狼與羊，羊與菜不能獨處，給出渡河方法。人在河西：人在河西：（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）人在河東：人在河東： 以十個向量作為頂點，將可能互相轉移的狀態連線，以十個向量作為頂點，將可能互相轉移的狀態連線，則得則得10個頂點的偶圖。個頂點的偶圖。問題：如何從狀

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

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

44、ra是 Materematisch Centrum, Amsterdam的一 個程序員。 1962年-1984年，作為一個數學教授任職于 Eindhoven Unviersity of Technology.1984年至1999年，作為計算機系系主任任職與美國UT Austin分校，并于1999年退休。2002年8月6日在荷蘭Nuenen自己的家中與世長辭 Dijkstra 最短路徑算法被廣泛的應用在網絡協議方面，如OSPF。 Edsger Dijkstra是1950年代ALGOL 語言的一個主要貢獻者。ALGOL高級編程語言已經成為結構清晰，數學基 礎嚴謹的一個典范。E. W. Dijkst

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

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

47、圖所示的單行線交通網，每個弧旁邊的數字表示這條單行線的長度。現在一個人要從示這條單行線的長度。現在一個人要從v1出發，經過出發，經過這個交通網到達這個交通網到達v8，要尋求是總路程最短的線路。，要尋求是總路程最短的線路。1) 賦權圖中從給定點到其余頂點的最短路賦權圖中從給定點到其余頂點的最短路636234102312624101v39v5v2v1v4v6v7v8v 從從v1到到v8的路線是很多的。比如從的路線是很多的。比如從v1出發，經過出發，經過v2,v5到達到達v8或者從或者從v1出發，經過出發，經過v4，v6，v7到達到達v8等。等。但不但不同的路線，經過的總長度是不同的同的路線，經過的

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

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

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

51、性質：最短路是一條路，最短路上最短路是一條路，最短路上的任一子段也是最短路。的任一子段也是最短路。 Dijkstra 算法的基本思想是：按距算法的基本思想是：按距 v0 從近到從近到遠為順序，依次求得遠為順序，依次求得 v0 到圖到圖 G 的各頂點的最短路的各頂點的最短路和距離，直至頂點和距離，直至頂點 v0（或直至圖（或直至圖 G 的所有頂點）。的所有頂點）。Dijkstra算法的基本思想: 從從vs出發，逐步向外尋找最短路。在運算過程中，出發，逐步向外尋找最短路。在運算過程中，與每個點對應，記錄一個數，叫做一個點的與每個點對應，記錄一個數，叫做一個點的標號標號。它。它或者表示從或者表示從v

52、s到該點的最短路權（叫做到該點的最短路權（叫做P 標號標號），或者），或者表示從表示從vs到該點最短路權的上界（叫做到該點最短路權的上界（叫做T 標號標號）。算法）。算法的每一步是去修改的每一步是去修改T 標號，把某一個具有標號，把某一個具有T 標號的點改標號的點改變為具有變為具有P 標號的點，使圖標號的點，使圖D 中具有中具有P 標號的頂點多一標號的頂點多一個。這樣，至多經過個。這樣，至多經過P -1步，就可求出從步，就可求出從 vs到各點到各點vj的的最短路。最短路。 P(v1)636234102312624101v4v2v6v7v8v9v5v3以例以例1為例說明這個基本思想。為例說明這個

53、基本思想。 在例在例1中，中，S=1。因為。因為wij 0，d（v1,v1）= 0。這時，。這時，v1是是具有具有P標號的點。現在看從標號的點。現在看從v1出發的三條弧（出發的三條弧（v1,v2）,（v1,v3）,（v1,v4）。如果一個人從）。如果一個人從 v1 出發沿（出發沿（v1,v2）到達）到達 v2，路程：，路程：d（v1,v1）+ w12= 6單位。單位。 v1 如果從如果從v1出發，沿（出發，沿（v1,v3）到達）到達v3，則是，則是d（v1,v1）+w13=3單位。同理，沿（單位。同理，沿（v1,v4）到達）到達v4，是，是d（v1,v1）+ w14 = 1單位。單位。故他故他

54、從從v1出發到達出發到達v4的最短路必是（的最短路必是（v1,v4），），d（v1,v4）= 1。這是因為從這是因為從v1到達到達v4的任一條路，假如是（的任一條路，假如是（v1,v4），則必先沿），則必先沿（v1,v2）到達）到達 v2，或者沿（，或者沿（v1,v3）到達）到達 v3，而這時路程已是，而這時路程已是6或者或者3單位。單位。P(v1)636234102312624101v4v2v6v7v8v9v5v3v1看從看從v1出發的三條弧（出發的三條弧（v1,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 由于所有的權由于所有的權 wij 0,因此因此,不論他如何再從不論他如何再從v2或者或者v3 到達到達 v4，所經過的總路程都不會比，所經過的總路程都不會比1少，于是就有少，于是就有d（v1,v4）=1。這樣就使。這樣就使v4變成具有變成具有P標號的點。標號的點。P(v1)636234102312624101v4v6v7v8v9v3v1P(v4) 現在看從現在看從 v1 和和 v4 指向其余點的弧指向其余點的弧.如上所述，從如上所述，從v1出發，分別沿（出發，分別沿（v1,v

56、2）,（v1,v3）到達）到達v2,v3，經過的路，經過的路程是程是6或者或者3單位單位.從從v4出發沿（出發沿（v4,v6）到達）到達v6，經過的，經過的路程是路程是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) 根據同樣的理由，可以斷定，從根據同樣的理由，可以斷定，從v1到達到達v3的最短路的最短路是（是（v1,v3），），d（v1,v3）= 3。

57、這樣，又使點這樣，又使點v3變為具有變為具有P 標號的點，不斷重復以標號的點，不斷重復以上過程，就可以求出從上過程，就可以求出從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最短路最短

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

59、為P標號，則停止，否則用標號，則停止，否則用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