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

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

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

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

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

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

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

7、網(wǎng)絡(luò)優(yōu)化 （netwok optimization）問題。所以上面例子中介紹的問題都是網(wǎng)絡(luò)優(yōu)化問題。由于多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流（flow）為研究的對象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（network flows）或網(wǎng)絡(luò)流規(guī)劃等。下面首先簡要介紹圖與網(wǎng)絡(luò)的一些基本概念。2 圖與網(wǎng)絡(luò)的基本概念2.1 無向圖一個無向圖(undirected graph)是由一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集（vertex set）或節(jié)點集（node set）， 中的每一個元素稱為該圖的一個頂點（vertex）或節(jié)點（node）；稱為圖的邊集（edge set），中

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

9、單圖(simple graph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點。2.2 有向圖定義 一個有向圖（directed graph或 digraph）是由一個非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集或節(jié)點集， 中的每一個元素稱為該圖的一個頂點或節(jié)點；稱為圖的弧集（arc set），中的每一個元素(即中某兩個元素的有序?qū)?記為或，被稱為該圖的一條從到的?。╝rc）。當弧時，稱為的尾（tail），為的頭（head），并稱弧為的出弧（outgoing arc），為的入弧（incoming arc）。對應(yīng)于每個有向圖，可以在相同頂點集上作一個圖，使得對于的每條弧

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

11、anning subgraph，又成生成子圖）是指滿足的子圖。2.5 頂點的度設(shè)，中與關(guān)聯(lián)的邊數(shù)（每個環(huán)算作兩條邊）稱為的度(degree)，記作。若是奇數(shù)，稱是奇頂點(odd point)；是偶數(shù)，稱是偶頂點(even point)。關(guān)于頂點的度，我們有如下結(jié)果：(i) (ii) 任意一個圖的奇頂點的個數(shù)是偶數(shù)。2.6 圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法為了在計算機上實現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計算機上來描述圖與網(wǎng)絡(luò)。一般來說，算法的好壞與網(wǎng)絡(luò)的具體表示方法，以及中間結(jié)果的操作方案是有關(guān)系的。這里我們介紹計算機上用來描述圖與網(wǎng)絡(luò)的5種常

12、用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個簡單有向圖，并假設(shè)中的頂點用自然數(shù)表示或編號，中的弧用自然數(shù)表示或編號。對于有多重邊或無向網(wǎng)絡(luò)的情況，我們只是在討論完簡單有向圖的表示方法之后，給出一些說明。（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacency matrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：是一個的矩陣，即 ， 也就是說，如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應(yīng)的元素為1；否則為0?？梢钥闯觯@種表示法非常簡單、直接。但是，在鄰接矩陣的所有個元素中，只有個為非零元。如果網(wǎng)

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

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

15、我們可以把關(guān)聯(lián)矩陣增加一行，把每一條弧所對應(yīng)的權(quán)存儲在增加的行中。如果網(wǎng)絡(luò)中每條弧賦有多個權(quán)，我們可以把關(guān)聯(lián)矩陣增加相應(yīng)的行數(shù)，把每一條弧所對應(yīng)的權(quán)存儲在增加的行中。（iii）弧表示法弧表表示法將圖以弧表（arc list）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)Α；”肀硎痉ㄖ苯恿谐鏊谢〉钠瘘c和終點，共需個存儲單元，因此當網(wǎng)絡(luò)比較稀疏時比較方便。此外，對于網(wǎng)絡(luò)圖中每條弧上的權(quán)，也要對應(yīng)地用額外的存儲單元表示。例如，例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和

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

17、所示的圖，鄰接表表示為這是一個5維指針數(shù)組，每一維（上面表示法中的每一行）對應(yīng)于一個節(jié)點的鄰接表，如第1行對應(yīng)于第1個節(jié)點的鄰接表（即第1個節(jié)點的所有出弧）。每個指針單元的第1個數(shù)據(jù)域表示弧的另一個端點（弧的頭），后面的數(shù)據(jù)域表示對應(yīng)弧上的權(quán)。如第1行中的“2”表示弧的另一個端點為2（即弧為（1,2），“8”表示對應(yīng)弧(1,2)上的權(quán)為8；“3”表示弧的另一個端點為3（即弧為(1,3)），“9”表示對應(yīng)?。?，3）上的權(quán)為9。又如，第5行說明節(jié)點5出發(fā)的弧有(5,3)、(5,4)，他們對應(yīng)的權(quán)分別為6和7。對于有向圖，一般用表示節(jié)點的鄰接表，即節(jié)點的所有出弧構(gòu)成的集合或鏈表（實際上只需要列出弧

18、的另一個端點，即弧的頭）。例如上面例子，等。這種記法我們在本書后面將會經(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ā)的

19、弧的起始地址（即弧的編號）。在這種表示法中，可以快速檢索從每個節(jié)點出發(fā)的所有弧，這種星形表示法稱為前向星形（forward star）表示法。例如，在例7所示的圖中，仍然假設(shè)?。?,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)絡(luò)圖可以用前向星形表示法表示如下： 節(jié)點對應(yīng)的出弧的起始地址編號數(shù)組（記為）節(jié)點號123456起始地址134679記錄弧信息的數(shù)組弧編號12345678起點11234455終點23423534權(quán)89640367在數(shù)組中，其元素個數(shù)比圖的節(jié)點數(shù)多1（即），且一定有，。對于節(jié)點，其

20、對應(yīng)的出弧存放在弧信息數(shù)組的位置區(qū)間為，如果，則節(jié)點沒有出弧。這種表示法與弧表表示法也非常相似，“記錄弧信息的數(shù)組”實際上相當于有序存放的“弧表”。只是在前向星形表示法中，弧被編號后有序存放，并增加一個數(shù)組（）記錄每個節(jié)點出發(fā)的弧的起始編號。前向星形表示法有利于快速檢索每個節(jié)點的所有出弧，但不能快速檢索每個節(jié)點的所有入弧。為了能夠快速檢索每個節(jié)點的所有入孤，可以采用反向星形（reverse star）表示法：首先存放進入節(jié)點1的所有孤，然后接著存放進入節(jié)點2的所有弧，依此類推，最后存放進入節(jié)點的所有孤。對每條弧，仍然依次存放其起點、終點、權(quán)的數(shù)值等有關(guān)信息。同樣，為了能夠快速檢索從每個節(jié)點的所

21、有入弧，我們一般還用一個數(shù)組記錄每個節(jié)點的入孤的起始地址（即弧的編號）。例如，例7所示的圖，可以用反向星形表示法表示為如下形式：節(jié)點對應(yīng)的入弧的起始地址編號數(shù)組（記為）節(jié)點號123456起始地址113689記錄弧信息的數(shù)組弧編號12345678終點22333445起點31145524權(quán)48906763如果既希望快速檢索每個節(jié)點的所有出弧，也希望快速檢索每個節(jié)點的所有入弧，則可以綜合采用前向和反向星形表示法。當然，將孤信息存放兩次是沒有必要的，可以只用一個數(shù)組（trace）記錄一條弧在兩種表示法中的對應(yīng)關(guān)系即可。例如，可以在采用前向星形表示法的基礎(chǔ)上，加上上面介紹的數(shù)組和如下的數(shù)組即可。這相當于

22、一種緊湊的雙向星形表示法如下所示：兩種表示法中的弧的對應(yīng)關(guān)系（記為）反向法中弧編號12345678正向法中弧編號41257836對于網(wǎng)絡(luò)圖的表示法，我們作如下說明： 星形表示法和鄰接表表示法在實際算法實現(xiàn)中都是經(jīng)常采用的。星形表示法的優(yōu)點是占用的存儲空間較少，并且對那些不提供指針類型的語言（如 FORTRAN語言等）也容易實現(xiàn)。鄰接表表示法對那些提供指針類型的語言（如C語言等）是方便的，且增加或刪除一條弧所需的計算工作量很少，而這一操作在星形表示法中所需的計算工作量較大（需要花費的計算時間）。有關(guān)“計算時間”的觀念是網(wǎng)絡(luò)優(yōu)化中需要考慮的一個關(guān)鍵因素。 當網(wǎng)絡(luò)不是簡單圖，而是具有平行?。炊嘀鼗?/p>

23、）時，顯然此時鄰接矩陣表示法是不能采用的。其他方法則可以很方便地推廣到可以處理平行弧的情形。 上述方法可以很方便地推廣到可以處理無向圖的情形，但由于無向圖中邊沒有方向，因此可能需要做一些自然的修改。例如，可以在計算機中只存儲鄰接矩陣的一半信息（如上三角部分），因為此時鄰接矩陣是對稱矩陣。無向圖的關(guān)聯(lián)矩陣只含有元素0和，而不含有，因為此時不區(qū)分邊的起點和終點。又如，在鄰接表和星形表示法中，每條邊會被存儲兩次，而且反向星形表示顯然是沒有必要的，等等。2.7 軌與連通，其中，與關(guān)聯(lián)，稱是圖的一條道路(walk)，為路長，頂點和分別稱為的起點和終點，而稱為它的內(nèi)部頂點。若道路的邊互不相同，則稱為跡(t

24、rail)。若道路的頂點互不相同，則稱為軌(path)。稱一條道路是閉的，如果它有正的長且起點和終點相同。起點和終點重合的軌叫做圈(cycle)。若圖的兩個頂點間存在道路，則稱和連通(connected)。間的最短軌的長叫做間的距離。記作。若圖的任二頂點均連通，則稱是連通圖。顯然有：(i) 圖是一條軌的充要條件是是連通的，且有兩個一度的頂點，其余頂點的度為2；(ii) 圖是一個圈的充要條件是是各頂點的度均為2的連通圖。3 應(yīng)用最短路問題3.1 兩個指定頂點之間的最短路徑問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖的頂點，兩城鎮(zhèn)間的直通

25、鐵路為圖相應(yīng)兩頂點間的邊，得圖。對的每一邊，賦以一個實數(shù)直通鐵路的長度，稱為的權(quán)，得到賦權(quán)圖。的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠為順序，依次求得到的各頂點的最短路和距離，直至（或直至的所有頂點），算法結(jié)束。為避免重復(fù)并保留每一步的計算信息，采用了標號算法。下面是該算法。(i) 令，對，令，。(ii) 對每個（），用代替。計算，把達到這個最小值的一個頂點記為，令。(iii). 若，停止；若，用代替，轉(zhuǎn)(ii)。算法結(jié)

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

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(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=

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

29、的長度，。對于無向圖，是對稱矩陣，。Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列，其中表示從頂點到頂點的路徑上所經(jīng)過的頂點序號不大于的最短路徑長度。計算時用迭代公式：是迭代次數(shù)，。最后，當時，即是各頂點之間的最短通路值。例10 用Floyd算法求解例1。矩陣path用來存放每對頂點之間最短路徑上所經(jīng)過的頂點的序號。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

30、(5,:)=zeros(1,5),55;a(6,:)=zeros(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, path4 樹4.1 基本概念連通的無圈圖叫做樹，記之為。若圖滿足，則稱是的生成樹。圖連通的充分必要條件為有生成樹。一個連通圖的生成樹的個數(shù)很多，用表示的生成樹的個數(shù)，則有公式公式 (Caylay)。公式 。其中表示從上刪除邊，表示把的長度收縮為零得到的圖。樹

31、有下面常用的五個充要條件。定理1 （i）是樹當且僅當中任二頂點之間有且僅有一條軌道。（ii）是樹當且僅當無圈，且。（iii）是樹當且僅當連通，且。（iv）是樹當且僅當連通，且，不連通。（v）是樹當且僅當無圈，恰有一個圈。4.2 應(yīng)用連線問題欲修筑連接個城市的鐵路，已知城與城之間的鐵路造價為，設(shè)計一個線路圖，使總造價最低。連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。下面介紹構(gòu)造最小生成樹的兩種常用算法。4.2.1 prim算法構(gòu)造最小生成樹設(shè)置兩個集合和,其中用于存放的最小生成樹中的頂點，集合存放的最小生成樹中的邊。令集合的初值為（假設(shè)構(gòu)造最小生

32、成樹時，從頂點出發(fā)），集合的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點加入集合中，將邊加入集合中，如此不斷重復(fù)，直到時，最小生成樹構(gòu)造完畢，這時集合中包含了最小生成樹的所有邊。prim算法如下：（i），；（ii）while end例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)=

33、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);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 Kruskal算法構(gòu)造最小生成樹科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法如下

34、:(i)選，使得。(ii)若已選好，則從中選取，使得 中無圈，且 。(iii)直到選得為止。例12 用Kruskal算法構(gòu)造例3的最小生成樹。我們用存放各邊端點的信息，當選中某一邊之后，就將此邊對應(yīng)的頂點序號中較大序號改記為此邊的另一序號，同時把后面邊中所有序號為的改記為。此方法的幾何意義是：將序號的這個頂點收縮到頂點，頂點不復(fù)存在。后面繼續(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

35、(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)v2 index(find(index=v1)=v2; else index(find(index=v2)=v1; end data(:,flag)=; index(:,flag)=;endresult5 匹配問題定義 若，與無公共端點（），則稱為圖的一個對集；中的一條邊的兩個端點叫做

36、在對集中相配；中的端點稱為被許配；中每個頂點皆被許配時，稱為完美對集；中已無使的對集，則稱為最大對集；若中有一軌，其邊交替地在對集內(nèi)外出現(xiàn)，則稱此軌為的交錯軌，交錯軌的起止頂點都未被許配時，此交錯軌稱為可增廣軌。若把可增廣軌上在外的邊納入對集，把內(nèi)的邊從對集中刪除，則被許配的頂點數(shù)增加2，對集中的“對兒”增加一個。1957年，貝爾熱(Berge)得到最大對集的充要條件：定理2 是圖中的最大對集當且僅當中無可增廣軌。1935年，霍爾(Hall)得到下面的許配定理：定理3 為二分圖，與是頂點集的劃分，中存在把中頂點皆許配的對集的充要條件是，則，其中是中頂點的鄰集。由上述定理可以得出：推論1：若是（

37、正則2分圖，則有完美對集。所謂正則圖，即每頂點皆度的圖。由此推論得出下面的婚配定理：定理4 每個姑娘都結(jié)識位小伙子，每個小伙子都結(jié)識位姑娘，則每位姑娘都能和她認識的一個小伙子結(jié)婚，并且每位小伙子也能和他認識的一個姑娘結(jié)婚。人員分派問題等實際問題可以化成對集來解決。人員分派問題：工作人員去做件工作，每人適合做其中一件或幾件，問能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？這個問題的數(shù)學(xué)模型是：是二分圖，頂點集劃分為，當且僅當適合做工作時，求中的最大對集。解決這個問題可以利用1965年埃德門茲(Edmonds)提出的匈牙利算法。匈牙利算法：（i）從中任意取定一個初始對集。（ii）

38、若把中的頂點皆許配，停止，即完美對集；否則取中未被許配的一頂點，記，。（iii）若，停止，無完美對集；否則取。（iv）若是被許配的，設(shè)，轉(zhuǎn)（iii）；否則，取可增廣軌，令，轉(zhuǎn)（ii）。把以上算法稍加修改就能夠用來求二分圖的最大對集。最優(yōu)分派問題：在人員分派問題中，工作人員適合做的各項工作當中，效益未必一致，我們需要制定一個分派方案，使公司總效益最大。這個問題的數(shù)學(xué)模型是：在人員分派問題的模型中，圖的每邊加了權(quán)，表示干工作的效益，求加權(quán)圖上的權(quán)最大的完美對集。解決這個問題可以用庫恩曼克萊斯（Kuhn-Munkres）算法。為此，我們要引入可行頂點標號與相等子圖的概念。定義 若映射，滿足， ，則稱

39、是二分圖的可行頂點標號。令，稱以為邊集的的生成子圖為相等子圖，記作?？尚许旤c標號是存在的。例如 。定理5 的完美對集即為的權(quán)最大的完美對集。Kuhn-Munkres算法（i）選定初始可行頂點標號，確定，在中選取一個對集。（ii）若中頂點皆被許配，停止，即的權(quán)最大的完美對集；否則，取中未被許配的頂點，令， 。(iii)若，轉(zhuǎn)（iv）；若，取 ， ， ，。（iv）選中一頂點，若已被許配，且，則，轉(zhuǎn)（iii）；否則，取中一個可增廣軌，令，轉(zhuǎn)（ii）。其中是中的相鄰頂點集。6 Euler圖和Hamilton圖6.1 基本概念定義 經(jīng)過的每條邊的跡叫做的Euler跡；閉的Euler跡叫做Euler回路或

40、回路；含Euler回路的圖叫做Euler圖。直觀地講，Euler圖就是從一頂點出發(fā)每邊恰通過一次能回到出發(fā)點的那種圖，即不重復(fù)地行遍所有的邊再回到出發(fā)點。定理7 （i）是Euler圖的充分必要條件是連通且每頂點皆偶次。（ii）是Euler圖的充分必要條件是連通且，是圈，。（iii）中有Euler跡的充要條件是連通且至多有兩個奇次點。定義 包含的每個頂點的軌叫做Hamilton(哈密頓)軌；閉的Hamilton軌叫做Hamilton圈或圈；含Hamilton圈的圖叫做Hamilton圖。直觀地講，Hamilton圖就是從一頂點出發(fā)每頂點恰通過一次能回到出發(fā)點的那種圖，即不重復(fù)地行遍所有的頂點再回

41、到出發(fā)點。6.2 Euler回路的Fleury算法1921年，F(xiàn)leury給出下面的求Euler回路的算法。Fleury算法：1o. ，令。2o. 假設(shè)跡已經(jīng)選定，那么按下述方法從中選取邊：（i）和相關(guān)聯(lián)；（ii）除非沒有別的邊可選擇，否則不是的割邊(cut edge)。(所謂割邊是一條刪除后使連通圖不再連通的邊)。3o. 當?shù)?步不能再執(zhí)行時，算法停止。6.3 應(yīng)用6.3.1 郵遞員問題中國郵遞員問題一位郵遞員從郵局選好郵件去投遞，然后返回郵局，當然他必須經(jīng)過他負責(zé)投遞的每條街道至少一次，為他設(shè)計一條投遞路線，使得他行程最短。上述中國郵遞員問題的數(shù)學(xué)模型是：在一個賦權(quán)連通圖上求一個含所有邊的

42、回路，且使此回路的權(quán)最小。顯然，若此連通賦權(quán)圖是Euler圖，則可用Fleury算法求Euler回路，此回路即為所求。對于非Euler圖，1973年，Edmonds和Johnson給出下面的解法：設(shè)是連通賦權(quán)圖。（i）求。（ii）對每對頂點，求（是與的距離，可用Floyd算法求得）。（iii）構(gòu)造完全賦權(quán)圖，以為頂點集，以為邊的權(quán)。（iv）求中權(quán)之和最小的完美對集。（v）求中邊的端點之間的在中的最短軌。（vi）在（v）中求得的每條最短軌上每條邊添加一條等權(quán)的所謂“倍邊”（即共端點共權(quán)的邊）。（vii）在（vi）中得的圖上求Euler回路即為中國郵遞員問題的解。多郵遞員問題：郵局有位投遞員，同時

43、投遞信件，全城街道都要投遞，完成任務(wù)返回郵局，如何分配投遞路線，使得完成投遞任務(wù)的時間最早？我們把這一問題記成kPP。kPP的數(shù)學(xué)模型如下：是連通圖，求的回路，使得（i），（ii），（iii）6.3.2 旅行商（TSP）問題一名推銷員準備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設(shè)計一條最短的旅行路線（從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）？這個問題稱為旅行商問題。用圖論的術(shù)語說，就是在一個賦權(quán)完全圖中，找出一個有最小權(quán)的Hamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅行商問題的有效算法。所以希望有一個方法以獲得相當好（但不一定最優(yōu)）的解。一

44、個可行的辦法是首先求一個Hamilton圈，然后適當修改以得到具有較小權(quán)的另一個Hamilton圈。修改的方法叫做改良圈算法。設(shè)初始圈。（i）對于，構(gòu)造新的Hamilton圈: ,它是由中刪去邊和，添加邊和而得到的。若，則以代替，叫做的改良圈。（ii）轉(zhuǎn)（i），直至無法改進，停止。用改良圈算法得到的結(jié)果幾乎可以肯定不是最優(yōu)的。為了得到更高的精確度，可以選擇不同的初始圈，重復(fù)進行幾次算法，以求得較精確的結(jié)果。這個算法的優(yōu)劣程度有時能用Kruskal算法加以說明。假設(shè)是中的最優(yōu)圈。則對于任何頂點，是在中的Hamilton軌，因而也是的生成樹。由此推知：若是中的最優(yōu)樹，同時和是和關(guān)聯(lián)的兩條邊，并使得

45、盡可能小，則將是的一個下界。這里介紹的方法已被進一步發(fā)展。圈的修改過程一次替換三條邊比一次僅替換兩條邊更為有效；然而，有點奇怪的是，進一步推廣這一想法，就不利了。例13 從北京（Pe）乘飛機到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：編寫程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;

46、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=5 1:4 6;L=length(c1);flag=1;while flag0 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)0 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a

47、(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 sum1sum sum=sum1; circle=c1;endcircle,sum7 最大流問題7.1 最大流問題的數(shù)學(xué)描述7.1.1 網(wǎng)絡(luò)中的流 定義 在以為節(jié)點集，為弧集的有向圖上定義如下的權(quán)函數(shù)：（i）為孤上的權(quán)函數(shù)，弧對應(yīng)的權(quán)記為，稱為孤的容量下界（lower bound）；（ii）為弧上的權(quán)函數(shù)

48、，弧對應(yīng)的權(quán)記為，稱為孤的容量上界，或直接稱為容量（capacity）；（iii）為頂點上的權(quán)函數(shù)，節(jié)點對應(yīng)的權(quán)記為，稱為頂點的供需量（supplydemand）；此時所構(gòu)成的網(wǎng)絡(luò)稱為流網(wǎng)絡(luò)，可以記為。 由于我們只討論為有限集合的情況，所以對于弧上的權(quán)函數(shù)和頂點上的權(quán)函數(shù)，可以直接用所有孤上對應(yīng)的權(quán)組成的有限維向量表示，因此有時直接稱為權(quán)向量，或簡稱權(quán)。由于給定有向圖后，我們總是可以在它的弧集合和頂點集合上定義各種權(quán)函數(shù)，所以流網(wǎng)絡(luò)一般也直接簡稱為網(wǎng)絡(luò)。 在流網(wǎng)絡(luò)中，弧的容量下界和容量上界表示的物理意義分別是：通過該弧發(fā)送某種“物質(zhì)”時，必須發(fā)送的最小數(shù)量為，而發(fā)送的最大數(shù)量為。頂點對應(yīng)的供需

49、量則表示該頂點從網(wǎng)絡(luò)外部獲得的“物質(zhì)”數(shù)量（時），或從該頂點發(fā)送到網(wǎng)絡(luò)外部的“物質(zhì)”數(shù)量（時）。下面我們給出嚴格定義。 定義 對于流網(wǎng)絡(luò)，其上的一個流（flow）是指從的弧集到的一個函數(shù)，即對每條弧賦予一個實數(shù)（稱為弧的流量）。如果流滿足 （1）， （2）則稱為可行流（feasible flow）。至少存在一個可行流的流網(wǎng)絡(luò)稱為可行網(wǎng)絡(luò)（feasible network）約束（1）稱為流量守恒條件（也稱流量平衡條件），約束（2）稱為容量約束。 可見，當時，表示有個單位的流量從該項點流出，因此頂點稱為供應(yīng)點（supply node）或源（source），有時也形象地稱為起始點或發(fā)點等；當時，表示

50、有個單位的流量流入該點（或說被該頂點吸收），因此頂點稱為需求點（demand node）或匯（sink），有時也形象地稱為終止點或收點等；當時，頂點稱為轉(zhuǎn)運點（transshipment node）或平衡點、中間點等。此外，根據(jù)（1）可知，對于可行網(wǎng)絡(luò)，必有 （3）也就是說，所有節(jié)點上的供需量之和為0是網(wǎng)絡(luò)中存在可行流的必要條件。 一般來說，我們總是可以把的流網(wǎng)絡(luò)轉(zhuǎn)化為的流網(wǎng)絡(luò)進行研究。所以，除非特別說明，以后我們總是假設(shè)（即所有孤的容量下界），并將時的流網(wǎng)絡(luò)簡記為。此時，相應(yīng)的容量約束（2）為 。定義 在流網(wǎng)絡(luò)中，對于流，如果 ，則稱為零流，否則為非零流。如果某條弧上的流量等于其容量（），則

51、稱該弧為飽和?。╯aturated arc）；如果某條弧上的流量小于其容量（），則稱該弧為非飽和??；如果某條弧上的流量為 0（），則稱該弧為空弧（void arc）。7.1.2 最大流問題考慮如下流網(wǎng)絡(luò)：節(jié)點為網(wǎng)絡(luò)中唯一的源點，為唯一的匯點，而其它節(jié)點為轉(zhuǎn)運點。如果網(wǎng)絡(luò)中存在可行流，此時稱流的流量（或流值，flow value）為（根據(jù)（3），它自然也等于），通常記為或，即 。對這種單源單匯的網(wǎng)絡(luò)，如果我們并不給定和（即流量不給定），則網(wǎng)絡(luò)一般記為。最大流問題（maximum flow problem）就是在中找到流值最大的可行流（即最大流）。我們將會看到，最大流問題的許多算法也可以用來求解流量給定的網(wǎng)絡(luò)中的可行流。也就是說，當我們解決了最大流問題以后，對于在流量給定的網(wǎng)絡(luò)中尋找可行流的問題，通常也就可以解決了。因此，用線性規(guī)劃的方法，最大流問題可以形式地描述如下：s.t. ， （4） . （5）定義 如果一個矩陣的任何子方陣的行列式的值都等于，或，則稱是全幺模的(totally unimodular TU，又譯為全單位模的)，或稱是全幺模矩陣。定理8（整流定理）