1、精選優質文檔-傾情為你奉上第五章 圖與網絡模型及方法§1 概論 圖論起源于18世紀。第一篇圖論論文是瑞士數學家歐拉于1736 年發表的“哥尼斯堡的七座橋”。1847年，克希霍夫為了給出電網絡方程而引進了“樹”的概念。1857年，凱萊在計數烷的同分異構物時，也發現了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術語，就是如何找出一個連通圖中的生成圈，近幾十年來，由于計算機技術和科學的飛速發展，大大地促進了圖論研究和應用，圖論的理論和方法已經滲透到物理、化學、通訊科學、建筑學、生物遺傳學、心理學、經濟學、社會學等學科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯系。

2、如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關系的離散系統提供了一個數學模型，借助于圖論的概念、理論和方法，可以對該模型求解。哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋將普萊格爾河中的兩個島及島與河岸聯結起來問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點。當然可以通過試驗去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個問題，采用了建立數學模型的方法。他將每一塊陸地用一個點來代替，將每一座橋用連接相應兩點的一條線來代替，從而得到一個有四個“點

3、”，七條“線”的“圖”。問題成為從任一點出發一筆畫出七條線再回到起點。歐拉考察了一般一筆畫的結構特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數線相關聯，將這個判定法則應用于七橋問題，得到了“不可能走通”的結果，不但徹底解決了這個問題，而且開創了圖論研究的先河。圖與網絡是運籌學（Operations Research）中的一個經典和重要的分支，所研究的問題涉及經濟管理、工業工程、交通運輸、計算機科學與信息技術、通訊與網絡技術等諸多領域。下面將要討論的最短路問題、最大流問題、最小費用流問題和匹配問題等都是圖與網絡的基本問題。我們首先通過一些例子來了解網絡優化問題。例1 最短路問

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

5、安排名員工去完成項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大例4 中國郵遞員問題（CPPchinese postman problem）一名郵遞員負責投遞某個街區的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發，經過投遞區內每條街道至少一次，最后返回郵局）由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5 旅行商問題（TSPtraveling salesman problem）一名推銷員準備前往若干城市推銷產品。如何為他（她）設計一條最短的旅行路線（從駐地出發，經過每個城市

6、恰好一次，最后返回駐地）這一問題的研究歷史十分悠久，通常稱之為旅行商問題。例6 運輸問題（transportation problem）某種原材料有個產地，現在需要將原材料從產地運往個使用這些原材料的工廠。假定個產地的產量和家工廠的需要量已知，單位產品從任一產地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低上述問題有兩個共同的特點：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優安排或方案，數學上把這種問題稱為最優化或優化（optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達，數學上把這種與圖相關的結構稱為網絡（network）。與圖和網絡相

7、關的最優化問題就是網絡最優化或稱網絡優化 （netwok optimization）問題。所以上面例子中介紹的問題都是網絡優化問題。由于多數網絡優化問題是以網絡上的流（flow）為研究的對象，因此網絡優化又常常被稱為網絡流（network flows）或網絡流規劃等。下面首先簡要介紹圖與網絡的一些基本概念。§2 圖與網絡的基本概念 無向圖一個無向圖(undirected graph)是由一個非空有限集合和中某些元素的無序對集合構成的二元組，記為。其中稱為圖的頂點集（vertex set）或節點集（node set）， 中的每一個元素稱為該圖的一個頂點（vertex）或節點（node）

8、；稱為圖的邊集（edge set），中的每一個元素(即中某兩個元素的無序對) 記為或 ，被稱為該圖的一條從到的邊（edge）。當邊時，稱為邊的端點，并稱與相鄰（adjacent）；邊稱為與頂點關聯（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖中相鄰。邊上賦權的無向圖稱為賦權無向圖或無向網絡（undirected network）。我們對圖和網絡不作嚴格區分，因為任何圖總是可以賦權的。一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖的頂點數用符號或表示，邊數用或表示。當討論的圖只有一個時，總是用來表示這個圖。從而在圖論符號中我們常略去字母，例如，分別用和代替和。

9、端點重合為一點的邊稱為環(loop)。一個圖稱為簡單圖(simple graph)，如果它既沒有環也沒有兩條邊連接同一對頂點。 有向圖定義 一個有向圖（directed graph或 digraph）是由一個非空有限集合和中某些元素的有序對集合構成的二元組，記為。其中稱為圖的頂點集或節點集， 中的每一個元素稱為該圖的一個頂點或節點；稱為圖的弧集（arc set），中的每一個元素(即中某兩個元素的有序對) 記為或，被稱為該圖的一條從到的弧（arc）。當弧時，稱為的尾（tail），為的頭（head），并稱弧為的出弧（outgoing arc），為的入弧（incoming arc）。對應于

10、每個有向圖，可以在相同頂點集上作一個圖，使得對于的每條弧，有一條有相同端點的邊與之相對應。這個圖稱為的基礎圖。反之，給定任意圖，對于它的每個邊，給其端點指定一個順序，從而確定一條弧，由此得到一個有向圖，這樣的有向圖稱為的一個定向圖。以下若未指明“有向圖”三字，“圖”字皆指無向圖。 完全圖、二分圖每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(complete graph)。個頂點的完全圖記為。若，（這里表示集合中的元素個數），中無相鄰頂點對，中亦然，則稱為二分圖(bipartite graph)；特別地，若，則，則稱為完全二分圖，記成。 、 子圖圖叫做圖的子圖（subgraph），記作，如果

11、，。若是的子圖，則稱為的母圖。的支撐子圖（spanning subgraph，又成生成子圖）是指滿足的子圖。 頂點的度設，中與關聯的邊數（每個環算作兩條邊）稱為的度(degree)，記作。若是奇數，稱是奇頂點(odd point)；是偶數，稱是偶頂點(even point)。關于頂點的度，我們有如下結果：(i) (ii) 任意一個圖的奇頂點的個數是偶數。 圖與網絡的數據結構網絡優化研究的是網絡上的各種優化模型與算法為了在計算機上實現網絡優化的算法，首先我們必須有一種方法（即數據結構）在計算機上來描述圖與網絡。一般來說，算法的好壞與網絡的具體表示方法，以及中間結果的操作方案是有關系的。這里我們介

12、紹計算機上用來描述圖與網絡的5種常用表示方法：鄰接矩陣表示法、關聯矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數據結構的討論中，我們首先假設是一個簡單有向圖，并假設中的頂點用自然數表示或編號，中的弧用自然數表示或編號。對于有多重邊或無向網絡的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。（i）鄰接矩陣表示法$鄰接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：是一個的矩陣，即 ， 也就是說，如果兩節點之間有一條弧，則鄰接矩陣中對應的元素為1；否則為0。可以看出，這種表示法非常簡單、直接。但是，在鄰接矩陣的

13、所有個元素中，只有個為非零元。如果網絡比較稀疏，這種表示法浪費大量的存儲空間，從而增加了在網絡中查找弧的時間。例7 對于右圖所示的圖，可以用鄰接矩陣表示為同樣，對于網絡中的權，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應的元素不再是1，而是相應的權而已。如果網絡中每條弧賦有多種權，則可以用多個矩陣表示這些權。（ii）關聯矩陣表示法關聯矩陣表示法是將圖以關聯矩陣（incidence matrix）的形式存儲在計算機中圖的關聯矩陣是如下定義的：是一個的矩陣，即 ，· 也就是說，在關聯矩陣中，每行對應于圖的一個節點，每列對應于圖的一條弧。如果一個節點是一條弧的起點，則關聯矩陣中對應

14、的元素為1；如果一個節點是一條弧的終點，則關聯矩陣中對應的元素為；如果一個節點與一條弧不關聯，則關聯矩陣中對應的元素為0。對于簡單圖，關聯矩陣每列只含有兩個非零元（一個，一個）。可以看出，這種表示法也非常簡單、直接。但是，在關聯矩陣的所有個元素中，只有個為非零元。如果網絡比較稀疏，這種表示法也會浪費大量的存儲空間。但由于關聯矩陣有許多特別重要的理論性質，因此它在網絡優化中是非常重要的概念。例8 對于例7所示的圖，如果關聯矩陣中每列對應弧的順序為(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關聯矩陣表示為同樣，對于網絡中的權，也可以通過對關聯矩

15、陣的擴展來表示。例如，如果網絡中每條弧有一個權，我們可以把關聯矩陣增加一行，把每一條弧所對應的權存儲在增加的行中。如果網絡中每條弧賦有多個權，我們可以把關聯矩陣增加相應的行數，把每一條弧所對應的權存儲在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arc list）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序對。弧表表示法直接列出所有弧的起點和終點，共需個存儲單元，因此當網絡比較稀疏時比較方便。此外，對于網絡圖中每條弧上的權，也要對應地用額外的存儲單元表示。例如，例7所示的圖，假設弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(

16、5,4)上的權分別為8，9，6，4，0，3，6和7，則弧表表示如下：起點11234455終點234(23534權89640367為了便于檢索，一般按照起點、終點的字典序順序存儲弧表，如上面的弧表就是按照這樣的順序存儲的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲在計算機中。所謂圖的鄰接表，也就是圖的所有節點的鄰接表的集合；而對每個節點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節點，用一個單向鏈表列出從該節點出發的所有弧，鏈表中每個單元對應于一條出弧。為了記錄弧上的權，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權等作為數據域

17、。圖的整個鄰接表可以用一個指針數組表示。例如，例7所示的圖，鄰接表表示為這是一個5維指針數組，每一維（上面表示法中的每一行）對應于一個節點的鄰接表，如第1行對應于第1個節點的鄰接表（即第1個節點的所有出弧）。每個指針單元的第1個數據域表示弧的另一個端點（弧的頭），后面的數據域表示對應弧上的權。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2），“8”表示對應弧(1,2)上的權為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應弧（1，3）上的權為9。又如，第5行說明節點5出發的弧有(5,3)、(5,4)，他們對應的權分別為6和7。對于有向圖，一般用表示節點的鄰接表，即

18、節點的所有出弧構成的集合或鏈表（實際上只需要列出弧的另一個端點，即弧的頭）。例如上面例子，等。這種記法我們在本書后面將會經常用到。（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節點，它也是記錄從該節點出發的所有弧，但它不是采用單向鏈表而是采用一個單一的數組表示。也就是說，在該數組中首先存放從節點1出發的所有弧，然后接著存放從節點2出發的所有孤，依此類推，最后存放從節點出發的所有孤。對每條弧，要依次存放其起點、終點、權的數值等有關信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節點出發的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節點出

19、發的所有弧，我們一般還用一個數組記錄每個節點出發的弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節點出發的所有弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權分別為8，9，6，4，0，3，6和7。此時該網絡圖可以用前向星形表示法表示如下： 節點對應的出弧的起始地址編號數組（記為）節點號1234；56起始地址134679記錄弧信息的數組弧編號12345678）起點11234455終點;23423534權8（9640367在數組中，

20、其元素個數比圖的節點數多1（即），且一定有，。對于節點，其對應的出弧存放在弧信息數組的位置區間為，如果，則節點沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數組（）記錄每個節點出發的弧的起始編號。前向星形表示法有利于快速檢索每個節點的所有出弧，但不能快速檢索每個節點的所有入弧。為了能夠快速檢索每個節點的所有入孤，可以采用反向星形（reverse star）表示法：首先存放進入節點1的所有孤，然后接著存放進入節點2的所有弧，依此類推，最后存放進入節點的所有孤。對每條弧，仍然依次存放其起點、終點

21、、權的數值等有關信息。同樣，為了能夠快速檢索從每個節點的所有入弧，我們一般還用一個數組記錄每個節點的入孤的起始地址（即弧的編號）。例如，例7所示的圖，可以用反向星形表示法表示為如下形式：節點對應的入弧的起始地址編號數組（記為）節點號123456】起始地址113689記錄弧信息的數組弧編號：12345678終點2$2333445起點31145524權489·06763如果既希望快速檢索每個節點的所有出弧，也希望快速檢索每個節點的所有入弧，則可以綜合采用前向和反向星形表示法。當然，將孤信息存放兩次是沒有必要的，可以只用一個數組（trace）記錄一條弧在兩種表示法中的對應關系即可。例如，可

22、以在采用前向星形表示法的基礎上，加上上面介紹的數組和如下的數組即可。這相當于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對應關系（記為）反向法中弧編號12345678正向法中弧編號41*257836對于網絡圖的表示法，我們作如下說明： 星形表示法和鄰接表表示法在實際算法實現中都是經常采用的。星形表示法的優點是占用的存儲空間較少，并且對那些不提供指針類型的語言（如 FORTRAN語言等）也容易實現。鄰接表表示法對那些提供指針類型的語言（如C語言等）是方便的，且增加或刪除一條弧所需的計算工作量很少，而這一操作在星形表示法中所需的計算工作量較大（需要花費的計算時間）。有關“計算時間”的觀念是

23、網絡優化中需要考慮的一個關鍵因素。 當網絡不是簡單圖，而是具有平行弧（即多重弧）時，顯然此時鄰接矩陣表示法是不能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。, 上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計算機中只存儲鄰接矩陣的一半信息（如上三角部分），因為此時鄰接矩陣是對稱矩陣。無向圖的關聯矩陣只含有元素0和，而不含有，因為此時不區分邊的起點和終點。又如，在鄰接表和星形表示法中，每條邊會被存儲兩次，而且反向星形表示顯然是沒有必要的，等等。 軌與連通，其中，與關聯，稱是圖的一條道路(walk)，為路長，頂點和

24、分別稱為的起點和終點，而稱為它的內部頂點。若道路的邊互不相同，則稱為跡(trail)。若道路的頂點互不相同，則稱為軌(path)。稱一條道路是閉的，如果它有正的長且起點和終點相同。起點和終點重合的軌叫做圈(cycle)。若圖的兩個頂點間存在道路，則稱和連通(connected)。間的最短軌的長叫做間的距離。記作。若圖的任二頂點均連通，則稱是連通圖。顯然有：(i) 圖是一條軌的充要條件是是連通的，且有兩個一度的頂點，其余頂點的度為2；(ii) 圖是一個圈的充要條件是是各頂點的度均為2的連通圖。"§3 應用最短路問題 兩個指定頂點之間的最短路徑問題如下：給出了一個連接若干個城鎮

25、的鐵路網絡，在這個網絡的兩個指定城鎮間，找一條最短鐵路線。以各城鎮為圖的頂點，兩城鎮間的直通鐵路為圖相應兩頂點間的邊，得圖。對的每一邊，賦以一個實數直通鐵路的長度，稱為的權，得到賦權圖。的子圖的權是指子圖的各邊的權和。問題就是求賦權圖中指定的兩個頂點間的具最小權的軌。這條軌叫做間的最短路，它的權叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠為順序，依次求得到的各頂點的最短路和距離，直至（或直至的所有頂點），算法結束。為避免重復并保留每一步的計算信息，采用了標號算法。下面是該算法。(i) 令，對，令，。(ii) 對每個（），用代替。計算

26、，把達到這個最小值的一個頂點記為，令。(iii). 若，停止；若，用代替，轉(ii)。%算法結束時，從到各頂點的距離由的最后一次的標號給出。在進入之前的標號叫T標號，進入時的標號叫P標號。算法就是不斷修改各項點的T標號，直至獲得P標號。若在算法運行過程中，將每一頂點獲得P標號所由來的邊在圖上標明，則算法結束時，至各項點的最短路也在圖上標示出來了。例9 某公司在六個城市中有分公司，從到的直接航程票價記在下述矩陣的位置上。（表示無直接航路），請幫助該公司設計一張城市到其它城市間的票價最便宜的路線圖。用矩陣（為頂點個數）存放各邊權的鄰接矩陣，行向量、分別用來存放標號信息、標號頂點順序、標號頂點索引、

27、最短通路的值。其中分量； 存放始點到第點最短通路中第頂點前一頂點的序號； 存放由始點到第點最短通路的值。求第一個城市到其它城市的最短路徑的Matlab程序如下：clear;clc;"M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a'pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones

28、(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;（while sum(pb)<length(a) tb=find(pb=0); d(tb)=min(d(tb),d(temp)+a(temp,tb); tmpb=find(d(tb)=min(d(tb); temp=tb(tmpb(1); pb(temp)=1; index1=index1,temp; index=index1(find(d(index1)=d(temp)-a(temp,index1); if length(index)>=2 index=index(1);) end index2

29、(temp)=index;endd, index1, index2 每對頂點之間的最短路徑計算賦權圖中各對頂點之間最短路徑，顯然可以調用Dijkstra算法。具體方法是：每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復執行次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。這種算法的時間復雜度為。第二種解決這一問題的方法是由Floyd R W提出的算法，稱之為Floyd算法。假設圖權的鄰接矩陣為，來存放各邊長度，其中：- ； 之間沒有邊，在程序中以各邊都不可能達到的充分大的數代替； 是之間邊的長度，。對于無向圖，是對稱矩陣，。Floyd算法的基本思想是

30、：遞推產生一個矩陣序列，其中表示從頂點到頂點的路徑上所經過的頂點序號不大于的最短路徑長度。計算時用迭代公式：是迭代次數，。最后，當時，即是各頂點之間的最短通路值。例10 用Floyd算法求解例1。矩陣path用來存放每對頂點之間最短路徑上所經過的頂點的序號。Floyd算法的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zero

31、s(1,6);<b=a+a'path=zeros(length(b);for k=1:6 for i=1:6 for j=1:6 if b(i,j)>b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j); path(i,j)=k; end end endendb, path§4 樹 基本概念連通的無圈圖叫做樹，記之為。若圖滿足，則稱是的生成樹。圖連通的充分必要條件為有生成樹。一個連通圖的生成樹的個數很多，用表示的生成樹的個數，則有公式公式 (Caylay)。公式 。其中表示從上刪除邊，表示把的長度收縮為零得到的圖。樹有下面常用的五個充要條件。；定理

32、1 （i）是樹當且僅當中任二頂點之間有且僅有一條軌道。（ii）是樹當且僅當無圈，且。（iii）是樹當且僅當連通，且。（iv）是樹當且僅當連通，且，不連通。（v）是樹當且僅當無圈，恰有一個圈。 應用連線問題欲修筑連接個城市的鐵路，已知城與城之間的鐵路造價為，設計一個線路圖，使總造價最低。連線問題的數學模型是在連通賦權圖上求權最小的生成樹。賦權圖的具有最小權的生成樹叫做最小生成樹。下面介紹構造最小生成樹的兩種常用算法。4.2.1 prim算法構造最小生成樹【設置兩個集合和,其中用于存放的最小生成樹中的頂點，集合存放的最小生成樹中的邊。令集合的初值為（假設構造最小生成樹時，從頂點出發），集合的初值為

33、。prim算法的思想是，從所有，的邊中，選取具有最小權值的邊，將頂點加入集合中，將邊加入集合中，如此不斷重復，直到時，最小生成樹構造完畢，這時集合中包含了最小生成樹的所有邊。prim算法如下：（i），；（ii）while end例11 用prim算法求右圖的最小生成樹。·我們用的第一、二、三行分別表示生成樹邊的起點、終點、權集合。Matlab程序如下：clc;clear;M=1000;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=7

34、0; a=a;zeros(2,7);a=a+a'a(find(a=0)=M;)result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); jb,kb=find(a(p,tb)=d); j=p(jb(1);k=tb(kb(1); result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult4.2.1 !4.2.2 Kruskal算法構造最小生成樹科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法如

35、下:(i)選，使得。(ii)若已選好，則從中選取，使得 中無圈，且 。(iii)直到選得為止。例12 用Kruskal算法構造例3的最小生成樹。我們用存放各邊端點的信息，當選中某一邊之后，就將此邊對應的頂點序號中較大序號改記為此邊的另一序號，同時把后面邊中所有序號為的改記為。此方法的幾何意義是：將序號的這個頂點收縮到頂點，頂點不復存在。后面繼續尋查時，發現某邊的兩個頂點序號相同時，認為已被收縮掉，失去了被選取的資格。;Matlab程序如下：clc;clear;M=1000;a(1,2)=50; a(1,3)=60;a(2,4)=65; a(2,5)=40;a(3,4)=52;a(3,7)=45

36、;a(4,5)=50; a(4,6)=30;a(4,7)=42;a(5,6)=70; i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i'j'b'index=data(1:2,:);loop=max(size(a)-1;result=;while length(result)<loop temp=min(data(3,:); flag=find(data(3,:)=temp); flag=flag(1); v1=data(1,flag);v2=data(2,flag); if index(1,flag)=i

37、ndex(2,flag) result=result,data(:,flag); end if v1>v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=;endresult§5 匹配問題定義 若，與無公共端點（），則稱為圖的一個對集；中的一條邊的兩個端點叫做在對集中相配；中的端點稱為被許配；中每個頂點皆被許配時，稱為完美對集；中已無使的對集，則稱為最大對集；若中有一軌，其邊交替地在對集內外出現，則稱此軌為的交錯軌，交錯軌的起止頂點都未被許配時，此交

38、錯軌稱為可增廣軌。若把可增廣軌上在外的邊納入對集，把內的邊從對集中刪除，則被許配的頂點數增加2，對集中的“對兒”增加一個。1957年，貝爾熱(Berge)得到最大對集的充要條件：定理2 是圖中的最大對集當且僅當中無可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3 為二分圖，與是頂點集的劃分，中存在把中頂點皆許配的對集的充要條件是，則，其中是中頂點的鄰集。由上述定理可以得出：推論1：若是（正則2分圖，則有完美對集。！所謂正則圖，即每頂點皆度的圖。由此推論得出下面的婚配定理：定理4 每個姑娘都結識位小伙子，每個小伙子都結識位姑娘，則每位姑娘都能和她認識的一個小伙子結婚，并且每位小伙

39、子也能和他認識的一個姑娘結婚。人員分派問題等實際問題可以化成對集來解決。人員分派問題：工作人員去做件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作如果不能，最多幾人可以有適合的工作這個問題的數學模型是：是二分圖，頂點集劃分為，當且僅當適合做工作時，求中的最大對集。解決這個問題可以利用1965年埃德門茲(Edmonds)提出的匈牙利算法。匈牙利算法：（i）從中任意取定一個初始對集。（ii）若把中的頂點皆許配，停止，即完美對集；否則取中未被許配的一頂點，記，。%（iii）若，停止，無完美對集；否則取。（iv）若是被許配的，設，轉（iii）；否則，取可增廣軌，令，轉（ii）。把以上算法

40、稍加修改就能夠用來求二分圖的最大對集。最優分派問題：在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數學模型是：在人員分派問題的模型中，圖的每邊加了權，表示干工作的效益，求加權圖上的權最大的完美對集。解決這個問題可以用庫恩曼克萊斯（Kuhn-Munkres）算法。為此，我們要引入可行頂點標號與相等子圖的概念。定義 若映射，滿足， ，則稱是二分圖的可行頂點標號。令，|稱以為邊集的的生成子圖為相等子圖，記作。可行頂點標號是存在的。例如 。定理5 的完美對集即為的權最大的完美對集。Kuhn-Munkres算法（i）選定初始可行頂點標

41、號，確定，在中選取一個對集。（ii）若中頂點皆被許配，停止，即的權最大的完美對集；否則，取中未被許配的頂點，令， 。(iii)若，轉（iv）；若，取 ，； ， ，。（iv）選中一頂點，若已被許配，且，則，轉（iii）；否則，取中一個可增廣軌，令，轉（ii）。其中是中的相鄰頂點集。§6 Euler圖和Hamilton圖 基本概念定義 經過的每條邊的跡叫做的Euler跡；閉的Euler跡叫做Euler回路或回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點出發每邊恰通過一次能回到出發點的那種圖，即不重復地行遍所有的邊再回到出發點。定理7 （i）是Euler圖的

42、充分必要條件是連通且每頂點皆偶次。（ii）是Euler圖的充分必要條件是連通且，是圈，。（iii）中有Euler跡的充要條件是連通且至多有兩個奇次點。定義 包含的每個頂點的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點出發每頂點恰通過一次能回到出發點的那種圖，即不重復地行遍所有的頂點再回到出發點。 Euler回路的Fleury算法1921年，Fleury給出下面的求Euler回路的算法。Fleury算法：1o. ，令。2o. 假設跡已經選定，那么按下述方法從中選取邊：

43、（i）和相關聯；（ii）除非沒有別的邊可選擇，否則不是的割邊(cut edge)。(所謂割邊是一條刪除后使連通圖不再連通的邊)。3o. 當第2步不能再執行時，算法停止。 應用 郵遞員問題中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當然他必須經過他負責投遞的每條街道至少一次，為他設計一條投遞路線，使得他行程最短。上述中國郵遞員問題的數學模型是：在一個賦權連通圖上求一個含所有邊的回路，且使此回路的權最小。顯然，若此連通賦權圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。-對于非Euler圖，1973年，Edmonds和Johnson給出下面的解法：設是連通

44、賦權圖。（i）求。（ii）對每對頂點，求（是與的距離，可用Floyd算法求得）。（iii）構造完全賦權圖，以為頂點集，以為邊的權。（iv）求中權之和最小的完美對集。（v）求中邊的端點之間的在中的最短軌。（vi）在（v）中求得的每條最短軌上每條邊添加一條等權的所謂“倍邊”（即共端點共權的邊）。（vii）在（vi）中得的圖上求Euler回路即為中國郵遞員問題的解。多郵遞員問題：【郵局有位投遞員，同時投遞信件，全城街道都要投遞，完成任務返回郵局，如何分配投遞路線，使得完成投遞任務的時間最早我們把這一問題記成kPP。kPP的數學模型如下：是連通圖，求的回路，使得（i），（ii），（iii） 旅行商（T

45、SP）問題一名推銷員準備前往若干城市推銷產品，然后回到他的出發地。如何為他設計一條最短的旅行路線（從駐地出發，經過每個城市恰好一次，最后返回駐地）這個問題稱為旅行商問題。用圖論的術語說，就是在一個賦權完全圖中，找出一個有最小權的Hamilton圈。稱這種圈為最優圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優）的解。一個可行的辦法是首先求一個Hamilton圈，然后適當修改以得到具有較小權的另一個Hamilton圈。修改的方法叫做改良圈算法。設初始圈。（i）對于，構造新的Hamilton圈:" ,它是由中刪去邊和，添加邊

46、和而得到的。若，則以代替，叫做的改良圈。（ii）轉（i），直至無法改進，停止。用改良圈算法得到的結果幾乎可以肯定不是最優的。為了得到更高的精確度，可以選擇不同的初始圈，重復進行幾次算法，以求得較精確的結果。這個算法的優劣程度有時能用Kruskal算法加以說明。假設是中的最優圈。則對于任何頂點，是在中的Hamilton軌，因而也是的生成樹。由此推知：若是中的最優樹，同時和是和關聯的兩條邊，并使得盡可能小，則將是的一個下界。這里介紹的方法已被進一步發展。圈的修改過程一次替換三條邊比一次僅替換兩條邊更為有效；然而，有點奇怪的是，進一步推廣這一想法，就不利了。例13 從北京（Pe）乘飛機到東京(T)、

47、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應如何安排旅游線，使旅程最短各城市之間的航線距離如下表：LM'NPaPeTL56352151"60M5621577870N35,21366868Pa215736&5161Pe5178685113T!6070686113解：編寫程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;$a(3,4)=36;a(3,5)=68;a(3,

48、6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a'c1=5 1:4 6;L=length(c1);flag=1;while flag>0 flag=0;】 for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;)for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);e

49、ndcircle=c1;sum=sum1;c1=5 6 1:4;%改變初始圈，該算法的最后一個頂點不動flag=1;while flag>0 flag=0; for m=1:L-3； for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<. a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1<sum sum=sum1;

50、circle=c1;endcircle,sum§7 最大流問題 最大流問題的數學描述 網絡中的流 定義 在以為節點集，為弧集的有向圖上定義如下的權函數：（i）為孤上的權函數，弧對應的權記為，稱為孤的容量下界（lower bound）；（ii）為弧上的權函數，弧對應的權記為，稱為孤的容量上界，或直接稱為容量（capacity）；（iii）為頂點上的權函數，節點對應的權記為，稱為頂點的供需量（supplydemand）；此時所構成的網絡稱為流網絡，可以記為。 由于我們只討論為有限集合的情況，所以對于弧上的權函數和頂點上的權函數，可以直接用所有孤上對應的權組成的有限維向量表示，因此有時直接

51、稱為權向量，或簡稱權。由于給定有向圖后，我們總是可以在它的弧集合和頂點集合上定義各種權函數，所以流網絡一般也直接簡稱為網絡。 在流網絡中，弧的容量下界和容量上界表示的物理意義分別是：通過該弧發送某種“物質”時，必須發送的最小數量為，而發送的最大數量為。頂點對應的供需量則表示該頂點從網絡外部獲得的“物質”數量（時），或從該頂點發送到網絡外部的“物質”數量（時）。下面我們給出嚴格定義。 定義 對于流網絡，其上的一個流（flow）是指從的弧集到的一個函數，即對每條弧賦予一個實數（稱為弧的流量）。如果流滿足 （1）， （2）則稱為可行流（feasible flow）。至少存在一個可行流的流網絡稱為可行

52、網絡（feasible network）約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。 可見，當時，表示有個單位的流量從該項點流出，因此頂點稱為供應點（supply node）或源（source），有時也形象地稱為起始點或發點等；當時，表示有個單位的流量流入該點（或說被該頂點吸收），因此頂點稱為需求點（demand node）或匯（sink），有時也形象地稱為終止點或收點等；當時，頂點稱為轉運點（transshipment node）或平衡點、中間點等。此外，根據（1）可知，對于可行網絡，必有 （3）也就是說，所有節點上的供需量之和為0是網絡中存在可行流的必要條件。

53、一般來說，我們總是可以把的流網絡轉化為的流網絡進行研究。所以，除非特別說明，以后我們總是假設（即所有孤的容量下界），并將時的流網絡簡記為。此時，相應的容量約束（2）為 。定義 在流網絡中，對于流，如果 ，則稱為零流，否則為非零流。如果某條弧上的流量等于其容量（），則稱該弧為飽和弧（saturated arc）；如果某條弧上的流量小于其容量（），則稱該弧為非飽和弧；如果某條弧上的流量為 0（），則稱該弧為空弧（void arc）。 最大流問題考慮如下流網絡：節點為網絡中唯一的源點，為唯一的匯點，而其它節點為轉運點。如果網絡中存在可行流，此時稱流的流量（或流值，flow value）為（根據（3），它自然也等于），通常記為或，即 。對這種單源單匯的網絡，如果我們并不給定和（即流量不給定），則網絡一般記為。最大流問題（maximum flow problem）就是在中找到流值最大的可行流（即最大流）。我們將會看到，最大流問題的許多算法也可以用來求解流量給