數(shù)學建模資料-圖與網(wǎng)絡模型及方法課件

圖與網(wǎng)絡模型及方法概論圖論起源于18世紀。第一篇圖論論文是瑞士數(shù)學家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。1847年，克?；舴驗榱私o出電網(wǎng)絡方程而引進了“樹”的概念。1857年，凱萊在計數(shù)烷的同分異構(gòu)物時，也發(fā)現(xiàn)了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術(shù)語，就是如何找出一個連通圖中的生成圈。近幾十年來，由于計算機技術(shù)和科學的飛速發(fā)展，大大地促進了圖論研究和應用，圖論的理論和方法已經(jīng)滲透到物理、化學、通訊科學、建筑學、生物遺傳學、心理學、經(jīng)濟學、社會學等學科中。圖得概念：圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學模型，借助于圖論的概念、理論和方法，可以對該模型求解。圖與網(wǎng)絡模型及方法概論圖論起源于18世紀。第一篇圖論論文是1例子：哥尼斯堡七橋問題：在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點可以通過試驗去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個問題，采用了建立數(shù)學模型的方法。他將每一塊陸地用一個點來代替，將每一座橋用連接相應兩點的一條線來代替，從而得到一個有四個“點”，七條“線”的“圖”。問題成為從任一點出發(fā)一筆畫出七條線再回到起點。歐拉考察了一般一筆畫的結(jié)構(gòu)特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數(shù)線相關(guān)聯(lián)，將這個判定法則應用于七橋問題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。例子：哥尼斯堡七橋問題：在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩2圖論的應用：圖與網(wǎng)絡是運籌學（OperationsResearch）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術(shù)、通訊與網(wǎng)絡技術(shù)等諸多領(lǐng)域。圖與網(wǎng)絡優(yōu)化的一些基本問題：例1最短路問題（SPP－shortestpathproblem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路。例2公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最??？例3指派問題（assignmentproblem）一家公司經(jīng)理準備安排名員工去完成項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大？圖論的應用：圖與網(wǎng)絡是運籌學（OperationsRese3例4中國郵遞員問題（CPP－chinesepostmanproblem）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。例6運輸問題（transportationproblem）某種原材料有個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往個使用這些原材料的工廠。假定每個產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？上述問題有兩個共同的特點：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達，數(shù)學上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡（network）。與圖和網(wǎng)絡相關(guān)的最優(yōu)化問題就是網(wǎng)絡最優(yōu)化或稱網(wǎng)絡優(yōu)化（netwokoptimization）問題。所以上面例子中介紹的問題都是網(wǎng)絡優(yōu)化問題。由于多數(shù)網(wǎng)絡優(yōu)化問題是以網(wǎng)絡上的流（flow）為研究的對象，因此網(wǎng)絡優(yōu)化又常常被稱為網(wǎng)絡流（networkflows）或網(wǎng)絡流規(guī)劃等例4中國郵遞員問題（CPP－chinesepostma4

圖與網(wǎng)絡的基本概念

無向圖：一個無向圖(undirectedgraph)G是由一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集（vertexset）或節(jié)點集（nodeset），中的每一個元素稱為該圖的一個頂點（vertex）或節(jié)點（node）；稱為圖的邊集（edgeset），中的每一個元素(即中某兩個元素的無序?qū)?

記為或，被稱為該圖的一條從到的邊（edge）。當邊時，稱為邊的端點，并稱與相鄰（adjacent）；邊稱為與頂點關(guān)聯(lián)（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖中相鄰。邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡（undirectednetwork）。我們對圖和網(wǎng)絡不作嚴格區(qū)分，因為任何圖總是可以賦權(quán)的。一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖的頂點數(shù)用符號或表示，邊數(shù)用或表示。端點重合為一點的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點。圖與網(wǎng)絡的基本概念無向圖：一個無向圖(undirecte5有向圖：當圖的邊集中的邊是頂點的有序?qū)r，這時候就稱為這些邊是有方向的。從而原來的無向圖也就成為這兒的有向圖。頂點的度：一個頂點的度是與這個頂點相關(guān)聯(lián)的邊的數(shù)目。在有向圖的情形下，一個頂點的度還分為頂點入度和頂點出度兩種情形。頂點的入度是與這個頂點相關(guān)聯(lián)的并且指向這個頂點的邊的數(shù)目。頂點的出度是與這個頂點相關(guān)聯(lián)的并且方向遠離這個頂點的邊的數(shù)目。圖與網(wǎng)絡的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡優(yōu)化研究的是網(wǎng)絡上的各種優(yōu)化模型與算法．為了在計算機上實現(xiàn)網(wǎng)絡優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計算機上來描述圖與網(wǎng)絡。一般來說，算法的好壞與網(wǎng)絡的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計算機上用來描述圖與網(wǎng)絡的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設是一個簡單有向圖，，并假設中的頂點用自然數(shù)表示或編號，中的弧用自然數(shù)表示或編號。對于有多重邊或無向網(wǎng)絡的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。有向圖：當圖的邊集中的邊是頂點的有序?qū)r，這時候就稱為這些邊6（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：是一個的矩陣，即也就是說，如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應的元素為1；否則為0?？梢钥闯?，這種表示法非常簡單、直接。但是，在鄰接矩陣的所有個元素中，只有個為非零元。如果網(wǎng)絡比較稀疏，這種表示法浪費大量的存儲空間，從而增加了在網(wǎng)絡中查找弧的時間。例7對于上圖所示的圖，可以用鄰接矩陣表示為（i）鄰接矩陣表示法也就是說，如果兩節(jié)點之間有一條弧，則鄰接7，

同樣，對于網(wǎng)絡中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應的元素不再是1，而是相應的權(quán)而已。如果網(wǎng)絡中每條弧賦有多種權(quán)，則可以用多個矩陣表示這些權(quán)。（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲在計算機中．圖的關(guān)聯(lián)矩陣是如下定義的：是一個的矩陣，即也就是說，在關(guān)聯(lián)矩陣中，每行對應于圖的一個節(jié)點，每列對應于圖的一條弧。如果一個節(jié)點是一條弧的起點，則關(guān)上聯(lián)矩陣中對應的元素為1；如果一個節(jié)點是一條弧的終點，則關(guān)聯(lián)矩陣中對應的元素為-1；如果一個節(jié)點與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應的元素為0。對于簡單圖，關(guān)聯(lián)矩陣每列只含有兩個非零元（一個+1，一個-1）?？梢钥闯?，這種表示法也非常簡單、直接。但是，在關(guān)聯(lián)矩陣的所有nm個元素中，只有2m個為非零元。如果網(wǎng)絡比較稀疏，這種表示法也會浪費大量的存儲空間。但由于關(guān)聯(lián)矩陣有許多特別重要的理論性質(zhì)，因此它在網(wǎng)絡優(yōu)化中是非常重要的概念。，同樣，對于網(wǎng)絡中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是8例8對于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對應弧的順序為(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為:同樣，對于網(wǎng)絡中的權(quán)，也可以通過對關(guān)聯(lián)矩陣的擴展來表示。例如，如果網(wǎng)絡中每條弧有一個權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對應的權(quán)存儲在增加的行中。如果網(wǎng)絡中每條弧賦有多個權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應的行數(shù)，把每一條弧所對應的權(quán)存儲在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)?。弧表表示法直接列出所有弧的起點和終點，共需2m個存儲單元，因此當網(wǎng)絡比較稀疏時比較方便。此外，對于網(wǎng)絡圖中每條弧上的權(quán)，也要對應地用額外的存儲單元表示。例如，例7所示的圖，假設弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的權(quán)分別為8，9，6，4，0，3，6和7，則弧表表示如下：例8對于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對應弧的順序為(9起點11234455終點23423534權(quán)89640367為了便于檢索，一般按照起點、終點的字典序順序存儲弧表，如上面的弧表就是按照這樣的順序存儲的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲在計算機中。所謂圖的鄰接表，也就是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點，用一個單向鏈表列出從該節(jié)點出發(fā)的所有弧，鏈表中每個單元對應于一條出弧。為了記錄弧上的權(quán)，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。例如，例7所示的圖，鄰接表表示為起點11234455終點23423534權(quán)89640367為10這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應于一個節(jié)點的鄰接表，如第1行對應于第1個節(jié)點的鄰接表（即第1個節(jié)點的所有出?。?。每個指針單元的第1個數(shù)據(jù)域表示弧的另一個端點（弧的頭），后面的數(shù)據(jù)域表示對應弧上的權(quán)。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2）），“8”表示對應弧(1,2)上的權(quán)為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應?。?，3）上的權(quán)為9。又如，第5行說明節(jié)點5出發(fā)的弧有(5,3)、(5,4)，他們對應的權(quán)分別為6和7。對于有向圖，一般用表示節(jié)點的鄰接表，即節(jié)點的所有出弧構(gòu)成的集合或鏈表（實際上只需要列出弧的另一個端點，即弧的頭）。例如上面例子，，等。這種記法我們在本書后面將會經(jīng)常用到。，

（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點，它也是記錄從該節(jié)點出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示。也就是說，在該數(shù)組中首先存放從節(jié)點1出發(fā)的所有弧，然后接著存放從節(jié)點2出發(fā)的所有孤，依此類推，最后存放從節(jié)點出發(fā)的所有孤。對每條弧，要依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節(jié)點出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節(jié)點出發(fā)的所有弧，我們一般還用一個數(shù)組記錄每個節(jié)點出發(fā)的弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有弧，這種星形表示法稱為前向星形（forwardstar）表示法。這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應于一11例如，在例7所示的圖中，仍然假設弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權(quán)分別為8，9，6，4，0，3，6和7。此時該網(wǎng)絡圖可以用前向星形表示法表示如下：節(jié)點對應的出弧的起始地址編號數(shù)組（記為）節(jié)點號起始地址123456134679記錄弧信息的數(shù)組弧編號12345678起點11234455終點23423534權(quán)89640367在數(shù)組中，其元素個數(shù)比圖的節(jié)點數(shù)多1（即n+1），且一定有，。對于節(jié)點，其對應的出弧存放在弧信息數(shù)組的位置區(qū)間為，

例如，在例7所示的圖中，仍然假設?。?,2），（l,3），（12如果，則節(jié)點沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組（）記錄每個節(jié)點出發(fā)的弧的起始編號。前向星形表示法有利于快速檢索每個節(jié)點的所有出弧，但不能快速檢索每個節(jié)點的所有入弧。為了能夠快速檢索每個節(jié)點的所有入孤，可以采用反向星形（reversestar）表示法：首先存放進入節(jié)點1的所有孤，然后接著存放進入節(jié)點2的所有弧，依此類推，最后存放進入節(jié)點的所有孤。對每條弧，仍然依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個節(jié)點的所有入弧，我們一般還用一個數(shù)組記錄每個節(jié)點的入孤的起始地址（即弧的編號）。例如，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點對應的入弧的起始地址編號數(shù)組（記為）節(jié)點號123456起始地址113689記錄弧信息的數(shù)組弧編號12345678終點22333445起點31145524權(quán)48906763如果13如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點的所有入弧，則可以綜合采用前向和反向星形表示法。當然，將孤信息存放兩次是沒有必要的，可以只用一個數(shù)組（trace）記錄一條弧在兩種表示法中的對應關(guān)系即可。例如，可以在采用前向星形表示法的基礎上，加上上面介紹的數(shù)組和如下的數(shù)組即可。這相當于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對應關(guān)系（記為）反向法中弧編號正向法中弧編號1234567841257836對于網(wǎng)絡圖的表示法，我們作如下說明星形表示法和鄰接表表示法在實際算法實現(xiàn)中都是經(jīng)常采用的。星形表示法的優(yōu)點是占用的存儲空間較少，并且對那些不提供指針類型的語言（如FORTRAN語言等）也容易實現(xiàn)。鄰接表表示法對那些提供指針類型的語言（如C語言等）是方便的，且增加或刪除一條弧所需的計算工作量很少，而這一操作在星形表示法中所需的計算工作量較大（需要花費計算時間）。有關(guān)“計算時間”的觀念是網(wǎng)絡優(yōu)化中需要考慮的一個關(guān)鍵因素。當網(wǎng)絡不是簡單圖，而是具有平行?。炊嘀鼗。r，顯然此時鄰接矩陣表示法是不能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點14上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計算機中只存儲鄰接矩陣的一半信息（如上三角部分），因為此時鄰接矩陣是對稱矩陣。無向圖的關(guān)聯(lián)矩陣只含有元素0和+1，而不含有-1，因為此時不區(qū)分邊的起點和終點。又如，在鄰接表和星形表示法中，每條邊會被存儲兩次，而且反向星形表示顯然是沒有必要的，等等。軌與連通，其中，。其中與關(guān)聯(lián)。W稱為圖G的一條道路，k為路長。頂點稱為W的起點和終點。若道路W的邊互不相同，則W稱為跡(trail)。若道路W的頂點互不相同，則W稱為軌(path)。稱一條道路是閉的，如果它有正的長且起點和終點相同。起點和終點重合的軌叫做圈.若圖G的兩個頂點u,v間存在道路，則稱u和v連通(connected)。U,v間的最短軌的長叫做U,v間的距離。記作d(u,v)。若圖G的任二頂點均連通，則稱G是連通圖。上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖15應用兩個指定頂點之間的最短距離問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡，在這個網(wǎng)絡的兩個指定城鎮(zhèn)間，找一條最短鐵路線以各城鎮(zhèn)為圖G的頂點，兩城鎮(zhèn)間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數(shù)w(e)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠為順序，依次求得到的各頂點的最短路和距離，直至（或直至G的所有頂點），算法結(jié)束。為避免重復并保留每一步的計算信息，采用了標號算法.下面是該算法。應用兩個指定頂點之間的最短距離問題如下：給出了一個連接若干個16(i令，對，令，，。(ii)對每個（），用

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

存放始點到第點最短通路中第頂點前一頂點的序號；存放由始點到第點最短通路的值。求第一個城市到其它城市的最短路徑的Matlab程序如下：例9某公司在六個城市中有分公司18clear;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(1,length(a));d(1:length(a))=M;d(1)=0;temp=1;whilesum(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)));iflength(index)>=2index=index(1);endindex2(temp)=index;endd,index1,index2clear;19連通的無圈圖叫做樹，記之為。若圖滿足，，則稱是的生成樹。圖連通的充分必要條件為有生成樹。一個連通圖的生成樹的個數(shù)很多，用表示的生成樹的個數(shù)，則有公式其中表示從上刪除邊，表示把的長度收縮為零得到的圖。應用—連線問題:欲修筑連接個城市的鐵路，已知城與城之間的鐵路造價為，設計一個線路圖，使總造價最低。下面介紹構(gòu)造最小生成樹的兩種常用算法。prim算法構(gòu)造最小生成樹設置兩個集合和,其中用于存放的最小生成樹中的頂點，集合存放的最小生成樹中的邊。令集合的初值為（假設構(gòu)造最小生成樹時，從頂點出發(fā)），集合的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，

將頂點加入集合中，將邊加入集合中，如此不斷重復，直到時，最小生成樹構(gòu)造完畢，這時集合中包含了最小生成樹的所有邊。連通的無圈圖叫做樹，記之為。若圖滿足20例11用prim算法求右圖的最小生成樹。我們用的第一、二、三行分別表示生成樹邊的起點、終點、權(quán)集合。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)=70;a=[a;zeros(2,7)];a=a+a';a(find(a==0))=M;result=[];p=1;tb=2:length(a);whilelength(result)~=length(a)-1temp=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))=[];endresult例11用prim算法求右圖的最小生成樹。我們用的第一、二、21例12用Kruskal算法構(gòu)造例11的最小生成樹。我們用存放各邊端點的信息，當選中某一邊之后，就將此邊對應的頂點序號中較大序號改記為此邊的另一序號，同時把后面邊中所有序號為的改記為。此方法的幾何意義是：將序號的這個頂點收縮到頂點，頂點不復存在。后面繼續(xù)尋查時，發(fā)現(xiàn)某邊的兩個頂點序號相同時，認為已被收縮掉，失去了被選取的資格。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)=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=[];whilelength(result)<looptemp=min(data(3,:));flag=find(data(3,:)==temp);flag=flag(1);v1=data(1,flag);v2=data(2,flag);ifindex(1,flag)~=index(2,flag)result=[result,data(:,flag)];endifv1>v2index(find(index==v1))=v2;elseindex(find(index==v2))=v1;enddata(:,flag)=[];index(:,flag)=[];endresult例12用Kruskal算法構(gòu)造例11的最小生成樹。Matl22匹配問題定義若，，與無公共端點（），則稱為圖的一個對集；中的一條邊的兩個端點叫做在對集中相配；中的端點稱為被許配；中每個頂點皆被許配時，稱為完美對集；中已無使的對集，則稱為最大對集；若中有一軌，其邊交替地在對集內(nèi)外出現(xiàn)，則稱此軌為的交錯軌，交錯軌的起止頂點都未被許配時，此交錯軌稱為可增廣軌。若把可增廣軌上在外的邊納入對集，把內(nèi)的邊從對集中刪除，則被許配的頂點數(shù)增加2，對集中的“對兒”增加一個。1957年，貝爾熱(Berge)得到最大對集的充要條件：定理2是圖中的最大對集當且僅當中無可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3為二分圖，與是頂點集的劃分，中存在把中頂點皆許配的對集的充要條件是，，則，其中是中頂點的鄰集。匹配問題定義若，23由上述定理可以得出：推論1：若是（)正則2分圖，則有完美對集。應用人員分派問題：工作人員去做件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個問題的數(shù)學模型是：是二分圖，頂點集劃分為，，，當且僅當適合做工作時，，求中的最大對集解決這個問題可以利用1965年埃德門茲(Edmonds)提出的匈牙利算法。i）從中任意取定一個初始對集。（ii）若把中的頂點皆許配，停止，即完美對集；否則取中未被許配的一頂點，記，。（iii）若，停止，無完美對集；否則取。（iv）若是被許配的，設，，，轉(zhuǎn)（iii）；否則，取可增廣軌，令，轉(zhuǎn)（ii）。由上述定理可以得出：應用人員分派問題：工作人員24最優(yōu)分派問題：在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數(shù)學模型是：在人員分派問題的模型中，圖的每邊加了權(quán)，表示干工作的效益，求加權(quán)圖上的權(quán)最大的完美對集。解決這個問題可以用庫恩—曼克萊斯（Kuhn-Munkres）算法。為此，我們要引入可行頂點標號與相等子圖的概念。定義若映射，滿足，，則稱是二分圖的可行頂點標號。令，稱以為邊集的的生成子圖為相等子圖，記作。可行頂點標號是存在的。例如定理5的完美對集即為的權(quán)最大的完美對集。最優(yōu)分派問題：在人員分派問題中，工作人員適合做的各項工作當中25Kuhn-Munkres算法（i）選定初始可行頂點標號，確定，在中選取一個對集。（ii）若中頂點皆被許配，停止，即的權(quán)最大的完美對集；否則，取中未被許配的頂點，令，。(iii)若，轉(zhuǎn)（iv）；若，取，

，

，。（iv）選中一頂點，若已被許配，且，則，，轉(zhuǎn)（iii）；否則，取中一個可增廣軌，令，轉(zhuǎn)（ii）。其中是中的相鄰頂點集。Kuhn-Munkres算法26Euler圖和Hamilton圖基本概念定義經(jīng)過的每條邊的跡叫做的Euler跡；閉的Euler跡叫做Euler回路或回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的邊再回到出發(fā)點。定理7（i）是Euler圖的充分必要條件是連通且每頂點皆偶次。（ii）是Euler圖的充分必要條件是連通且，是圈，。（iii）中有Euler跡的充要條件是連通且至多有兩個奇次點。定義包含的每個頂點的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖，即不重復地行遍所有的頂點再回到出發(fā)點。Euler圖和Hamilton圖基本概念定義經(jīng)過276.2Euler回路的Fleury算法1921年，F(xiàn)leury給出下面的求Euler回路的算法。Fleury算法：1.，令。2.假設跡已經(jīng)選定，那么按下述方法從中選取邊：（i）和相關(guān)聯(lián)；（ii）除非沒有別的邊可選擇，否則不是的割邊(cutedge)。(所謂割邊是一條刪除后使連通圖不再連通的邊)。3.當?shù)?步不能再執(zhí)行時，算法停止。6.3應用6.3.1郵遞員問題中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當然他必須經(jīng)過他負責投遞的每條街道至少一次，為他設計一條投遞路線，使得他行程最短。上述中國郵遞員問題的數(shù)學模型是：在一個賦權(quán)連通圖上求一個含所有邊的回路，且使此回路的權(quán)最小。顯然，若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。6.2Euler回路的Fleury算法Fleury算法：286.3.2旅行商（TSP）問題一名推銷員準備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這個問題稱為旅行商問題。用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，找出一個有最小權(quán)的Hamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優(yōu)）的解。一個可行的辦法是首先求一個Hamilton圈，然后適當修改以得到具有較小權(quán)的另一個Hamilton圈。修改的方法叫做改良圈算法。設初始圈。（i）對于，構(gòu)造新的Hamilton圈:,它是由中刪去邊和，添加邊和而得到的。若，則以代替，叫做的改良圈。（ii）轉(zhuǎn)（i），直至無法改進，停止用改良圈算法得到的結(jié)果幾乎可以肯定不是最優(yōu)的。為了得到更高的精確度，可以選擇不同的初始圈，重復進行幾次算法，以求得較精確的結(jié)果。例13從北京（Pe）乘飛機到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：6.3.2旅行商（TSP）問題一名推銷員準備前往若干城市29LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113LMNPaPeTL5635215160M562157787030解：編寫程序如下：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,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a';c1=[51:46];L=length(c1);flag=1;whileflag>0flag=0;form=1:L-3forn=m+2:L-1ifa(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);endend

解：編寫程序如下：31endendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endcircle=c1;sum=sum1;c1=[561:4];%改變初始圈，該算法的最后一個頂點不動flag=1;whileflag>0flag=0;form=1:L-3forn=m+2:L-1ifa(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);endendendendend32sum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endifsum1<sumsum=sum1;circle=c1;endcircle,sumsum1=0;33圖與網(wǎng)絡模型及方法概論圖論起源于18世紀。第一篇圖論論文是瑞士數(shù)學家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。1847年，克?；舴驗榱私o出電網(wǎng)絡方程而引進了“樹”的概念。1857年，凱萊在計數(shù)烷的同分異構(gòu)物時，也發(fā)現(xiàn)了“樹”。哈密爾頓于1859年提出“周游世界”游戲，用圖論的術(shù)語，就是如何找出一個連通圖中的生成圈。近幾十年來，由于計算機技術(shù)和科學的飛速發(fā)展，大大地促進了圖論研究和應用，圖論的理論和方法已經(jīng)滲透到物理、化學、通訊科學、建筑學、生物遺傳學、心理學、經(jīng)濟學、社會學等學科中。圖得概念：圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點表示這些具體事物，用連接兩點的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學模型，借助于圖論的概念、理論和方法，可以對該模型求解。圖與網(wǎng)絡模型及方法概論圖論起源于18世紀。第一篇圖論論文是34例子：哥尼斯堡七橋問題：在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點可以通過試驗去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個問題，采用了建立數(shù)學模型的方法。他將每一塊陸地用一個點來代替，將每一座橋用連接相應兩點的一條線來代替，從而得到一個有四個“點”，七條“線”的“圖”。問題成為從任一點出發(fā)一筆畫出七條線再回到起點。歐拉考察了一般一筆畫的結(jié)構(gòu)特點，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點都與偶數(shù)線相關(guān)聯(lián)，將這個判定法則應用于七橋問題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。例子：哥尼斯堡七橋問題：在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩35圖論的應用：圖與網(wǎng)絡是運籌學（OperationsResearch）中的一個經(jīng)典和重要的分支，所研究的問題涉及經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術(shù)、通訊與網(wǎng)絡技術(shù)等諸多領(lǐng)域。圖與網(wǎng)絡優(yōu)化的一些基本問題：例1最短路問題（SPP－shortestpathproblem）一名貨柜車司機奉命在最短的時間內(nèi)將一車貨物從甲地運往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于需要找到一條從甲地到乙地的最短路。例2公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最??？例3指派問題（assignmentproblem）一家公司經(jīng)理準備安排名員工去完成項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大？圖論的應用：圖與網(wǎng)絡是運籌學（OperationsRese36例4中國郵遞員問題（CPP－chinesepostmanproblem）一名郵遞員負責投遞某個街區(qū)的郵件。如何為他（她）設計一條最短的投遞路線（從郵局出發(fā)，經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問題是我國管梅谷教授1960年首先提出的，所以國際上稱之為中國郵遞員問題。例5旅行商問題（TSP－travelingsalesmanproblem）一名推銷員準備前往若干城市推銷產(chǎn)品。如何為他（她）設計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這一問題的研究歷史十分悠久，通常稱之為旅行商問題。例6運輸問題（transportationproblem）某種原材料有個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運往個使用這些原材料的工廠。假定每個產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運費已知，那么如何安排運輸方案可以使總運輸成本最低？上述問題有兩個共同的特點：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學上把這種問題稱為最優(yōu)化或優(yōu)化（optimization）問題；二是它們都易于用圖形的形式直觀地描述和表達，數(shù)學上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡（network）。與圖和網(wǎng)絡相關(guān)的最優(yōu)化問題就是網(wǎng)絡最優(yōu)化或稱網(wǎng)絡優(yōu)化（netwokoptimization）問題。所以上面例子中介紹的問題都是網(wǎng)絡優(yōu)化問題。由于多數(shù)網(wǎng)絡優(yōu)化問題是以網(wǎng)絡上的流（flow）為研究的對象，因此網(wǎng)絡優(yōu)化又常常被稱為網(wǎng)絡流（networkflows）或網(wǎng)絡流規(guī)劃等例4中國郵遞員問題（CPP－chinesepostma37

圖與網(wǎng)絡的基本概念

無向圖：一個無向圖(undirectedgraph)G是由一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集（vertexset）或節(jié)點集（nodeset），中的每一個元素稱為該圖的一個頂點（vertex）或節(jié)點（node）；稱為圖的邊集（edgeset），中的每一個元素(即中某兩個元素的無序?qū)?

記為或，被稱為該圖的一條從到的邊（edge）。當邊時，稱為邊的端點，并稱與相鄰（adjacent）；邊稱為與頂點關(guān)聯(lián)（incident）。如果某兩條邊至少有一個公共端點，則稱這兩條邊在圖中相鄰。邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡（undirectednetwork）。我們對圖和網(wǎng)絡不作嚴格區(qū)分，因為任何圖總是可以賦權(quán)的。一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖的頂點數(shù)用符號或表示，邊數(shù)用或表示。端點重合為一點的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點。圖與網(wǎng)絡的基本概念無向圖：一個無向圖(undirecte38有向圖：當圖的邊集中的邊是頂點的有序?qū)r，這時候就稱為這些邊是有方向的。從而原來的無向圖也就成為這兒的有向圖。頂點的度：一個頂點的度是與這個頂點相關(guān)聯(lián)的邊的數(shù)目。在有向圖的情形下，一個頂點的度還分為頂點入度和頂點出度兩種情形。頂點的入度是與這個頂點相關(guān)聯(lián)的并且指向這個頂點的邊的數(shù)目。頂點的出度是與這個頂點相關(guān)聯(lián)的并且方向遠離這個頂點的邊的數(shù)目。圖與網(wǎng)絡的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡優(yōu)化研究的是網(wǎng)絡上的各種優(yōu)化模型與算法．為了在計算機上實現(xiàn)網(wǎng)絡優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計算機上來描述圖與網(wǎng)絡。一般來說，算法的好壞與網(wǎng)絡的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計算機上用來描述圖與網(wǎng)絡的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設是一個簡單有向圖，，并假設中的頂點用自然數(shù)表示或編號，中的弧用自然數(shù)表示或編號。對于有多重邊或無向網(wǎng)絡的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。有向圖：當圖的邊集中的邊是頂點的有序?qū)r，這時候就稱為這些邊39（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：是一個的矩陣，即也就是說，如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應的元素為1；否則為0?？梢钥闯?，這種表示法非常簡單、直接。但是，在鄰接矩陣的所有個元素中，只有個為非零元。如果網(wǎng)絡比較稀疏，這種表示法浪費大量的存儲空間，從而增加了在網(wǎng)絡中查找弧的時間。例7對于上圖所示的圖，可以用鄰接矩陣表示為（i）鄰接矩陣表示法也就是說，如果兩節(jié)點之間有一條弧，則鄰接40，

同樣，對于網(wǎng)絡中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應的元素不再是1，而是相應的權(quán)而已。如果網(wǎng)絡中每條弧賦有多種權(quán)，則可以用多個矩陣表示這些權(quán)。（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲在計算機中．圖的關(guān)聯(lián)矩陣是如下定義的：是一個的矩陣，即也就是說，在關(guān)聯(lián)矩陣中，每行對應于圖的一個節(jié)點，每列對應于圖的一條弧。如果一個節(jié)點是一條弧的起點，則關(guān)上聯(lián)矩陣中對應的元素為1；如果一個節(jié)點是一條弧的終點，則關(guān)聯(lián)矩陣中對應的元素為-1；如果一個節(jié)點與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應的元素為0。對于簡單圖，關(guān)聯(lián)矩陣每列只含有兩個非零元（一個+1，一個-1）?？梢钥闯?，這種表示法也非常簡單、直接。但是，在關(guān)聯(lián)矩陣的所有nm個元素中，只有2m個為非零元。如果網(wǎng)絡比較稀疏，這種表示法也會浪費大量的存儲空間。但由于關(guān)聯(lián)矩陣有許多特別重要的理論性質(zhì)，因此它在網(wǎng)絡優(yōu)化中是非常重要的概念。，同樣，對于網(wǎng)絡中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是41例8對于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對應弧的順序為(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為:同樣，對于網(wǎng)絡中的權(quán)，也可以通過對關(guān)聯(lián)矩陣的擴展來表示。例如，如果網(wǎng)絡中每條弧有一個權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對應的權(quán)存儲在增加的行中。如果網(wǎng)絡中每條弧賦有多個權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應的行數(shù)，把每一條弧所對應的權(quán)存儲在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)Α；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c和終點，共需2m個存儲單元，因此當網(wǎng)絡比較稀疏時比較方便。此外，對于網(wǎng)絡圖中每條弧上的權(quán)，也要對應地用額外的存儲單元表示。例如，例7所示的圖，假設弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的權(quán)分別為8，9，6，4，0，3，6和7，則弧表表示如下：例8對于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對應弧的順序為(42起點11234455終點23423534權(quán)89640367為了便于檢索，一般按照起點、終點的字典序順序存儲弧表，如上面的弧表就是按照這樣的順序存儲的。（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲在計算機中。所謂圖的鄰接表，也就是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點，用一個單向鏈表列出從該節(jié)點出發(fā)的所有弧，鏈表中每個單元對應于一條出弧。為了記錄弧上的權(quán)，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。例如，例7所示的圖，鄰接表表示為起點11234455終點23423534權(quán)89640367為43這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應于一個節(jié)點的鄰接表，如第1行對應于第1個節(jié)點的鄰接表（即第1個節(jié)點的所有出?。Ｃ總€指針單元的第1個數(shù)據(jù)域表示弧的另一個端點（弧的頭），后面的數(shù)據(jù)域表示對應弧上的權(quán)。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2）），“8”表示對應弧(1,2)上的權(quán)為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應弧（1，3）上的權(quán)為9。又如，第5行說明節(jié)點5出發(fā)的弧有(5,3)、(5,4)，他們對應的權(quán)分別為6和7。對于有向圖，一般用表示節(jié)點的鄰接表，即節(jié)點的所有出弧構(gòu)成的集合或鏈表（實際上只需要列出弧的另一個端點，即弧的頭）。例如上面例子，，等。這種記法我們在本書后面將會經(jīng)常用到。，

（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點，它也是記錄從該節(jié)點出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示。也就是說，在該數(shù)組中首先存放從節(jié)點1出發(fā)的所有弧，然后接著存放從節(jié)點2出發(fā)的所有孤，依此類推，最后存放從節(jié)點出發(fā)的所有孤。對每條弧，要依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。這實際上相當于對所有弧給出了一個順序和編號，只是從同一節(jié)點出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個節(jié)點出發(fā)的所有弧，我們一般還用一個數(shù)組記錄每個節(jié)點出發(fā)的弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有弧，這種星形表示法稱為前向星形（forwardstar）表示法。這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應于一44例如，在例7所示的圖中，仍然假設?。?,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的權(quán)分別為8，9，6，4，0，3，6和7。此時該網(wǎng)絡圖可以用前向星形表示法表示如下：節(jié)點對應的出弧的起始地址編號數(shù)組（記為）節(jié)點號起始地址123456134679記錄弧信息的數(shù)組弧編號12345678起點11234455終點23423534權(quán)89640367在數(shù)組中，其元素個數(shù)比圖的節(jié)點數(shù)多1（即n+1），且一定有，。對于節(jié)點，其對應的出弧存放在弧信息數(shù)組的位置區(qū)間為，

例如，在例7所示的圖中，仍然假設?。?,2），（l,3），（45如果，則節(jié)點沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組（）記錄每個節(jié)點出發(fā)的弧的起始編號。前向星形表示法有利于快速檢索每個節(jié)點的所有出弧，但不能快速檢索每個節(jié)點的所有入弧。為了能夠快速檢索每個節(jié)點的所有入孤，可以采用反向星形（reversestar）表示法：首先存放進入節(jié)點1的所有孤，然后接著存放進入節(jié)點2的所有弧，依此類推，最后存放進入節(jié)點的所有孤。對每條弧，仍然依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個節(jié)點的所有入弧，我們一般還用一個數(shù)組記錄每個節(jié)點的入孤的起始地址（即弧的編號）。例如，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點對應的入弧的起始地址編號數(shù)組（記為）節(jié)點號123456起始地址113689記錄弧信息的數(shù)組弧編號12345678終點22333445起點31145524權(quán)48906763如果46如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點的所有入弧，則可以綜合采用前向和反向星形表示法。當然，將孤信息存放兩次是沒有必要的，可以只用一個數(shù)組（trace）記錄一條弧在兩種表示法中的對應關(guān)系即可。例如，可以在采用前向星形表示法的基礎上，加上上面介紹的數(shù)組和如下的數(shù)組即可。這相當于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對應關(guān)系（記為）反向法中弧編號正向法中弧編號1234567841257836對于網(wǎng)絡圖的表示法，我們作如下說明星形表示法和鄰接表表示法在實際算法實現(xiàn)中都是經(jīng)常采用的。星形表示法的優(yōu)點是占用的存儲空間較少，并且對那些不提供指針類型的語言（如FORTRAN語言等）也容易實現(xiàn)。鄰接表表示法對那些提供指針類型的語言（如C語言等）是方便的，且增加或刪除一條弧所需的計算工作量很少，而這一操作在星形表示法中所需的計算工作量較大（需要花費計算時間）。有關(guān)“計算時間”的觀念是網(wǎng)絡優(yōu)化中需要考慮的一個關(guān)鍵因素。當網(wǎng)絡不是簡單圖，而是具有平行?。炊嘀鼗。r，顯然此時鄰接矩陣表示法是不能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點47上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計算機中只存儲鄰接矩陣的一半信息（如上三角部分），因為此時鄰接矩陣是對稱矩陣。無向圖的關(guān)聯(lián)矩陣只含有元素0和+1，而不含有-1，因為此時不區(qū)分邊的起點和終點。又如，在鄰接表和星形表示法中，每條邊會被存儲兩次，而且反向星形表示顯然是沒有必要的，等等。軌與連通，其中，。其中與關(guān)聯(lián)。W稱為圖G的一條道路，k為路長。頂點稱為W的起點和終點。若道路W的邊互不相同，則W稱為跡(trail)。若道路W的頂點互不相同，則W稱為軌(path)。稱一條道路是閉的，如果它有正的長且起點和終點相同。起點和終點重合的軌叫做圈.若圖G的兩個頂點u,v間存在道路，則稱u和v連通(connected)。U,v間的最短軌的長叫做U,v間的距離。記作d(u,v)。若圖G的任二頂點均連通，則稱G是連通圖。上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖48應用兩個指定頂點之間的最短距離問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡，在這個網(wǎng)絡的兩個指定城鎮(zhèn)間，找一條最短鐵路線以各城鎮(zhèn)為圖G的頂點，兩城鎮(zhèn)間的直通鐵路為圖G相應兩頂點間的邊，得圖G。對G的每一邊e，賦以一個實數(shù)w(e)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠為順序，依次求得到的各頂點的最短路和距離，直至（或直至G的所有頂點），算法結(jié)束。為避免重復并保留每一步的計算信息，采用了標號算法.下面是該算法。應用兩個指定頂點之間的最短距離問題如下：給出了一個連接若干個49(i令，對，令，，。(ii)對每個（），用

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

存放始點到第點最短通路中第頂點前一頂點的序號；存放由始點到第點最短通路的值。求第一個城市到其它城市的最短路徑的Matlab程序如下：例9某公司在六個城市