第六章 圖與網絡模型

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

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

3、“線”的“圖”。問題成為從任一點出發(fā)一筆畫出七條線再回到起點。歐拉考察了一般一筆畫的結構特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數線相關聯，將這個判定法則應用于七橋問題，得到了“不可能走通”的結果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。圖與網絡所研究的問題涉及經濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術、通訊與網絡技術等諸多領域。下面將要討論的最短路問題、最小費用問題和匹配問題等都是圖與網絡的基本問題。我們首先通過一些例子來了解網絡優(yōu)化問題。例1 最短路問題（SPPshortest path problem）一名貨柜車司機奉命在最短的時間內將一車貨物從

4、甲地運往乙地。從甲地到乙地的公路網縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路。例2 公路連接問題某一地區(qū)有若干個主要城市，現準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經高速公路直接或間接到達另一個城市。假定已經知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最?。坷? 指派問題（assignment problem）一家公司經理準備安排名員工去完成項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。

5、如何分配工作方案可以使總回報最大？例4 中國郵遞員問題（CPPchinese postman problem）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經過投遞區(qū)內每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5 旅行商問題（TSPtraveling salesman problem）一名推銷員準備前往若干城市推銷產品。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。例6 運輸問題（trans

6、portation problem）某種原材料有個產地，現在需要將原材料從產地運往個使用這些原材料的工廠。假定個產地的產量和家工廠的需要量已知，單位產品從任一產地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？上述問題有兩個共同的特點：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數學上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達，數學上把這種與圖相關的結構稱為網絡（network）。與圖和網絡相關的最優(yōu)化問題就是網絡最優(yōu)化或稱網絡優(yōu)化 （netwok optimization）問題。所以上面

7、例子中介紹的問題都是網絡優(yōu)化問題。由于多數網絡優(yōu)化問題是以網絡上的流（flow）為研究的對象，因此網絡優(yōu)化又常常被稱為網絡流（network flows）或網絡流規(guī)劃等。2.圖與網絡的一些基本概念。2.1 無向圖一個無向圖(undirected graph)是由一個非空有限集合和中某些元素的無序對集合構成的二元組，記為。其中稱為圖的頂點集（vertex set）或節(jié)點集（node set）， 中的每一個元素稱為該圖的一個頂點（vertex）或節(jié)點（node）；稱為圖的邊集（edge set），中的每一個元素(即中某兩個元素的無序對) 記為或 ，被稱為該圖的一條從到的邊（edge）。當

8、邊時，稱為邊的端點，并稱與相鄰（adjacent）；邊稱為與頂點關聯（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖中相鄰。邊上賦權的無向圖稱為賦權無向圖或無向網絡（undirected network）。我們對圖和網絡不作嚴格區(qū)分，因為任何圖總是可以賦權的。一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖的頂點數用符號或表示，邊數用或表示。當討論的圖只有一個時，總是用來表示這個圖。從而在圖論符號中我們常略去字母，例如，分別用和代替和。端點重合為一點的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simple graph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點。2.2 有向

9、圖定義 一個有向圖（directed graph或 digraph）是由一個非空有限集合和中某些元素的有序對集合構成的二元組，記為。其中稱為圖的頂點集或節(jié)點集， 中的每一個元素稱為該圖的一個頂點或節(jié)點；稱為圖的弧集（arc set），中的每一個元素(即中某兩個元素的有序對) 記為或，被稱為該圖的一條從到的?。╝rc）。當弧時，稱為的尾（tail），為的頭（head），并稱弧為的出?。╫utgoing arc），為的入弧（incoming arc）。對應于每個有向圖，可以在相同頂點集上作一個圖，使得對于的每條弧，有一條有相同端點的邊與之相對應。這個圖稱為的基礎圖。反之，給定任意圖，對于

10、它的每個邊，給其端點指定一個順序，從而確定一條弧，由此得到一個有向圖，這樣的有向圖稱為的一個定向圖。以下若未指明“有向圖”三字，“圖”字皆指無向圖。2.3 完全圖、二分圖每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(complete graph)。個頂點的完全圖記為。若，（這里表示集合中的元素個數），中無相鄰頂點對，中亦然，則稱為二分圖(bipartite graph)；特別地，若，則，則稱為完全二分圖，記成。 2.4 子圖圖叫做圖的子圖（subgraph），記作，如果，。若是的子圖，則稱為的母圖。的支撐子圖（spanning subgraph，又成生成子圖）是指滿足的子圖。2.5 頂點的

11、度設，中與關聯的邊數（每個環(huán)算作兩條邊）稱為的度(degree)，記作。若是奇數，稱是奇頂點(odd point)；是偶數，稱是偶頂點(even point)。關于頂點的度，我們有如下結果：(i) (ii) 任意一個圖的奇頂點的個數是偶數。2.6 圖與網絡的數據結構網絡優(yōu)化研究的是網絡上的各種優(yōu)化模型與算法為了在計算機上實現網絡優(yōu)化的算法，首先我們必須有一種方法（即數據結構）在計算機上來描述圖與網絡。一般來說，算法的好壞與網絡的具體表示方法，以及中間結果的操作方案是有關系的。這里我們介紹計算機上用來描述圖與網絡的5種常用表示方法：鄰接矩陣表示法、關聯矩陣表示法、弧表表示法、鄰接表表示法和星形表

12、示法。在下面數據結構的討論中，我們首先假設是一個簡單有向圖，并假設中的頂點用自然數表示或編號，中的弧用自然數表示或編號。對于有多重邊或無向網絡的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：是一個的矩陣，即 ， 也就是說，如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應的元素為1；否則為0?？梢钥闯?，這種表示法非常簡單、直接。但是，在鄰接矩陣的所有個元素中，只有個為非零元。如果網絡比較稀疏，這種表示法浪費大量的存儲空間，從而增加了在網絡中查找弧的時間。例

13、7 對于右圖所示的圖，可以用鄰接矩陣表示為同樣，對于網絡中的權，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應的元素不再是1，而是相應的權而已。如果網絡中每條弧賦有多種權，則可以用多個矩陣表示這些權。（ii）關聯矩陣表示法關聯矩陣表示法是將圖以關聯矩陣（incidence matrix）的形式存儲在計算機中圖的關聯矩陣是如下定義的：是一個的矩陣，即 ， 也就是說，在關聯矩陣中，每行對應于圖的一個節(jié)點，每列對應于圖的一條弧。如果一個節(jié)點是一條弧的起點，則關聯矩陣中對應的元素為1；如果一個節(jié)點是一條弧的終點，則關聯矩陣中對應的元素為；如果一個節(jié)點與一條弧不關聯，則關聯矩陣中對應的元素為0。對

14、于簡單圖，關聯矩陣每列只含有兩個非零元（一個，一個）?？梢钥闯?，這種表示法也非常簡單、直接。但是，在關聯矩陣的所有個元素中，只有個為非零元。如果網絡比較稀疏，這種表示法也會浪費大量的存儲空間。但由于關聯矩陣有許多特別重要的理論性質，因此它在網絡優(yōu)化中是非常重要的概念。例8 對于例7所示的圖，如果關聯矩陣中每列對應弧的順序為(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關聯矩陣表示為同樣，對于網絡中的權，也可以通過對關聯矩陣的擴展來表示。例如，如果網絡中每條弧有一個權，我們可以把關聯矩陣增加一行，把每一條弧所對應的權存儲在增加的行中。如果網絡中

15、每條弧賦有多個權，我們可以把關聯矩陣增加相應的行數，把每一條弧所對應的權存儲在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arc list）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序對?；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c和終點，共需個存儲單元，因此當網絡比較稀疏時比較方便。此外，對于網絡圖中每條弧上的權，也要對應地用額外的存儲單元表示。例如，例7所示的圖，假設弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的權分別為8，9，6，4，0，3，6和7，則弧表表示如下：起點11234455終點23423534權8964036

16、7為了便于檢索，一般按照起點、終點的字典序順序存儲弧表，如上面的弧表就是按照這樣的順序存儲的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacency lists）的形式存儲在計算機中。所謂圖的鄰接表，也就是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點，用一個單向鏈表列出從該節(jié)點出發(fā)的所有弧，鏈表中每個單元對應于一條出弧。為了記錄弧上的權，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權等作為數據域。圖的整個鄰接表可以用一個指針數組表示。例如，例7所示的圖，鄰接表表示為這是一個5維指針數組，每一維（上面表示法中的每一行）對

17、應于一個節(jié)點的鄰接表，如第1行對應于第1個節(jié)點的鄰接表（即第1個節(jié)點的所有出弧）。每個指針單元的第1個數據域表示弧的另一個端點（弧的頭），后面的數據域表示對應弧上的權。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2），“8”表示對應弧(1,2)上的權為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應弧（1，3）上的權為9。又如，第5行說明節(jié)點5出發(fā)的弧有(5,3)、(5,4)，他們對應的權分別為6和7。對于有向圖，一般用表示節(jié)點的鄰接表，即節(jié)點的所有出弧構成的集合或鏈表（實際上只需要列出弧的另一個端點，即弧的頭）。例如上面例子，等。這種記法我們在本書后面將會經常用

18、到。（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點，它也是記錄從該節(jié)點出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數組表示。也就是說，在該數組中首先存放從節(jié)點1出發(fā)的所有弧，然后接著存放從節(jié)點2出發(fā)的所有孤，依此類推，最后存放從節(jié)點出發(fā)的所有孤。對每條弧，要依次存放其起點、終點、權的數值等有關信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節(jié)點出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節(jié)點出發(fā)的所有弧，我們一般還用一個數組記錄每個節(jié)點出發(fā)的弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有

19、弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設?。?,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權分別為8，9，6，4，0，3，6和7。此時該網絡圖可以用前向星形表示法表示如下： 節(jié)點對應的出弧的起始地址編號數組（記為）節(jié)點號123456起始地址134679記錄弧信息的數組弧編號12345678起點11234455終點23423534權89640367在數組中，其元素個數比圖的節(jié)點數多1（即），且一定有，。對于節(jié)點，其對應的出弧存放在弧信息數組的位置區(qū)間為，如果，則節(jié)點沒有出弧。這種表示法與弧

20、表表示法也非常相似，“記錄弧信息的數組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數組（）記錄每個節(jié)點出發(fā)的弧的起始編號。前向星形表示法有利于快速檢索每個節(jié)點的所有出弧，但不能快速檢索每個節(jié)點的所有入弧。為了能夠快速檢索每個節(jié)點的所有入孤，可以采用反向星形（reverse star）表示法：首先存放進入節(jié)點1的所有孤，然后接著存放進入節(jié)點2的所有弧，依此類推，最后存放進入節(jié)點的所有孤。對每條弧，仍然依次存放其起點、終點、權的數值等有關信息。同樣，為了能夠快速檢索從每個節(jié)點的所有入弧，我們一般還用一個數組記錄每個節(jié)點的入孤的起始地址（即弧的編號）。例如

21、，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點對應的入弧的起始地址編號數組（記為）節(jié)點號123456起始地址113689記錄弧信息的數組弧編號12345678終點22333445起點31145524權48906763如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點的所有入弧，則可以綜合采用前向和反向星形表示法。當然，將孤信息存放兩次是沒有必要的，可以只用一個數組（trace）記錄一條弧在兩種表示法中的對應關系即可。例如，可以在采用前向星形表示法的基礎上，加上上面介紹的數組和如下的數組即可。這相當于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對應關系（記為）反向法中弧編號12345678正向法中弧編號41257836對于網絡圖的表示法，我們作如下說明： 星形表示法和鄰接表表示法在實際算法實現中都