1、運籌學圖與網絡優化1第七章第七章 圖與網絡優化圖與網絡優化圖是最直觀的模型圖是最直觀的模型運籌學圖與網絡優化2BACD圖論圖論 Graph Theory 哥尼斯堡七橋問題哥尼斯堡七橋問題 (Knigsberg Bridge Problem) Leonhard Euler (1707-1783) 在在1736年發表第一篇圖論年發表第一篇圖論方面的論文，奠基了圖論中的一些基本定理方面的論文，奠基了圖論中的一些基本定理 很多問題都可以用點和線來表示，一般點表示實體，很多問題都可以用點和線來表示，一般點表示實體，線表示實體間的關聯線表示實體間的關聯ABCD運籌學圖與網絡優化37.1 圖與網絡的基本概念

2、圖與網絡的基本概念1 圖與網絡圖圖與網絡圖 節點節點 (Vertex) 物理實體、事物、概念物理實體、事物、概念 一般用一般用 vi 表示表示 邊邊 (Edge) 節點間的連線，表示有節點間的連線，表示有關聯關聯 一般用一般用 eij 表示表示 圖圖 (Graph) 節點和邊的集合節點和邊的集合 一般用一般用 G(V,E) 表示表示 點集點集 V=v1,v2, vn 邊集邊集E=eij 網絡圖網絡圖 (Network)邊上具有表示連接強度邊上具有表示連接強度的權值，如的權值，如 wij又稱又稱加權圖加權圖(Weighted graph)v1v5v4v3v2e12e34e13e24e22e13e

3、45圖圖 7.2運籌學圖與網絡優化42 無向圖與有向圖無向圖與有向圖 所有邊都沒有方向的圖稱為無向圖，如圖所有邊都沒有方向的圖稱為無向圖，如圖7.2 在無向圖中在無向圖中 eij=eji，或，或 (vi, vj)=(vj, vi) 當所有邊都有方向時，稱為有向圖，用當所有邊都有方向時，稱為有向圖，用D(V,A)表示表示 在有向圖中，有向邊又稱為在有向圖中，有向邊又稱為弧弧，用，用 aij表示，表示，i, j 的順序的順序是不能顛倒的，圖中弧的方向用箭頭標識是不能顛倒的，圖中弧的方向用箭頭標識 圖中既有邊又有弧，稱為混合圖圖中既有邊又有弧，稱為混合圖運籌學圖與網絡優化53 端點，關聯邊，相鄰，次

4、端點，關聯邊，相鄰，次 圖中可以只有點，而沒有邊；而有邊必有點圖中可以只有點，而沒有邊；而有邊必有點 若節點若節點vi, vj 之間有一條邊之間有一條邊 eij，則稱，則稱 vi, vj 是是 eij 的的端點端點(end vertex)，而，而 eij 是節點是節點 vi, vj 的的關聯邊關聯邊(incident edge) 同一條邊的兩個端點稱為同一條邊的兩個端點稱為相鄰相鄰(adjacent)節點節點，具有共同，具有共同端點的邊稱為端點的邊稱為相鄰邊相鄰邊 一條邊的兩個端點相同，稱為一條邊的兩個端點相同，稱為自環自環(self-loop)；具有兩；具有兩個共同端點的兩條邊稱為個共同端點

5、的兩條邊稱為平行（多重）邊平行（多重）邊(parallel edges) 既沒有自環也沒有平行邊的圖稱為既沒有自環也沒有平行邊的圖稱為簡單圖簡單圖(simple graph) 在無向圖中，與節點相關聯邊的數目，稱為該節點的在無向圖中，與節點相關聯邊的數目，稱為該節點的“次次”(degree)，記為，記為 d ；次數為奇數的點稱為；次數為奇數的點稱為奇點奇點(odd),次數為偶數的點稱為次數為偶數的點稱為偶點偶點(even)；圖中都是偶點的；圖中都是偶點的圖稱為偶點圖圖稱為偶點圖(even graph)運籌學圖與網絡優化63 端點，關聯邊，相鄰，次端點，關聯邊，相鄰，次 有向圖中，由節點向外指的

6、弧的數目稱有向圖中，由節點向外指的弧的數目稱為正次數，記為為正次數，記為 d+，指向該節點的弧的，指向該節點的弧的數目稱為負次數，記為數目稱為負次數，記為 d 次數為次數為 0 的點稱為的點稱為孤立點孤立點(isolated vertex) ，次數為次數為 1 的點稱為的點稱為懸掛點懸掛點(pendant vertex)定理定理 1：圖中點的次數和是邊數個：圖中點的次數和是邊數個2倍倍定理定理 2：圖中奇點的個數總是偶數個：圖中奇點的個數總是偶數個 運籌學圖與網絡優化74 鏈，圈，初等鏈，初等圈，簡單鏈（圈）鏈，圈，初等鏈，初等圈，簡單鏈（圈） 相鄰節點的序列相鄰節點的序列 v1 ,v2 ,

7、vn 構成一條構成一條鏈鏈(link)p178； 在無向圖中，節點不重復出現的鏈稱為在無向圖中，節點不重復出現的鏈稱為初等鏈初等鏈； 首尾相連的鏈稱為首尾相連的鏈稱為圈圈(loop) ；首尾相連的首尾相連的初等鏈稱為初等鏈稱為初等圈初等圈； 邊不重復出現的鏈（圈）稱為邊不重復出現的鏈（圈）稱為簡單鏈簡單鏈（圈）（圈）運籌學圖與網絡優化8 5 完全圖，偶圖完全圖，偶圖 簡單圖中任意兩點間都有邊相連，則稱為完全簡單圖中任意兩點間都有邊相連，則稱為完全圖。圖。 n個點的完全圖有個點的完全圖有n（n-1）/2條邊條邊 若圖的頂點能分成兩個互不相交的非空集合若圖的頂點能分成兩個互不相交的非空集合V1、V

8、2，其在同一個集合中任意兩點間都沒有邊相，其在同一個集合中任意兩點間都沒有邊相連，則稱為偶圖（二部圖）。連，則稱為偶圖（二部圖）。 若偶圖的頂點集合若偶圖的頂點集合V1、V2之間的每一對不同之間的每一對不同頂點都有一條邊相連，則稱為完全偶圖。頂點都有一條邊相連，則稱為完全偶圖。 在完全偶圖中，若頂點分別為在完全偶圖中，若頂點分別為n1、n2，有，有n1n2條邊條邊 運籌學圖與網絡優化9 6 子圖，部分圖；連通圖，成分子圖，部分圖；連通圖，成分 設有兩個圖設有兩個圖 G1(V1, E1), G2(V2, E2), 若若V2 V1, E2 E1， 則則 G2 是是 G1 的子圖。若的子圖。若V2

9、=V1, E2 E1， 則則 G2 是是 G1 的的部分圖（支撐子圖）。部分圖（支撐子圖）。 無向圖中，若任意兩點間至少存在一條無向圖中，若任意兩點間至少存在一條鏈鏈，則稱為，則稱為連連通圖通圖(connected graph)，否則為，否則為非連通圖非連通圖( discon-nected graph)；非連通圖中的每個；非連通圖中的每個連通子（分）圖連通子（分）圖稱為稱為成分成分 (component) 鏈，圈，路徑鏈，圈，路徑(簡稱路簡稱路)，回路都是原圖的子圖，回路都是原圖的子圖 支撐子圖也是子圖，子圖不一定是支撐子圖。支撐子圖也是子圖，子圖不一定是支撐子圖。 平面圖平面圖(planar

10、 graph)，若在平面上，若在平面上可以可以畫出該圖而沒畫出該圖而沒有任何邊相交有任何邊相交運籌學圖與網絡優化107基礎圖，路，回路，歐拉回路基礎圖，路，回路，歐拉回路 在有向圖在有向圖D(V,A)中去掉箭頭，稱為中去掉箭頭，稱為D的的基礎圖，基礎圖，G（D） 在有向圖中，在有向圖中，鏈鏈 路路 圈圈 回路回路 走過圖中所有邊且每條邊僅走一次的閉行走稱為走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉歐拉回路回路定理定理 ：偶點圖一定存在歐拉回路：偶點圖一定存在歐拉回路(一筆畫定理一筆畫定理)運籌學圖與網絡優化117.2 樹圖與最小支撐樹樹圖與最小支撐樹 一般研究無向圖一般研究無向圖 樹圖：倒

11、置的樹，樹圖：倒置的樹，根根(root)在上，在上，樹葉樹葉(leaf)在下在下 多級輻射制的電信網絡、管理的指標體系、家譜、分多級輻射制的電信網絡、管理的指標體系、家譜、分類學、組織結構等都是典型的樹圖類學、組織結構等都是典型的樹圖C1C2C3C4根根葉葉運籌學圖與網絡優化12 7.2.1 樹的定義及其性質樹的定義及其性質 任兩點之間有且只有一條鏈的圖稱為任兩點之間有且只有一條鏈的圖稱為樹樹(tree)。 無圈的連通圖稱為無圈的連通圖稱為樹樹(tree)p180。 記為記為T（V，E） 樹的性質樹的性質：p180-181 任何樹必存在次數為任何樹必存在次數為 1 的點的點 具有具有 n 個節

12、點的樹個節點的樹 T 的邊恰好為的邊恰好為 n 1 條，條，反之，任何有反之，任何有n 個節點，個節點， n 1 條邊的連通條邊的連通圖必是一棵樹圖必是一棵樹 最少邊的連通子圖，樹中必不存在回路最少邊的連通子圖，樹中必不存在回路 運籌學圖與網絡優化137.2.2 支撐樹支撐樹 樹樹 T 是連通圖是連通圖 G 的的支撐樹支撐樹(spanning tree)，若，若 T 是是 G的支撐圖且是樹圖的支撐圖且是樹圖 樹枝總長最小的支撐樹稱為最小支樹枝總長最小的支撐樹稱為最小支撐樹。撐樹。運籌學圖與網絡優化14支撐樹支撐樹ACDBACDBACDBADCB連通圖連通圖 G 最小支撐樹？最小支撐樹？運籌學圖

13、與網絡優化15 7.2.3 最小支撐樹最小支撐樹 有有n 個鄉村，各村間道路的長度是已知的，如何個鄉村，各村間道路的長度是已知的，如何敷設光纜線路使敷設光纜線路使 n 個鄉村連通且總長度最短個鄉村連通且總長度最短 顯然，這要求在已知邊長的網路圖中找最小支撐顯然，這要求在已知邊長的網路圖中找最小支撐樹樹 最小支撐樹的算法最小支撐樹的算法： Kruskal 算法：將圖中所有邊按權值從小到大排算法：將圖中所有邊按權值從小到大排列，依次選所剩最小的邊加入邊集列，依次選所剩最小的邊加入邊集 T，只要不和，只要不和前面加入的邊構成回路，直到前面加入的邊構成回路，直到 T 中有中有 n 1 條邊，條邊，則則

14、 T 是最小支撐樹是最小支撐樹運籌學圖與網絡優化16 Kruskal 算法基于下述定理算法基于下述定理定理定理 4.1 指定圖中任一點指定圖中任一點vi，如果，如果 vj 是距是距 vi 最近的最近的相鄰節點，則關聯邊相鄰節點，則關聯邊 eij 必在某個最小支撐樹中。必在某個最小支撐樹中。推論推論 4.1 將網路中的節點劃分為兩個不相交的集合將網路中的節點劃分為兩個不相交的集合V1和和V2，V2=V V1，則，則V1和和V2間權值最小的邊必間權值最小的邊必定在某個最小支撐樹中。定在某個最小支撐樹中。 最小支撐樹不一定唯一最小支撐樹不一定唯一 定理定理 4.1 推論推論4.1是一個構造性定理，它

15、指示了找是一個構造性定理，它指示了找最小支撐樹的有效算法最小支撐樹的有效算法運籌學圖與網絡優化17 方法一（方法一（ Prim Prim 算法）算法）：1 1、根據網路寫出邊權矩陣，兩點間若沒有邊，則用、根據網路寫出邊權矩陣，兩點間若沒有邊，則用 表示；表示；2 2、從、從 v v1 1 開始標記，在第一行打開始標記，在第一行打 ，劃去第一列；，劃去第一列；3 3、從所有打、從所有打 的行中找出尚未劃掉的最小元素，對該元素畫的行中找出尚未劃掉的最小元素，對該元素畫圈，劃掉該元素所在列，與該列數對應的行打圈，劃掉該元素所在列，與該列數對應的行打 ；4 4、若所有列都劃掉，則已找到最小生成樹、若所

16、有列都劃掉，則已找到最小生成樹( (所有畫圈元素所對所有畫圈元素所對應的邊應的邊) )；否則，返回第；否則，返回第 3 3 步。步。 該算法中，打該算法中，打 行對應的節點在行對應的節點在 V V1 1中，未劃去的列在中，未劃去的列在 V V2 2中中 97125 .19179810787111275 . 9165 .195 . 9101710111610v1v4v6v3v5v2101081177169.51712919.5 v1v4v6v3v5v2108779.5運籌學圖與網絡優化1812222312222333445方法二（避圈法）方法二（避圈法）開始選一條最小權的邊，以后每一步中，開始選

17、一條最小權的邊，以后每一步中，總從未被選取的邊中選一條權最小的邊，并使之與已選取的總從未被選取的邊中選一條權最小的邊，并使之與已選取的邊不構成圈，直到選出邊不構成圈，直到選出n-1條邊為止。條邊為止。PrimPrim算法是多項式算法算法是多項式算法PrimPrim算法可以求最大生成樹算法可以求最大生成樹網路的邊權可以有多種解釋，如效率網路的邊權可以有多種解釋，如效率次數受限的最小生成樹次數受限的最小生成樹尚無有效算法尚無有效算法運籌學圖與網絡優化19方法三（破圈法）方法三（破圈法）任取一個圈，從圈中去掉一條權最大的邊。在余下的圖任取一個圈，從圈中去掉一條權最大的邊。在余下的圖 中，重復這個步驟

18、，直到出現一個不含圈的圖為止。中，重復這個步驟，直到出現一個不含圈的圖為止。122223334451222233345122223334122223331222332122232運籌學圖與網絡優化20斯坦納樹問題斯坦納樹問題 假設我們在北京、上海、西安三假設我們在北京、上海、西安三城市之間架設電話線，一種辦法是分城市之間架設電話線，一種辦法是分別聯通北京別聯通北京-上海和北京上海和北京-西安。另西安。另一種辦法是選第四個點，假設鄭州。一種辦法是選第四個點，假設鄭州。由此分別向三城市架線，可能你不會由此分別向三城市架線，可能你不會想到第二種辦法所用的電話線只是第想到第二種辦法所用的電話線只是第一

19、種辦法的一種辦法的86.6%，即可取得比第一，即可取得比第一種辦法節約種辦法節約13%的顯著經濟效益。這的顯著經濟效益。這就是離散數學界就是離散數學界30年代提出的著名的年代提出的著名的斯坦納樹問題，但一直未能得到證明。斯坦納樹問題，但一直未能得到證明。 運籌學圖與網絡優化21 1967年大名鼎鼎的貝爾電話公司，遇上了一家精明的用戶航空公司，這家用戶要求在第四個點的位置上架上電話線。這樣使得電話公司不僅要拉新線，增加服務網點，而且要減少收費。這件事的連鎖反應迫使電話公司改變了堅持長達10年按照最少發生樹長度收費的原則，并且不得不對最短網絡問題進行研究。 運籌學圖與網絡優化22斯坦納比 貝爾實驗

20、室數學中心主任波雷克和研究員吉爾伯特對斯坦納比問題作了許多研究，根據自己多年研究所得提出如下猜想：對歐氏平面上的任何有限點集，其最小的Steiner樹同最小發生樹的長度之比(稱為Steiner比，即斯坦納比)不小于3/2。 運籌學圖與網絡優化23正三角形加點可以節省最多。 運籌學圖與網絡優化24運籌學圖與網絡優化25運籌學圖與網絡優化26運籌學圖與網絡優化27 由于其在運輸、通信和計算機等現代經濟與科技中由于其在運輸、通信和計算機等現代經濟與科技中的重要作用，近幾十年來它的研究進展越來越快。的重要作用，近幾十年來它的研究進展越來越快。1985年，格拉姆和金芳容借助于計算機進行了大量運年，格拉姆

21、和金芳容借助于計算機進行了大量運算，證明了斯坦納比大于算，證明了斯坦納比大于0.824，雖距，雖距0.866不遙遠，卻不遙遠，卻始終未能達到最終目標。美國數學會主席曾感嘆道：始終未能達到最終目標。美國數學會主席曾感嘆道：“這問題已經公開了這問題已經公開了22年，這件事總令你不安，你不年，這件事總令你不安，你不能證明這樣初級的東西。能證明這樣初級的東西。”也許源于猜想提出的戲劇也許源于猜想提出的戲劇性背景，也許源于理論意義以及貝爾實驗室的學術權性背景，也許源于理論意義以及貝爾實驗室的學術權威，也許源于數學家對形成初等而又難解問題的愛好，威，也許源于數學家對形成初等而又難解問題的愛好，人們對這個問

22、題的研究歷久不衰。人們對這個問題的研究歷久不衰。 斯坦納比的證明（1）運籌學圖與網絡優化28斯坦納比的證明（2） 1990年，年，41歲的堵丁柱因為攻克這一問題而成為世歲的堵丁柱因為攻克這一問題而成為世界數學界冒出的奇葩。他與貝爾實驗室黃光明研究員界數學界冒出的奇葩。他與貝爾實驗室黃光明研究員合作，找到了一個全新途徑，給出了吉爾伯特合作，找到了一個全新途徑，給出了吉爾伯特-波雷克波雷克猜想完整的證明。證明的核心是關于鞍點的一個定理。猜想完整的證明。證明的核心是關于鞍點的一個定理。其主要思想是，首先在歐氏平面含其主要思想是，首先在歐氏平面含n點的集合與點的集合與2n-3維維空間的點之間建立一一對

23、應的關系，使得猜想可以化空間的點之間建立一一對應的關系，使得猜想可以化為為2n-3維空間上函數的極值問題。然后利用鞍點定理維空間上函數的極值問題。然后利用鞍點定理找出可以達到極值的臨界點應滿足的必要條件。之后，找出可以達到極值的臨界點應滿足的必要條件。之后，再將此條件轉換為臨界點對應的點集上的幾何性質。再將此條件轉換為臨界點對應的點集上的幾何性質。最后，利用這幾何性質確定幾何結構，驗證該猜想。最后，利用這幾何性質確定幾何結構，驗證該猜想。 運籌學圖與網絡優化29斯坦納比的證明（3） 證明于證明于1990年年10月在會議上正式公開，月在會議上正式公開，紐約時紐約時報報立刻做了報道。接著立刻做了報

24、道。接著科學科學雜志、雜志、科學新聞科學新聞新科學論新科學論SLAM新聞新聞等報刊上出現了許多報等報刊上出現了許多報道。值得提及的道。值得提及的SLAM新聞新聞在頭版上用了個有趣在頭版上用了個有趣的的“在計算機時代歐氏幾何的歐氏平面上在計算機時代歐氏幾何的歐氏平面上n點的集合點的集合2n-3維空間的點力與運氣維空間的點力與運氣”。在。在不列顛百科全不列顛百科全書書1992年鑒年鑒中，該證明進一步被列為入選的中，該證明進一步被列為入選的6項數學項數學成果的第一項。因此，堵丁柱也榮獲了中國科學院自成果的第一項。因此，堵丁柱也榮獲了中國科學院自然科學一等獎、國家科技進步二等獎和中國青年科學然科學一等

25、獎、國家科技進步二等獎和中國青年科學家獎等殊榮。家獎等殊榮。 運籌學圖與網絡優化307.3 最短路問題最短路問題p185p185 4.5.1.2 狄克斯特拉算法狄克斯特拉算法 (Dijkstra algorithm, 1959)計算兩節點之間或一個節點到所有節點之間的最短路計算兩節點之間或一個節點到所有節點之間的最短路令令 dij 表示表示 vi 到到 vj 的直接距離的直接距離(兩點之間有邊兩點之間有邊)，若兩點之間，若兩點之間沒有邊，則令沒有邊，則令 dij = ；令；令 dii = 0，s 表示始點，表示始點，t 表示終表示終點點0、令、令始點始點Ts=0，并用，并用框框住，框框住，所有

26、其它節點臨時標記所有其它節點臨時標記 Tj= ；1、從、從 vs 出發，對其相鄰節點出發，對其相鄰節點 vj1 進行臨時標記，有進行臨時標記，有 Tj1=ds,j1 ；2、在所有臨時標記中找出最小者，、在所有臨時標記中找出最小者，并并框住作為框住作為永久標記永久標記，設其，設其為為 vr ，加粗該邊。，加粗該邊。若此時全部節點都是永久標記，算法結束若此時全部節點都是永久標記，算法結束；否則到下一步；否則到下一步；3、從新的永久標記節點、從新的永久標記節點 vr 出發，對其相鄰的臨時標記節點進行出發，對其相鄰的臨時標記節點進行再標記，設再標記，設 vj2 為其相鄰節點，則為其相鄰節點，則 Tj2

27、=minTj2, Tr+dr,j2 ，返回，返回第第2步。步。運籌學圖與網絡優化31例例1 1 狄克斯特拉算法狄克斯特拉算法2s5t6341074918815220230 0 815101215113113運籌學圖與網絡優化32最短路問題的標號過程 Dijkstra算法的基本思想：若vs,v1,vk是從vs到vk的最短路，則vs,v1,vi是從vs到vi的最短路。 T(臨時)標號：從vs到某一節點最短距離的上界。 P(永久)標號： 從vs到某一節點的最短距離。運籌學圖與網絡優化33步驟： 給vs標上永久標號P(vs)=0，其余節點標上臨時標號T(vj)= (1)若節點vi是剛得到P標號的點。把

28、與vi有弧(邊)直接相連而且有屬于T標號的節點，改為下列T標號T(vj)=minT(vj),P(vi)+dij (2)把T標號中標號最小的節點vj0的臨時標號T(vj0)改為P(vj0),直至算法終止;否則轉(1)運籌學圖與網絡優化34例 求節點v1到節點v5的最短距離及其路線vSv1v2v3v4v5122233344解 P(vs)=0 T(vj)=,j=1,5第一步：T(v1)=minT(v1),P(vs)+ds1=min,0+4=4 (1)與節點vs直接相連的臨時標號的節點為 v1, v2，將這兩個節點的臨時標號改為T(v2)=minT(v2),P(vs)+ds2=min,0+3=30運籌

29、學圖與網絡優化35 (2)在所有T標號中，最小的為T(v2)=3,于是令P(v2)=3vSv1v2v3v4v5122233344043第二步： (1)與節點v2直接相連的臨時標號的節點為V1和v4，把這兩個節點的T標號改為T(v1)=minT(v1),P(v2)+d21=min4,3+2=4T(v4)=minT(v4),P(v2)+d24=min,3+2=5 (2).在所有T變化中，T(v1)=4最小，于是令P(v1)=45運籌學圖與網絡優化36第三步： (1).與節點v1相連的臨時標號的節點為v3,v4，把這兩個節點的T標號改為T(v3)=minT(v3),P(v1)+d13=min,4+3

30、=7T(v4)=minT(v4),P(v1)+d14=min5,4+1=5 (2).在T標號中，T(v4)=5最小，令P(v4)=5vSv1v2v3v4v51222333440453 7運籌學圖與網絡優化37第四步： (1).與節點v4相連的T標號有v3,v5把這兩個節點的T標號改為T(v3)=minT(v3),P(v4)+d43=min7,5+2=7T(v5)=minT(v5),P(v5)+d45=min,5+4=9vSv1v2v3v4v5122233344045379 (2).T(v3)最小,P(v3)=7運籌學圖與網絡優化38第五步： (1).與v3相連的臨時標號有v5T(v5)=min

31、T(v5),P(v3)+d35=min9,7+3=9(2).P(v5)=9最短路線：vsv1v4 v5 vsv2v4 v5vSv1v2v3v4v5122233344045379運籌學圖與網絡優化39也可以用表格的形式求解。也可以用表格的形式求解。p190運籌學圖與網絡優化40 Dijkstra最短路算法的最短路算法的特點特點和和適應范圍適應范圍一種隱階段的動態規劃方法，而且是正向遞推一種隱階段的動態規劃方法，而且是正向遞推每次迭代只有一個節點獲得永久標記，若有兩個或兩個以上每次迭代只有一個節點獲得永久標記，若有兩個或兩個以上節點的臨時標記同時最小，可任選一個永久標記；總是從一節點的臨時標記同時

32、最小，可任選一個永久標記；總是從一個新的永久標記開始新一輪的臨時標記，是一種個新的永久標記開始新一輪的臨時標記，是一種深探法深探法被框住的永久標記被框住的永久標記 Tj 表示表示 vs 到到 vj 的最短路，因此的最短路，因此 要求要求 dij 0，第第 k 次迭代得到的永久標記，其最短路中最多有次迭代得到的永久標記，其最短路中最多有 k 條邊，因條邊，因此最多有此最多有n 1 次迭代次迭代如果只求如果只求 vs 到到 vt 的最短路，則當的最短路，則當 vt 得到永久標記算法就結束得到永久標記算法就結束了；但算法復雜度是一樣的了；但算法復雜度是一樣的應用應用 Dijkstra 算法算法 n

33、1 次次 ，可以求所有點間的最短路，可以求所有點間的最短路vs 到所有點的最短路也是一棵生成樹，但不是最小生成樹到所有點的最短路也是一棵生成樹，但不是最小生成樹運籌學圖與網絡優化41Warshall-Floyd算法算法 (1962)Warshall-Floyd算法可以解決有算法可以解決有負權值負權值邊邊( (弧弧) )的最短路問題的最短路問題 該算法是一種整體算法，一次求出所有點間的最短路該算法是一種整體算法，一次求出所有點間的最短路 該算法不允許有該算法不允許有負權值回路負權值回路，但可以發現負權值回路，但可以發現負權值回路 該算法基于基本的三角運算該算法基于基本的三角運算定義定義 對給定的

34、點間初始距離矩陣對給定的點間初始距離矩陣dij，令，令dii= ， i。對一。對一 個固定點個固定點 j，運算，運算 dik=mindik, dij+djk, i, k j , 稱為稱為 三角三角運算。運算。( (注意，這里允許注意，這里允許 i=k) )定理定理 依次對依次對 j=1,2,n 執行三角運算，則執行三角運算，則 dik 最終等于最終等于 i 到到 k 間最短路的長度。間最短路的長度。kjidijdjkdik運籌學圖與網絡優化42Floyd-Warshall 算法算法 (1962)for i=1 to n do dii= ;for all eij=0; for j=1 to n

35、do for i=1 to n do if i j then for k=1 to n do if k j then begin dik=mindik, dij+djk; if dikdij+djk then eik=j end;例例 1 中中 1 到到 7 點的最短路是點的最短路是 1-2-5-7查伴隨矩陣查伴隨矩陣 E 的第一行的第一行123456710020255 若網路中存在負回路，則計算若網路中存在負回路，則計算中，某些中，某些 dii 會小于會小于0，此時應，此時應中斷算法中斷算法 顯然，顯然，Floyd 算法要進行算法要進行 n(n-1)2 次加法和比較次加法和比較 如何回溯找出

36、任兩點之間的最如何回溯找出任兩點之間的最短路？短路？ 在在Floyd 算法中設一伴隨矩陣算法中設一伴隨矩陣E=eik， eik 記錄了記錄了 i 到到 k 最短最短路中最后一個中間節點路中最后一個中間節點運籌學圖與網絡優化43小結小結 最短路有廣泛的應用最短路有廣泛的應用 (4.3.4節節 市話局擴容方案市話局擴容方案) 最短路的多種形式：無向圖，有向圖無循環圈，有向最短路的多種形式：無向圖，有向圖無循環圈，有向圖，混合圖，無負邊權，有負邊權，有負回路，圖，混合圖，無負邊權，有負邊權，有負回路，k-最最短路等短路等 當存在負權值邊時，當存在負權值邊時，Floyd算法比算法比Dijkstra算法

37、效率高，算法效率高，且程序極簡單。但且程序極簡單。但Dijkstra算法靈活算法靈活 若圖是前向的，則若圖是前向的，則Dijkstra算法也可以求兩點間最長路算法也可以求兩點間最長路 一般情況下，兩點間最長路是一般情況下，兩點間最長路是 NP-complete，但最短，但最短路是路是 P算法算法 兩點間兩點間k-最短路：分為邊不相交的和邊相交的最短路：分為邊不相交的和邊相交的 求邊求邊不相交的不相交的k-最短路非常容易：先求最短路，將該最短路非常容易：先求最短路，將該最短路中的邊從網路刪去，再用最短路中的邊從網路刪去，再用Dijkstra算法可求次最算法可求次最短路，以此類推短路，以此類推運籌

38、學圖與網絡優化44 4.5.1.3 最短路應用舉例最短路應用舉例市話擴容市話擴容 ( (實裝率實裝率= =0.8) )年 號 年 號 0 1 2 3 4 5 6 7 8 9 10 11 12預測數 預測數 1.6 1.8 2.0 2.2 2.5 2.8 3.1 3.5 3.9 4.4 4.9 5.5 6.2t02000t64000t85000t96000t117000t128000t330001, 42, 76, 135, 124, 8.83, 8.31, 3.52, 6.04, 8.33, 7.15, 8.91, 32, 4.53, 6.84, 7.51, 2.52, 4.33, 5.5運籌

39、學圖與網絡優化457.4 網絡的最大流和最小截網絡的最大流和最小截 7.4.1 網絡流的概念網絡流的概念 p192 網絡流一般在有向圖上討論網絡流一般在有向圖上討論D=（V，A，C） 定義網絡上支路的定義網絡上支路的容量容量為其最大通過能力，記為為其最大通過能力，記為 cij ，支路上的實際支路上的實際流量流量記為記為 fij 。當支路上當支路上 fij = cij ，稱為，稱為飽和弧飽和弧 圖中規定一個發點圖中規定一個發點s s，一個收點，一個收點t;t;節點沒有容量限制，節點沒有容量限制，流在節點不會存儲流在節點不會存儲 集合集合f=fij |（vi,vj）A 稱為該網絡稱為該網絡D的一個

40、的一個流流fij（cij，fij）運籌學圖與網絡優化467.4 網絡的最大流和最小截網絡的最大流和最小截 7.4.1 網絡流的概念網絡流的概念 p193 集合集合f=fij |（vi,vj）A 稱為該網絡稱為該網絡D的一個的一個流流f 容量限制條件容量限制條件：0 fij cij 平衡條件平衡條件：tifvtsisifvxxijijvBvjivAvij)(,0)()()( 滿足上述條件的滿足上述條件的網絡網絡流稱為流稱為可行流可行流，總存在，總存在可行流，如可行流，如0流流f=0 |（vi,vj）A ；v= v(f)稱為從稱為從s s到到t t的可行流的可行流f的的流量。流量。 最大流問題也是

41、一個線性規劃問題最大流問題也是一個線性規劃問題viA(vi)B(vi)運籌學圖與網絡優化47最大流問題也是一個線性規劃問題最大流問題也是一個線性規劃問題p194ijijvBvjivAvijcftifvtsisifvxxfvvijij0)(,0)()(max)()(運籌學圖與網絡優化48 7.4.1 增廣鏈增廣鏈 當支路上當支路上 fij = cij ，稱為，稱為飽和弧飽和弧 當支路上當支路上 fij 0 ，稱為，稱為非零流弧非零流弧st5432(3,0)(5,3)(1,1)(5,1)(1,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1

42、,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffc 運籌學圖與網絡優化49 7.4.1 增廣鏈增廣鏈 鏈中與鏈中與 s 到到 t 方向一致的弧稱為方向一致的弧稱為前向弧前向弧，反，反之稱為之稱為后向弧后向弧 前向弧前向弧的全體記為的全體記為 后向弧后向弧的全體記為的全體記為st5432(3,0)(5,3)(1,1)(5,1)(1,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向

43、向弧弧前前向向弧弧ijijijijffc 運籌學圖與網絡優化50 7.4.1 增廣鏈增廣鏈 f為可行流，為可行流， 為為s到到t的鏈。若滿足下列條件稱為的鏈。若滿足下列條件稱為增廣鏈。增廣鏈。 中每一弧是中每一弧是非飽和弧非飽和弧 中每一弧是中每一弧是非零流弧非零流弧st5432(3,0)(5,3)(1,1)(5,1)(1,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffc 運籌學圖與網絡優化51 截集與截集容量截

44、集與截集容量定義定義：截集截集把網路分割為兩個成分的正向弧的集合，其中一把網路分割為兩個成分的正向弧的集合，其中一 個個成分包含成分包含 s 點，另一個包含點，另一個包含 t 點點 。（割、割集）。（割、割集） 一般包含一般包含 s 點的成分中的節點集合用點的成分中的節點集合用S表示，包含表示，包含 t 點的成點的成 分中的節點集合用分中的節點集合用S表示表示 截集容量截集容量是指截集中正向弧的是指截集中正向弧的容量容量之和之和SjSiijcSSc),(st5342(4,0)(3,0)(2,0)(1,0)(1,0)(5,0)(3,0)(2,0)(5,0)SS624運籌學圖與網絡優化52 定義定

45、義：最小最小截集截集是截集容量最小的截集（最小割）是截集容量最小的截集（最小割）st42314(4)2(1)5(5)3(1)3(2)5(3)9(7)7(7)6(3)141514121916161113運籌學圖與網絡優化53為任一截集任一可行流，其中，為),(),()(SSfSScfv.),( ,).,()(),( ,*為最小截集為最大流則為一截集，為一可行流SSfSScfvSSf.,:8*的增廣鏈當且僅當不存在關于為最大流定理ff運籌學圖與網絡優化54的增廣鏈不存在關于為最大流證明的增廣鏈當且僅當不存在關于為最大流定理*:.,:8ffffst5432(3,0)(5,3)(1,1)(5,1)(1

46、,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffc 運籌學圖與網絡優化55的增廣鏈不存在關于為最大流證明的增廣鏈當且僅當不存在關于為最大流定理*:.,:8ffffst134256(14,14)(9,9)(15,12)(16,15)(3,1)(12,12)(6,5)(4,4)(5,5)(22,22)(13,12)(7,5)(6,1)(19,13)運籌學圖與網絡優化56.,:8*的增廣鏈當且僅當不存在關于為最大流定理

47、ff定理p195 福特福特-富克森定理：網路的最大流等于最小截集容富克森定理：網路的最大流等于最小截集容量。量。運籌學圖與網絡優化57 7.4.2 確定網路最大流的標號法確定網路最大流的標號法 從任一個初始可行流出發，如從任一個初始可行流出發，如 0 流流 基本算法：找一條從基本算法：找一條從 s 到到 t 點的點的增廣鏈增廣鏈(augmenting path) 若在當前可行流下找不到增廣鏈，則已得到最大流若在當前可行流下找不到增廣鏈，則已得到最大流 增廣鏈中與增廣鏈中與 s 到到 t 方向一致的弧稱為方向一致的弧稱為前向弧前向弧，反之，反之后向弧后向弧 增廣過程：前向弧增廣過程：前向弧 f

48、ij=fij + ,后向弧后向弧 f ij=fij 增廣后仍是可行流增廣后仍是可行流 ，找從找從 s 到到 t 點的點的增廣鏈增廣鏈st5432(3,0)(5,3)(1,1)(5,1)(1,1) s2=4 5t=2 45=3 43=1 32=1增增廣廣量量 = min ij= min(4,1,1,3,2)= 1st5432(3,1)(5,4)(1,0)(5,2)(1,0) 后后向向弧弧前前向向弧弧ijijijijffc 運籌學圖與網絡優化58 最大流最小截的標號法步驟最大流最小截的標號法步驟第一步：標號過程，找一條增廣鏈第一步：標號過程，找一條增廣鏈1、給源點給源點 s 標號標號s+, (s)

49、= ，表示從，表示從 s 點有無限流出潛力點有無限流出潛力2、找出與已標號節點找出與已標號節點 i 相鄰的所有未標號節點相鄰的所有未標號節點 j，若，若(1) (i, j)是前向弧且飽和，則節點是前向弧且飽和，則節點 j 不標號；不標號；(2) (i, j)是前向弧且未飽和，則節點是前向弧且未飽和，則節點 j 標號為標號為i+, (j)，表示從節點，表示從節點 i 正正向流出，可增廣向流出，可增廣 (j)=min (i), cij fij ；(3) (j, i)是后向弧，若是后向弧，若 fji=0，則節點，則節點 j 不標號；不標號；(4) (j, i)是后向弧，若是后向弧，若 fji0，則節

50、點，則節點 j 標號為標號為i , (j)，表示從節點，表示從節點 j 流流向向 i，可增廣，可增廣 (j)=min (i), fji ；3、重復步驟重復步驟 2，可能出現兩種情況：，可能出現兩種情況：(1) 節點節點 t 尚未標號，但無法繼續標記，說明網路中已不存在增廣鏈，尚未標號，但無法繼續標記，說明網路中已不存在增廣鏈，當前流當前流 v(f) 就是最大流；所有獲標號的節點在就是最大流；所有獲標號的節點在 V 中，未獲標號節中，未獲標號節點在點在 V 中，中，V 與與 V 間的弧即為最小截集；算法結束間的弧即為最小截集；算法結束(2)節點節點 t 獲得標號，找到一條增廣鏈，由節點獲得標號，

51、找到一條增廣鏈，由節點 t 標號回溯可找出該增標號回溯可找出該增廣鏈；到第二步廣鏈；到第二步運籌學圖與網絡優化59 最大流最小截的標號法步驟最大流最小截的標號法步驟第二步：增廣過程第二步：增廣過程1、對、對增廣鏈中的前向弧，令增廣鏈中的前向弧，令 f =f+ (t)， (t) 為節點為節點 t 的標記值的標記值2、對對增廣鏈中的后向弧，令增廣鏈中的后向弧，令 f =f (t)3、非增廣鏈上的所有支路流量保持不變、非增廣鏈上的所有支路流量保持不變第三步：抹除圖上所有標號，回到第一步第三步：抹除圖上所有標號，回到第一步 以上算法是按廣探法描述的，但在實際圖上作業時，按深以上算法是按廣探法描述的，但在實際圖上作業時，按深探法進行更快捷探法進行更快捷 一次只找一條增廣鏈，增廣一次換一張圖一次只找一條增廣鏈，增廣一次換一張圖 最后一次用廣探法，以便找出最小截集最后一次用廣探法，以便找出最小截集運籌學圖與網絡優化60最大流最小截集的標號法舉例最大流最小截集的標號法舉例st134256(14,14)(9,9)(15,9)(16,1