數(shù)學(xué)建模-圖與網(wǎng)絡(luò)模型及方法Word版

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

記為或，被稱為該圖的一條從到的邊（edge）。當(dāng)邊時(shí)，稱為邊的端點(diǎn)，并稱與相鄰（adjacent）；邊稱為與頂點(diǎn)關(guān)聯(lián)（incident）。如果某兩條邊至少有一個(gè)公共端點(diǎn)，則稱這兩條邊在圖中相鄰。邊上賦權(quán)的無向圖稱為賦權(quán)無向圖或無向網(wǎng)絡(luò)（undirectednetwork）。我們對(duì)圖和網(wǎng)絡(luò)不作嚴(yán)格區(qū)分，因?yàn)槿魏螆D總是可以賦權(quán)的。整理為word格式整理為word格式整理為word格式一個(gè)圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有限。圖的頂點(diǎn)數(shù)用符號(hào)或表示，邊數(shù)用或表示。當(dāng)討論的圖只有一個(gè)時(shí)，總是用來表示這個(gè)圖。從而在圖論符號(hào)中我們常略去字母，例如，分別用和代替和。端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)(loop)。一個(gè)圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對(duì)頂點(diǎn)。2.2有向圖定義一個(gè)有向圖（directedgraph或digraph）是由一個(gè)非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點(diǎn)集或節(jié)點(diǎn)集，中的每一個(gè)元素稱為該圖的一個(gè)頂點(diǎn)或節(jié)點(diǎn)；稱為圖的弧集（arcset），中的每一個(gè)元素(即中某兩個(gè)元素的有序?qū)?

記為或，被稱為該圖的一條從到的?。╝rc）。當(dāng)弧時(shí)，稱為的尾（tail），為的頭（head），并稱弧為的出弧（outgoingarc），為的入弧（incomingarc）。對(duì)應(yīng)于每個(gè)有向圖，可以在相同頂點(diǎn)集上作一個(gè)圖，使得對(duì)于的每條弧，有一條有相同端點(diǎn)的邊與之相對(duì)應(yīng)。這個(gè)圖稱為的基礎(chǔ)圖。反之，給定任意圖，對(duì)于它的每個(gè)邊，給其端點(diǎn)指定一個(gè)順序，從而確定一條弧，由此得到一個(gè)有向圖，這樣的有向圖稱為的一個(gè)定向圖。以下若未指明“有向圖”三字，“圖”字皆指無向圖。2.3完全圖、二分圖每一對(duì)不同的頂點(diǎn)都有一條邊相連的簡單圖稱為完全圖(completegraph)。個(gè)頂點(diǎn)的完全圖記為。若，，（這里表示集合中的元素個(gè)數(shù)），中無相鄰頂點(diǎn)對(duì)，中亦然，則稱為二分圖(bipartitegraph)；特別地，若，則，則稱為完全二分圖，記成。2.4子圖圖叫做圖的子圖（subgraph），記作，如果，。若是的子圖，則稱為的母圖。的支撐子圖（spanningsubgraph，又成生成子圖）是指滿足的子圖。2.5頂點(diǎn)的度設(shè)，中與關(guān)聯(lián)的邊數(shù)（每個(gè)環(huán)算作兩條邊）稱為的度(degree)，記作。若是奇數(shù)，稱是奇頂點(diǎn)(oddpoint)；是偶數(shù)，稱是偶頂點(diǎn)(evenpoint)。關(guān)于頂點(diǎn)的度，我們有如下結(jié)果：整理為word格式整理為word格式整理為word格式(=1\*romani)(=2\*romanii)任意一個(gè)圖的奇頂點(diǎn)的個(gè)數(shù)是偶數(shù)。2.6圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法．為了在計(jì)算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計(jì)算機(jī)上來描述圖與網(wǎng)絡(luò)。一般來說，算法的好壞與網(wǎng)絡(luò)的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計(jì)算機(jī)上用來描述圖與網(wǎng)絡(luò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個(gè)簡單有向圖，，并假設(shè)中的頂點(diǎn)用自然數(shù)表示或編號(hào)，中的弧用自然數(shù)表示或編號(hào)。對(duì)于有多重邊或無向網(wǎng)絡(luò)的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。（=1\*romani）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲(chǔ)在計(jì)算機(jī)中。圖的鄰接矩陣是如下定義的：是一個(gè)的矩陣，即，也就是說，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對(duì)應(yīng)的元素為1；否則為0?？梢钥闯觯@種表示法非常簡單、直接。但是，在鄰接矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法浪費(fèi)大量的存儲(chǔ)空間，從而增加了在網(wǎng)絡(luò)中查找弧的時(shí)間。例7對(duì)于右圖所示的圖，可以用鄰接矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時(shí)一條弧所對(duì)應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個(gè)矩陣表示這些權(quán)。（=2\*romanii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲(chǔ)在計(jì)算機(jī)中．圖的關(guān)聯(lián)矩陣是如下定義的：是一個(gè)的矩陣，即，整理為word格式整理為word格式整理為word格式也就是說，在關(guān)聯(lián)矩陣中，每行對(duì)應(yīng)于圖的一個(gè)節(jié)點(diǎn)，每列對(duì)應(yīng)于圖的一條弧。如果一個(gè)節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為1；如果一個(gè)節(jié)點(diǎn)是一條弧的終點(diǎn)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為；如果一個(gè)節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對(duì)應(yīng)的元素為0。對(duì)于簡單圖，關(guān)聯(lián)矩陣每列只含有兩個(gè)非零元（一個(gè)，一個(gè)）?？梢钥闯?，這種表示法也非常簡單、直接。但是，在關(guān)聯(lián)矩陣的所有個(gè)元素中，只有個(gè)為非零元。如果網(wǎng)絡(luò)比較稀疏，這種表示法也會(huì)浪費(fèi)大量的存儲(chǔ)空間。但由于關(guān)聯(lián)矩陣有許多特別重要的理論性質(zhì)，因此它在網(wǎng)絡(luò)優(yōu)化中是非常重要的概念。例8對(duì)于例7所示的圖，如果關(guān)聯(lián)矩陣中每列對(duì)應(yīng)弧的順序?yàn)?1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為同樣，對(duì)于網(wǎng)絡(luò)中的權(quán)，也可以通過對(duì)關(guān)聯(lián)矩陣的擴(kuò)展來表示。例如，如果網(wǎng)絡(luò)中每條弧有一個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。如果網(wǎng)絡(luò)中每條弧賦有多個(gè)權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把每一條弧所對(duì)應(yīng)的權(quán)存儲(chǔ)在增加的行中。（=3\*romaniii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)??；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c(diǎn)和終點(diǎn)，共需個(gè)存儲(chǔ)單元，因此當(dāng)網(wǎng)絡(luò)比較稀疏時(shí)比較方便。此外，對(duì)于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對(duì)應(yīng)地用額外的存儲(chǔ)單元表示。例如，例7所示的圖，假設(shè)弧(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，則弧表表示如下：起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367為了便于檢索，一般按照起點(diǎn)、終點(diǎn)的字典序順序存儲(chǔ)弧表，如上面的弧表就是按照這樣的順序存儲(chǔ)的。（=4\*romaniv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲(chǔ)在計(jì)算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對(duì)每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧。鄰接表表示法就是對(duì)圖的每個(gè)節(jié)點(diǎn)，用一個(gè)單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有弧，鏈表中每個(gè)單元對(duì)應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個(gè)單元除列出弧的另一個(gè)端點(diǎn)外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個(gè)鄰接表可以用一個(gè)指針數(shù)組表示。例如，例7所示的圖，鄰接表表示為整理為word格式整理為word格式整理為word格式這是一個(gè)5維指針數(shù)組，每一維（上面表示法中的每一行）對(duì)應(yīng)于一個(gè)節(jié)點(diǎn)的鄰接表，如第1行對(duì)應(yīng)于第1個(gè)節(jié)點(diǎn)的鄰接表（即第1個(gè)節(jié)點(diǎn)的所有出?。?。每個(gè)指針單元的第1個(gè)數(shù)據(jù)域表示弧的另一個(gè)端點(diǎn)（弧的頭），后面的數(shù)據(jù)域表示對(duì)應(yīng)弧上的權(quán)。如第1行中的“2”表示弧的另一個(gè)端點(diǎn)為2（即弧為（1,2）），“8”表示對(duì)應(yīng)弧(1,2)上的權(quán)為8；“3”表示弧的另一個(gè)端點(diǎn)為3（即弧為(1,3)），“9”表示對(duì)應(yīng)弧（1，3）上的權(quán)為9。又如，第5行說明節(jié)點(diǎn)5出發(fā)的弧有(5,3)、(5,4)，他們對(duì)應(yīng)的權(quán)分別為6和7。對(duì)于有向圖，一般用表示節(jié)點(diǎn)的鄰接表，即節(jié)點(diǎn)的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個(gè)端點(diǎn)，即弧的頭）。例如上面例子，，等。這種記法我們在本書后面將會(huì)經(jīng)常用到。（=5\*romanv）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對(duì)每個(gè)節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個(gè)單一的數(shù)組表示。也就是說，在該數(shù)組中首先存放從節(jié)點(diǎn)1出發(fā)的所有弧，然后接著存放從節(jié)點(diǎn)2出發(fā)的所有孤，依此類推，最后存放從節(jié)點(diǎn)出發(fā)的所有孤。對(duì)每條弧，要依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。這實(shí)際上相當(dāng)于對(duì)所有弧給出了一個(gè)順序和編號(hào)，只是從同一節(jié)點(diǎn)出發(fā)的弧的順序可以任意排列。此外，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始地址（即弧的編號(hào)）。在這種表示法中，可以快速檢索從每個(gè)節(jié)點(diǎn)出發(fā)的所有弧，這種星形表示法稱為前向星形（forwardstar）表示法。例如，在例7所示的圖中，仍然假設(shè)弧（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。此時(shí)該網(wǎng)絡(luò)圖可以用前向星形表示法表示如下：節(jié)點(diǎn)對(duì)應(yīng)的出弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456起始地址134679記錄弧信息的數(shù)組弧編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367在數(shù)組中，其元素個(gè)數(shù)比圖的節(jié)點(diǎn)數(shù)多1（即），且一定有，。對(duì)于節(jié)點(diǎn)，其對(duì)應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為整理為word格式整理為word格式整理為word格式，如果，則節(jié)點(diǎn)沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實(shí)際上相當(dāng)于有序存放的“弧表”。只是在前向星形表示法中，弧被編號(hào)后有序存放，并增加一個(gè)數(shù)組（）記錄每個(gè)節(jié)點(diǎn)出發(fā)的弧的起始編號(hào)。前向星形表示法有利于快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，但不能快速檢索每個(gè)節(jié)點(diǎn)的所有入弧。為了能夠快速檢索每個(gè)節(jié)點(diǎn)的所有入孤，可以采用反向星形（reversestar）表示法：首先存放進(jìn)入節(jié)點(diǎn)1的所有孤，然后接著存放進(jìn)入節(jié)點(diǎn)2的所有弧，依此類推，最后存放進(jìn)入節(jié)點(diǎn)的所有孤。對(duì)每條弧，仍然依次存放其起點(diǎn)、終點(diǎn)、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個(gè)節(jié)點(diǎn)的所有入弧，我們一般還用一個(gè)數(shù)組記錄每個(gè)節(jié)點(diǎn)的入孤的起始地址（即弧的編號(hào)）。例如，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點(diǎn)對(duì)應(yīng)的入弧的起始地址編號(hào)數(shù)組（記為）節(jié)點(diǎn)號(hào)123456起始地址113689記錄弧信息的數(shù)組弧編號(hào)12345678終點(diǎn)22333445起點(diǎn)31145524權(quán)48906763如果既希望快速檢索每個(gè)節(jié)點(diǎn)的所有出弧，也希望快速檢索每個(gè)節(jié)點(diǎn)的所有入弧，則可以綜合采用前向和反向星形表示法。當(dāng)然，將孤信息存放兩次是沒有必要的，可以只用一個(gè)數(shù)組（trace）記錄一條弧在兩種表示法中的對(duì)應(yīng)關(guān)系即可。例如，可以在采用前向星形表示法的基礎(chǔ)上，加上上面介紹的數(shù)組和如下的數(shù)組即可。這相當(dāng)于一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對(duì)應(yīng)關(guān)系（記為）反向法中弧編號(hào)12345678正向法中弧編號(hào)41257836對(duì)于網(wǎng)絡(luò)圖的表示法，我們作如下說明：=1\*GB3①星形表示法和鄰接表表示法在實(shí)際算法實(shí)現(xiàn)中都是經(jīng)常采用的。星形表示法的優(yōu)點(diǎn)是占用的存儲(chǔ)空間較少，并且對(duì)那些不提供指針類型的語言（如FORTRAN語言等）也容易實(shí)現(xiàn)。鄰接表表示法對(duì)那些提供指針類型的語言（如C語言等）是方便的，且增加或刪除一條弧所需的計(jì)算工作量很少，而這一操作在星形表示法中所需的計(jì)算工作量較大（需要花費(fèi)的計(jì)算時(shí)間）。有關(guān)“計(jì)算時(shí)間”的觀念是網(wǎng)絡(luò)優(yōu)化中需要考慮的一個(gè)關(guān)鍵因素。=2\*GB3②當(dāng)網(wǎng)絡(luò)不是簡單圖，而是具有平行?。炊嘀鼗。r(shí)，顯然此時(shí)鄰接矩陣表示法是不能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。=3\*GB3③上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計(jì)算機(jī)中只存儲(chǔ)鄰接矩陣的一半信息（如上三角部分），因?yàn)榇藭r(shí)鄰接矩陣是對(duì)稱矩陣。無向圖的關(guān)聯(lián)矩陣只含有元素0和整理為word格式整理為word格式整理為word格式，而不含有，因?yàn)榇藭r(shí)不區(qū)分邊的起點(diǎn)和終點(diǎn)。又如，在鄰接表和星形表示法中，每條邊會(huì)被存儲(chǔ)兩次，而且反向星形表示顯然是沒有必要的，等等。2.7軌與連通，其中，，，，與關(guān)聯(lián)，稱是圖的一條道路(walk)，為路長，頂點(diǎn)和分別稱為的起點(diǎn)和終點(diǎn)，而稱為它的內(nèi)部頂點(diǎn)。若道路的邊互不相同，則稱為跡(trail)。若道路的頂點(diǎn)互不相同，則稱為軌(path)。稱一條道路是閉的，如果它有正的長且起點(diǎn)和終點(diǎn)相同。起點(diǎn)和終點(diǎn)重合的軌叫做圈(cycle)。若圖的兩個(gè)頂點(diǎn)間存在道路，則稱和連通(connected)。間的最短軌的長叫做間的距離。記作。若圖的任二頂點(diǎn)均連通，則稱是連通圖。顯然有：(=1\*romani)圖是一條軌的充要條件是是連通的，且有兩個(gè)一度的頂點(diǎn)，其余頂點(diǎn)的度為2；(=2\*romanii)圖是一個(gè)圈的充要條件是是各頂點(diǎn)的度均為2的連通圖?！?應(yīng)用—最短路問題3.1兩個(gè)指定頂點(diǎn)之間的最短路徑問題如下：給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖相應(yīng)兩頂點(diǎn)間的邊，得圖。對(duì)的每一邊，賦以一個(gè)實(shí)數(shù)—直通鐵路的長度，稱為的權(quán)，得到賦權(quán)圖。的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個(gè)頂點(diǎn)間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到的各頂點(diǎn)的最短路和距離，直至（或直至的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計(jì)算信息，采用了標(biāo)號(hào)算法。下面是該算法。(=1\*romani)令，對(duì)，令，，。(=2\*romanii)對(duì)每個(gè)（），用代替。計(jì)算，把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，令。整理為word格式整理為word格式整理為word格式(=3\*romaniii).若，停止；若，用代替，轉(zhuǎn)(=2\*romanii)。算法結(jié)束時(shí)，從到各頂點(diǎn)的距離由的最后一次的標(biāo)號(hào)給出。在進(jìn)入之前的標(biāo)號(hào)叫T標(biāo)號(hào)，進(jìn)入時(shí)的標(biāo)號(hào)叫P標(biāo)號(hào)。算法就是不斷修改各項(xiàng)點(diǎn)的T標(biāo)號(hào)，直至獲得P標(biāo)號(hào)。若在算法運(yùn)行過程中，將每一頂點(diǎn)獲得P標(biāo)號(hào)所由來的邊在圖上標(biāo)明，則算法結(jié)束時(shí)，至各項(xiàng)點(diǎn)的最短路也在圖上標(biāo)示出來了。例9某公司在六個(gè)城市中有分公司，從到的直接航程票價(jià)記在下述矩陣的位置上。（表示無直接航路），請幫助該公司設(shè)計(jì)一張城市到其它城市間的票價(jià)最便宜的路線圖。用矩陣（為頂點(diǎn)個(gè)數(shù)）存放各邊權(quán)的鄰接矩陣，行向量、、、分別用來存放標(biāo)號(hào)信息、標(biāo)號(hào)頂點(diǎn)順序、標(biāo)號(hào)頂點(diǎn)索引、最短通路的值。其中分量；存放始點(diǎn)到第點(diǎn)最短通路中第頂點(diǎn)前一頂點(diǎn)的序號(hào)；存放由始點(diǎn)到第點(diǎn)最短通路的值。求第一個(gè)城市到其它城市的最短路徑的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(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)));整理為word格式整理為word格式整理為word格式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,index23.2每對(duì)頂點(diǎn)之間的最短路徑計(jì)算賦權(quán)圖中各對(duì)頂點(diǎn)之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到從每一個(gè)頂點(diǎn)到其它頂點(diǎn)的最短路徑。這種算法的時(shí)間復(fù)雜度為。第二種解決這一問題的方法是由FloydRW提出的算法，稱之為Floyd算法。假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中：；之間沒有邊，在程序中以各邊都不可能達(dá)到的充分大的數(shù)代替；是之間邊的長度，。對(duì)于無向圖，是對(duì)稱矩陣，。Floyd算法的基本思想是：遞推產(chǎn)生一個(gè)矩陣序列，其中表示從頂點(diǎn)到頂點(diǎn)的路徑上所經(jīng)過的頂點(diǎn)序號(hào)不大于的最短路徑長度。計(jì)算時(shí)用迭代公式：是迭代次數(shù)，。最后，當(dāng)時(shí)，即是各頂點(diǎn)之間的最短通路值。例10用Floyd算法求解例1。矩陣path用來存放每對(duì)頂點(diǎn)之間最短路徑上所經(jīng)過的頂點(diǎn)的序號(hào)。Floyd算法的Matlab程序如下：clear;clc;整理為word格式整理為word格式整理為word格式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);b=a+a';path=zeros(length(b));fork=1:6fori=1:6forj=1:6ifb(i,j)>b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path§4樹4.1基本概念連通的無圈圖叫做樹，記之為。若圖滿足，，則稱是的生成樹。圖連通的充分必要條件為有生成樹。一個(gè)連通圖的生成樹的個(gè)數(shù)很多，用表示的生成樹的個(gè)數(shù)，則有公式公式(Caylay)。公式。其中表示從上刪除邊，表示把的長度收縮為零得到的圖。樹有下面常用的五個(gè)充要條件。定理1（=1\*romani）是樹當(dāng)且僅當(dāng)中任二頂點(diǎn)之間有且僅有一條軌道。（=2\*romanii）是樹當(dāng)且僅當(dāng)無圈，且。（=3\*romaniii）是樹當(dāng)且僅當(dāng)連通，且。（=4\*romaniv）是樹當(dāng)且僅當(dāng)連通，且，不連通。（=5\*romanv）是樹當(dāng)且僅當(dāng)無圈，，恰有一個(gè)圈。4.2應(yīng)用—連線問題欲修筑連接個(gè)城市的鐵路，已知城與城之間的鐵路造價(jià)為，設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低。連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。下面介紹構(gòu)造最小生成樹的兩種常用算法。prim算法構(gòu)造最小生成樹設(shè)置兩個(gè)集合和,其中用于存放的最小生成樹中的頂點(diǎn)，集合存放整理為word格式整理為word格式整理為word格式的最小生成樹中的邊。令集合的初值為（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)出發(fā)），集合的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點(diǎn)加入集合中，將邊加入集合中，如此不斷重復(fù)，直到時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合中包含了最小生成樹的所有邊。prim算法如下：（=1\*romani），；（=2\*romanii）whileend例11用prim算法求右圖的最小生成樹。我們用的第一、二、三行分別表示生成樹邊的起點(diǎn)、終點(diǎn)、權(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))=[];endresultKruskal算法構(gòu)造最小生成樹科茹斯克爾（Kruskal）算法是一個(gè)好算法。Kruskal算法如下:(=1\*romani)選，使得。(=2\*romanii)若已選好，則從中選取，使得=1\*GB3①中無圈，且=2\*GB3②。整理為word格式整理為word格式整理為word格式(=3\*romaniii)直到選得為止。例12用Kruskal算法構(gòu)造例3的最小生成樹。我們用存放各邊端點(diǎn)的信息，當(dāng)選中某一邊之后，就將此邊對(duì)應(yīng)的頂點(diǎn)序號(hào)中較大序號(hào)改記為此邊的另一序號(hào)，同時(shí)把后面邊中所有序號(hào)為的改記為。此方法的幾何意義是：將序號(hào)的這個(gè)頂點(diǎn)收縮到頂點(diǎn)，頂點(diǎn)不復(fù)存在。后面繼續(xù)尋查時(shí)，發(fā)現(xiàn)某邊的兩個(gè)頂點(diǎn)序號(hào)相同時(shí)，認(rè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§5匹配問題定義若，，與無公共端點(diǎn)（），則稱為圖的一個(gè)對(duì)集；中的一條邊的兩個(gè)端點(diǎn)叫做在對(duì)集中相配；中的端點(diǎn)稱為被許配；中每個(gè)頂點(diǎn)皆被許配時(shí)，稱為完美對(duì)集；中已無使整理為word格式整理為word格式整理為word格式的對(duì)集，則稱為最大對(duì)集；若中有一軌，其邊交替地在對(duì)集內(nèi)外出現(xiàn)，則稱此軌為的交錯(cuò)軌，交錯(cuò)軌的起止頂點(diǎn)都未被許配時(shí)，此交錯(cuò)軌稱為可增廣軌。若把可增廣軌上在外的邊納入對(duì)集，把內(nèi)的邊從對(duì)集中刪除，則被許配的頂點(diǎn)數(shù)增加2，對(duì)集中的“對(duì)兒”增加一個(gè)。1957年，貝爾熱(Berge)得到最大對(duì)集的充要條件：定理2是圖中的最大對(duì)集當(dāng)且僅當(dāng)中無可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3為二分圖，與是頂點(diǎn)集的劃分，中存在把中頂點(diǎn)皆許配的對(duì)集的充要條件是，，則，其中是中頂點(diǎn)的鄰集。由上述定理可以得出：推論1：若是（正則2分圖，則有完美對(duì)集。所謂正則圖，即每頂點(diǎn)皆度的圖。由此推論得出下面的婚配定理：定理4每個(gè)姑娘都結(jié)識(shí)位小伙子，每個(gè)小伙子都結(jié)識(shí)位姑娘，則每位姑娘都能和她認(rèn)識(shí)的一個(gè)小伙子結(jié)婚，并且每位小伙子也能和他認(rèn)識(shí)的一個(gè)姑娘結(jié)婚。人員分派問題等實(shí)際問題可以化成對(duì)集來解決。人員分派問題：工作人員去做件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個(gè)問題的數(shù)學(xué)模型是：是二分圖，頂點(diǎn)集劃分為，，，當(dāng)且僅當(dāng)適合做工作時(shí)，，求中的最大對(duì)集。解決這個(gè)問題可以利用1965年埃德門茲(Edmonds)提出的匈牙利算法。匈牙利算法：（=1\*romani）從中任意取定一個(gè)初始對(duì)集。（=2\*romanii）若把中的頂點(diǎn)皆許配，停止，即完美對(duì)集；否則取中未被許配的一頂點(diǎn)，記，。（=3\*romaniii）若，停止，無完美對(duì)集；否則取。（=4\*romaniv）若是被許配的，設(shè)，，，轉(zhuǎn)（=3\*romaniii）；否則，取可增廣軌，令，轉(zhuǎn)（=2\*romanii）。把以上算法稍加修改就能夠用來求二分圖的最大對(duì)集。最優(yōu)分派問題：在人員分派問題中，工作人員適合做的各項(xiàng)工作當(dāng)中，效益未必一致，我們需要制定一個(gè)分派方案，使公司總效益最大。這個(gè)問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖的每邊加了權(quán)，表示干工作的效益，求加權(quán)圖上的權(quán)最大的完美對(duì)集。解決這個(gè)問題可以用庫恩—曼克萊斯（Kuhn-Munkres）算法。為此，我們要引入可行頂點(diǎn)標(biāo)號(hào)與相等子圖的概念。定義若映射，滿足，整理為word格式整理為word格式整理為word格式，則稱是二分圖的可行頂點(diǎn)標(biāo)號(hào)。令，稱以為邊集的的生成子圖為相等子圖，記作?？尚许旤c(diǎn)標(biāo)號(hào)是存在的。例如。定理5的完美對(duì)集即為的權(quán)最大的完美對(duì)集。Kuhn-Munkres算法（=1\*romani）選定初始可行頂點(diǎn)標(biāo)號(hào)，確定，在中選取一個(gè)對(duì)集。（=2\*romanii）若中頂點(diǎn)皆被許配，停止，即的權(quán)最大的完美對(duì)集；否則，取中未被許配的頂點(diǎn)，令，。(=3\*romaniii)若，轉(zhuǎn)（=4\*romaniv）；若，取，， ，。（=4\*romaniv）選中一頂點(diǎn)，若已被許配，且，則，，轉(zhuǎn)（=3\*romaniii）；否則，取中一個(gè)可增廣軌，令，轉(zhuǎn)（=2\*romanii）。其中是中的相鄰頂點(diǎn)集?！?Euler圖和Hamilton圖6.1基本概念定義經(jīng)過的每條邊的跡叫做的Euler跡；閉的Euler跡叫做Euler回路或回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點(diǎn)出發(fā)每邊恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的邊再回到出發(fā)點(diǎn)。定理7（=1\*romani）是Euler圖的充分必要條件是連通且每頂點(diǎn)皆偶次。（=2\*romanii）是Euler圖的充分必要條件是連通且，是圈，。（=3\*romaniii）中有Euler跡的充要條件是連通且至多有兩個(gè)奇次點(diǎn)。整理為word格式整理為word格式整理為word格式定義包含的每個(gè)頂點(diǎn)的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點(diǎn)出發(fā)每頂點(diǎn)恰通過一次能回到出發(fā)點(diǎn)的那種圖，即不重復(fù)地行遍所有的頂點(diǎn)再回到出發(fā)點(diǎn)。6.2Euler回路的Fleury算法1921年，F(xiàn)leury給出下面的求Euler回路的算法。Fleury算法：1o.，令。2o.假設(shè)跡已經(jīng)選定，那么按下述方法從中選取邊：（=1\*romani）和相關(guān)聯(lián)；（=2\*romanii）除非沒有別的邊可選擇，否則不是的割邊(cutedge)。(所謂割邊是一條刪除后使連通圖不再連通的邊)。3o.當(dāng)?shù)?步不能再執(zhí)行時(shí)，算法停止。6.3應(yīng)用6.3.1郵遞員問題中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當(dāng)然他必須經(jīng)過他負(fù)責(zé)投遞的每條街道至少一次，為他設(shè)計(jì)一條投遞路線，使得他行程最短。上述中國郵遞員問題的數(shù)學(xué)模型是：在一個(gè)賦權(quán)連通圖上求一個(gè)含所有邊的回路，且使此回路的權(quán)最小。顯然，若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。對(duì)于非Euler圖，1973年，Edmonds和Johnson給出下面的解法：設(shè)是連通賦權(quán)圖。（=1\*romani）求。（=2\*romanii）對(duì)每對(duì)頂點(diǎn)，求（是與的距離，可用Floyd算法求得）。（=3\*romaniii）構(gòu)造完全賦權(quán)圖，以為頂點(diǎn)集，以為邊的權(quán)。（=4\*romaniv）求中權(quán)之和最小的完美對(duì)集。（=5\*romanv）求中邊的端點(diǎn)之間的在中的最短軌。（=6\*romanvi）在（=5\*romanv）中求得的每條最短軌上每條邊添加一條等權(quán)的所謂“倍邊”（即共端點(diǎn)共權(quán)的邊）。（=7\*romanvii）在（=6\*romanvi）中得的圖上求Euler回路即為中國郵遞員問題的解。多郵遞員問題：郵局有位投遞員，同時(shí)投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時(shí)間最早？我們把這一問題記成kPP。kPP的數(shù)學(xué)模型如下：是連通圖，，求的回路，使得（=1\*romani），，整理為word格式整理為word格式整理為word格式（=2\*romanii），（=3\*romaniii）6.3.2旅行商（TSP）問題一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個(gè)城市恰好一次，最后返回駐地）？這個(gè)問題稱為旅行商問題。用圖論的術(shù)語說，就是在一個(gè)賦權(quán)完全圖中，找出一個(gè)有最小權(quán)的Hamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個(gè)方法以獲得相當(dāng)好（但不一定最優(yōu)）的解。一個(gè)可行的辦法是首先求一個(gè)Hamilton圈，然后適當(dāng)修改以得到具有較小權(quán)的另一個(gè)Hamilton圈。修改的方法叫做改良圈算法。設(shè)初始圈。（=1\*romani）對(duì)于，構(gòu)造新的Hamilton圈:,它是由中刪去邊和，添加邊和而得到的。若，則以代替，叫做的改良圈。（=2\*romanii）轉(zhuǎn)（=1\*romani），直至無法改進(jìn)，停止。用改良圈算法得到的結(jié)果幾乎可以肯定不是最優(yōu)的。為了得到更高的精確度，可以選擇不同的初始圈，重復(fù)進(jìn)行幾次算法，以求得較精確的結(jié)果。這個(gè)算法的優(yōu)劣程度有時(shí)能用Kruskal算法加以說明。假設(shè)是中的最優(yōu)圈。則對(duì)于任何頂點(diǎn)，是在中的Hamilton軌，因而也是的生成樹。由此推知：若是中的最優(yōu)樹，同時(shí)和是和關(guān)聯(lián)的兩條邊，并使得盡可能小，則將是的一個(gè)下界。這里介紹的方法已被進(jìn)一步發(fā)展。圈的修改過程一次替換三條邊比一次僅替換兩條邊更為有效；然而，有點(diǎn)奇怪的是，進(jìn)一步推廣這一想法，就不利了。例13從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：編寫程序如下：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;整理為word格式整理為word格式整理為word格式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);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endcircle=c1;sum=sum1;c1=[561:4];%改變初始圈，該算法的最后一個(gè)頂點(diǎn)不動(dòng)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);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endifsum1<sum整理為word格式整理為word格式整理為word格式sum=sum1;circle=c1;endcircle,sum§7最大流問題7.1最大流問題的數(shù)學(xué)描述7.1.1網(wǎng)絡(luò)中的流定義在以為節(jié)點(diǎn)集，為弧集的有向圖上定義如下的權(quán)函數(shù)：（=1\*romani）為孤上的權(quán)函數(shù)，弧對(duì)應(yīng)的權(quán)記為，稱為孤的容量下界（lowerbound）；（=2\*romanii）為弧上的權(quán)函數(shù)，弧對(duì)應(yīng)的權(quán)記為，稱為孤的容量上界，或直接稱為容量（capacity）；（=3\*romaniii）為頂點(diǎn)上的權(quán)函數(shù)，節(jié)點(diǎn)對(duì)應(yīng)的權(quán)記為，稱為頂點(diǎn)的供需量（supply／demand）；此時(shí)所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記為。由于我們只討論為有限集合的情況，所以對(duì)于弧上的權(quán)函數(shù)和頂點(diǎn)上的權(quán)函數(shù)，可以直接用所有孤上對(duì)應(yīng)的權(quán)組成的有限維向量表示，因此有時(shí)直接稱為權(quán)向量，或簡稱權(quán)。由于給定有向圖后，我們總是可以在它的弧集合和頂點(diǎn)集合上定義各種權(quán)函數(shù)，所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò)。在流網(wǎng)絡(luò)中，弧的容量下界和容量上界表示的物理意義分別是：通過該弧發(fā)送某種“物質(zhì)”時(shí)，必須發(fā)送的最小數(shù)量為，而發(fā)送的最大數(shù)量為。頂點(diǎn)對(duì)應(yīng)的供需量則表示該頂點(diǎn)從網(wǎng)絡(luò)外部獲得的“物質(zhì)”數(shù)量（時(shí)），或從該頂點(diǎn)發(fā)送到網(wǎng)絡(luò)外部的“物質(zhì)”數(shù)量（時(shí)）。下面我們給出嚴(yán)格定義。定義對(duì)于流網(wǎng)絡(luò)，其上的一個(gè)流（flow）是指從的弧集到的一個(gè)函數(shù)，即對(duì)每條弧賦予一個(gè)實(shí)數(shù)（稱為弧的流量）。如果流滿足（1），（2）則稱為可行流（feasibleflow）。至少存在一個(gè)可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasiblenetwork）．約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束?？梢?，當(dāng)時(shí)，表示有個(gè)單位的流量從該項(xiàng)點(diǎn)流出，因此頂點(diǎn)稱為供應(yīng)點(diǎn)（supplynode）或源（source），有時(shí)也形象地稱為起始點(diǎn)或發(fā)點(diǎn)等；當(dāng)整理為word格式整理為word格式整理為word格式時(shí)，表示有個(gè)單位的流量流入該點(diǎn)（或說被該頂點(diǎn)吸收），因此頂點(diǎn)稱為需求點(diǎn)（demandnode）或匯（sink），有時(shí)也形象地稱為終止點(diǎn)或收點(diǎn)等；當(dāng)時(shí)，頂點(diǎn)稱為轉(zhuǎn)運(yùn)點(diǎn)（transshipmentnode）或平衡點(diǎn)、中間點(diǎn)等。此外，根據(jù)（1）可知，對(duì)于可行網(wǎng)絡(luò)，必有（3）也就是說，所有節(jié)點(diǎn)上的供需量之和為0是網(wǎng)絡(luò)中存在可行流的必要條件。一般來說，我們總是可以把的流網(wǎng)絡(luò)轉(zhuǎn)化為的流網(wǎng)絡(luò)進(jìn)行研究。所以，除非特別說明，以后我們總是假設(shè)（即所有孤的容量下界），并將時(shí)的流網(wǎng)絡(luò)簡記為。此時(shí)，相應(yīng)的容量約束（2）為。定義在流網(wǎng)絡(luò)中，對(duì)于流，如果，則稱為零流，否則為非零流。如果某條弧上的流量等于其容量（），則稱該弧為飽和?。╯aturatedarc）；如果某條弧上的流量小于其容量（），則稱該弧為非飽和?。蝗绻硹l弧上的流量為0（），則稱該弧為空?。╲oidarc）。7.1.2最大流問題考慮如下流網(wǎng)絡(luò)：節(jié)點(diǎn)為網(wǎng)絡(luò)中唯一的源點(diǎn)，為唯一的匯點(diǎn)，而其它節(jié)點(diǎn)為轉(zhuǎn)運(yùn)點(diǎn)。如果網(wǎng)絡(luò)中存在可行流，此時(shí)稱流的流量（或流值，flowvalue）為（根據(jù)（3），它自然也等于），通常記為或，即。對(duì)這種單源單匯的網(wǎng)絡(luò)，如果我們并不給定和（即流量不給定），則網(wǎng)絡(luò)一般記為。最大流問題（maximumflowproblem）就是在中找到流值最大的可行流（即最大流）。我們將會(huì)看到，最大流問題的許多算法也可以用來求解流量給定的網(wǎng)絡(luò)中的可行流。也就是說，當(dāng)我們解決了最大流問題以后，對(duì)于在流量給定的網(wǎng)絡(luò)中尋找可行流的問題，通常也就可以解決了。因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：s.t.，（4）.（5）整理為word格式整理為word格式整理為word格式定義如果一個(gè)矩陣的任何子方陣的行列式的值都等于，或，則稱是全幺模的(totallyunimodularTU，又譯為全單位模的)，或稱是全幺模矩陣。定理8（整流定理）最大流問題所對(duì)應(yīng)的約束矩陣是全幺模矩陣。若所有弧容量均為正整數(shù)，則問題的最優(yōu)解為整數(shù)解。最大流問題是一個(gè)特殊的線性規(guī)劃問題。我們將會(huì)看到利用圖的特點(diǎn)，解決這個(gè)問題的方法較之線性規(guī)劃的一般方法要方便、直觀得多。7.1.3單源和單匯運(yùn)輸網(wǎng)絡(luò)實(shí)際問題往往是多源多匯網(wǎng)絡(luò)，為了計(jì)算的規(guī)格化，可將多源多匯網(wǎng)絡(luò)化成單源單匯網(wǎng)絡(luò)。設(shè)是的源，是的匯，具體轉(zhuǎn)化方法如下：（=1\*romani）在原圖中增加兩個(gè)新的頂點(diǎn)和，令其分別為新圖中之單源和單匯，則中所有頂點(diǎn)成為之中間頂點(diǎn)集。（=2\*romanii）用一條容量為的弧把連接到中的每個(gè)頂點(diǎn)。（=3\*romaniii）用一條容量為的弧把中的每個(gè)頂點(diǎn)連接到。和中的流以一個(gè)簡單的方式相互對(duì)應(yīng)。若是中的流，則由所定義的函數(shù)是中使得的流。反之，中的流在的弧集上的限制就是中具有相同值的流。7.2最大流和最小割關(guān)系設(shè)，，，，則稱為網(wǎng)絡(luò)的一個(gè)割，其中，為尾在，頭在的弧集，稱為割的容量。定理9是最大流，是容量最小的割的充要條件是。在網(wǎng)絡(luò)中，對(duì)于軌（此軌為無向的），若，則稱它為前向??；若，則稱它為后向弧。在網(wǎng)絡(luò)中，從到的軌上，若對(duì)所有的前向弧都有，對(duì)所有的后向弧恒有，則稱這條軌為從到的關(guān)于的可增廣軌。令，整理為word格式整理為word格式整理為word格式則在這條可增廣軌上每條前向弧的流都可以增加一個(gè)量，而相應(yīng)的后向弧的流可減少，這樣就可使得網(wǎng)絡(luò)的流量獲得增加，同時(shí)可以使每條弧的流量不超過它的容量，而且保持為正，也不影響其它弧的流量?？傊?，網(wǎng)絡(luò)中可增廣軌的存在是有意義的，因?yàn)檫@意味著不是最大流。7.3最大流的一種算法—標(biāo)號(hào)法標(biāo)號(hào)法是由Ford和Fulkerson在1957年提出的。用標(biāo)號(hào)法尋求網(wǎng)絡(luò)中最大流的基本思想是尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止。即首先給出一個(gè)初始流，這樣的流是存在的，例如零流。如果存在關(guān)于它的可增廣軌，那么調(diào)整該軌上每條弧上的流量，就可以得到新的流。對(duì)于新的流，如果仍存在可增廣軌，則用同樣的方法使流的值增大，繼續(xù)這個(gè)過程，直到網(wǎng)絡(luò)中不存在關(guān)于新得到流的可增廣軌為止，則該流就是所求的最大流。這種方法分為以下兩個(gè)過程：A.標(biāo)號(hào)過程：通過標(biāo)號(hào)過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。這兩個(gè)過程的步驟分述如下。（A）標(biāo)號(hào)過程：（=1\*romani）給發(fā)點(diǎn)標(biāo)號(hào)為。（=2\*romanii）若頂點(diǎn)已經(jīng)標(biāo)號(hào)，則對(duì)的所有未標(biāo)號(hào)的鄰接頂點(diǎn)按以下規(guī)則標(biāo)號(hào)：=1\*GB3①若，且時(shí)，令，則給頂點(diǎn)標(biāo)號(hào)為，若，則不給頂點(diǎn)標(biāo)號(hào)。=2\*GB3②，且，令，則給標(biāo)號(hào)為，若，則不給標(biāo)號(hào)。（=3\*romaniii）不斷地重復(fù)步驟（=2\*romanii）直到收點(diǎn)被標(biāo)號(hào)，或不再有頂點(diǎn)可以標(biāo)號(hào)為止。當(dāng)被標(biāo)號(hào)時(shí)，表明存在一條從到的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若點(diǎn)不能被標(biāo)號(hào)，且不存在其它可以標(biāo)號(hào)的頂點(diǎn)時(shí)，表明不存在從到的可增廣軌，算法結(jié)束，此時(shí)所獲得的流就是最大流。（B）增流過程（=1\*romani）令。（=2\*romanii）若的標(biāo)號(hào)為），則；若的標(biāo)號(hào)為，則。（=3\*romaniii）若，把全部標(biāo)號(hào)去掉，并回到標(biāo)號(hào)過程（A）。否則，令，并回到增流過程（=2\*romanii）。求網(wǎng)絡(luò)中的最大流的算法的程序設(shè)計(jì)具體步驟如下：對(duì)每個(gè)節(jié)點(diǎn)，其標(biāo)號(hào)包括兩部分信息該節(jié)點(diǎn)在可能的增廣路中的前一個(gè)節(jié)點(diǎn)，以及沿該可能的增廣路到該節(jié)點(diǎn)為止可以增廣的最大流量。整理為word格式整理為word格式整理為word格式STEP0置初始可行流（如零流）；對(duì)節(jié)點(diǎn)標(biāo)號(hào)，即令=任意正值（如1）。STEP1若，繼續(xù)下一步；否則停止，已經(jīng)得到最大流，結(jié)束。STEP2取消所有節(jié)點(diǎn)的標(biāo)號(hào)，即令，；令LIST={}，對(duì)節(jié)點(diǎn)標(biāo)號(hào)，即令充分大的正值。STEP3如果LIST且，繼續(xù)下一步；否則：（3a）如果已經(jīng)有標(biāo)號(hào)（即），則找到了一條增廣路，沿該增廣路對(duì)流進(jìn)行增廣（增廣的流量為，增廣路可以根據(jù)pred回溯方便地得到），轉(zhuǎn)STEP1。（3b）如果沒有標(biāo)號(hào)（即LIST=且），轉(zhuǎn)STEP1。STEP4從LIST中移走一個(gè)節(jié)點(diǎn)；尋找從節(jié)點(diǎn)出發(fā)的所有可能的增廣?。海?a）對(duì)非飽和前向弧，若節(jié)點(diǎn)沒有標(biāo)號(hào)（即），對(duì)進(jìn)行標(biāo)號(hào)，即令，，并將加入LIST中。（4b）對(duì)非空后向弧，若節(jié)點(diǎn)沒有標(biāo)號(hào)（即），對(duì)進(jìn)行標(biāo)號(hào)，即令，，并將加入LIST中。例14用Ford-Fulkerson算法計(jì)算如下網(wǎng)絡(luò)中的最大流，每條弧上的兩個(gè)數(shù)字分別表示容量和當(dāng)前流量。解編寫程序如下：clc,clear,M=1000;u(1,2)=1;u(1,3)=1;u(1,4)=2;u(2,3)=1;u(2,5)=2;u(3,5)=1;u(4,3)=3;u(4,5)=3;f(1,2)=1;f(1,3)=0;f(1,4)=1;f(2,3)=0;f(2,5)=1;f(3,5)=1;f(4,3)=1;f(4,5)=0;n=length(u);list=[];maxf=zeros(1:n);maxf(n)=1;整理為word格式整理為word格式整理為word格式whilemaxf(n)>0maxf=zeros(1,n);pred=zeros(1,n);list=1;record=list;maxf(1)=M;while(~isempty(list))&(maxf(n)==0)flag=list(1);list(1)=[];index1=(find(u(flag,:)~=0));label1=index1(find(u(flag,index1)...-f(flag,index1)~=0));label1=setdiff(label1,record);list=union(li