圖論數(shù)學(xué)建模課件

圖論山東建筑大學(xué)賀長偉圖論山東建筑大學(xué)1引言

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點(diǎn)。

1引言

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)圖論數(shù)學(xué)建模課件

當(dāng)然可以通過試驗(yàn)去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個問題，采用了建立數(shù)學(xué)模型的方法。他將每一塊陸地用一個點(diǎn)來代替，將每一座橋用連接相應(yīng)兩點(diǎn)的一條線來代替，從而得到一個有四個“點(diǎn)”，七條“線”的“圖”。問題成為從任一點(diǎn)出發(fā)一筆畫出七條線再回到起點(diǎn)。歐拉考察了一般一筆畫的結(jié)構(gòu)特點(diǎn)，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點(diǎn)都與偶數(shù)線相關(guān)聯(lián)，將這個判定法則應(yīng)用于七橋問題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。當(dāng)然可以通過試驗(yàn)去嘗試解決這個問題，但該城居民的

我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題。例1最短路問題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達(dá)另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題。例3指派問題（assignmentproblem）

一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，

每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員

工去完成同一項(xiàng)任務(wù)時所獲得的回報是不同的。

如何分配工作方案可以使總回報最大？

例4中國郵遞員問題（CPP－chinesepostman

problem）

一名郵遞員負(fù)責(zé)投遞某個街區(qū)的郵件。如何為他

（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，

經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）

？由于這一問題是我國管梅谷教授1960年首先

提的，所以國際上稱之為中國郵遞員問題。例3指派問題（assignmentproblem）

例5運(yùn)輸問題（transportationproblem）某種原材料有個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個使用這些原材料的工廠。假定個產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？上述問題有兩個共同的特點(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）問題。例5運(yùn)輸問題（transportationproble2圖與網(wǎng)絡(luò)的基本概念

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

記為或，被稱為該圖的一條從到的邊（edge）2圖與網(wǎng)絡(luò)的基本概念2.1無向圖一個圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有限。圖的頂點(diǎn)數(shù)用符號或表示，邊數(shù)用或表示。當(dāng)討論的圖只有一個時，總是用G來表示這個圖。從而在圖論符號中我們常略去字母G，例如:分別用代替。端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點(diǎn)。一個圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有2.2有向圖定義一個有向圖（directedgraph或digraph）G是由一個非空有限集合V和V中某些元素的有序?qū)蠘?gòu)成的二元組，記為其中稱為圖的頂點(diǎn)集或節(jié)點(diǎn)集

.

稱為圖的弧集（arcset），A中的每一個元素(即中某兩個元素的有序?qū)?

記為或，

當(dāng)弧

時，

稱為尾（tail），為頭（head）.2.2有向圖2.3完全圖、二分圖每一對不同的頂點(diǎn)都有一條邊相連的簡單圖稱為完全圖(completegraph)。n個頂點(diǎn)的完全圖記為。若，，（這里表示集合X中的元素個數(shù)），X中無相鄰頂點(diǎn)對，Y中亦然，則稱G為二分圖(bipartitegraph)；特別地，若，則，則稱G為完全二分圖，記成。

2.3完全圖、二分圖2.4子圖如果,,圖H叫做圖G的子圖（subgraph），記作。若H是G的子圖，則G稱為H的母圖。2.5頂點(diǎn)的度設(shè)，G中與v關(guān)聯(lián)的邊數(shù)（每個環(huán)算作兩條邊）稱為v的度(degree)，記作。若是奇數(shù)，稱v是奇頂點(diǎn)(oddpoint)；若是偶數(shù)，稱v是偶頂點(diǎn)(evenpoint)。關(guān)于頂點(diǎn)的度，我們有如下結(jié)果：(i)(ii)任意一個圖的奇頂點(diǎn)的個數(shù)是偶數(shù)。2.4子圖2.6圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法．為了在計算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計算機(jī)上來描述圖與網(wǎng)絡(luò)。這里我們介紹計算機(jī)上用來描述圖與網(wǎng)絡(luò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個簡單有向圖，，并假設(shè)V中的頂點(diǎn)用自然數(shù)1,2,…n表示或編號，A中的弧用自然數(shù)1,2,…m表示或編號。

2.6圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲在計算機(jī)中。圖的鄰接矩陣是如下定義的：C是一個n*n的0-1矩陣，即也就是說，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對應(yīng)的元素為1；否則為0。

（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adja例1對于所示的圖，可以用鄰接矩陣表示為同樣，對于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個矩陣表示這些權(quán)。例1對于所示的圖，可以用鄰接矩陣表示為（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲在計算機(jī)中．圖的關(guān)聯(lián)矩陣B是如下定義的：B是一個n*m的矩陣，即（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（inc如果一個節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點(diǎn)是一條弧的終點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為-1；如果一個節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為0。例2對于例1所示的圖，如果關(guān)聯(lián)矩陣中每列對應(yīng)弧的順序?yàn)?1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為（列單位為?。?/p>

如果一個節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果（iii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲在計算機(jī)中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)Α＠?，假設(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（iii）弧表示法弧表表示法將圖以弧表（arclist）的（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲在計算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對每個節(jié)點(diǎn)，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點(diǎn)，用一個單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有弧，鏈表中每個單元對應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個單元除列出弧的另一個端點(diǎn)外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。

（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacen

對于有向圖，一般用表示節(jié)點(diǎn)的鄰接表，即節(jié)點(diǎn)的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個端點(diǎn)，即弧的頭）。例如上面例子，，等。對于有向圖，一般用（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示。

記錄弧信息的數(shù)組弧編號12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367（v）星形表示法星形（star）表示法的思想與鄰接表表示法的§3應(yīng)用—最短路問題3.1兩個指定頂點(diǎn)之間的最短路徑問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點(diǎn)間的邊，得圖G。對G的每一邊e，賦以一個實(shí)數(shù)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖G的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點(diǎn)間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作?！?應(yīng)用—最短路問題3.1兩個指定頂點(diǎn)之間的最短路徑求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到的G各頂點(diǎn)的最短路和距離，直至（或直至的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計算信息，采用了標(biāo)號算法。下面是該算法。令，對令，，。(ii)對每個,用代替計算，把達(dá)到這個最小值的一個頂點(diǎn)記為，令。(iii)若，停止；若，用i+1代替

i，轉(zhuǎn)(ii)。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）找出u0到其他各點(diǎn)的最短路徑找出u0到其他各點(diǎn)的最短路徑圖論數(shù)學(xué)建模課件3.2每對頂點(diǎn)之間的最短路徑計算賦權(quán)圖中各對頂點(diǎn)之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到從每一個頂點(diǎn)到其它頂點(diǎn)的最短路徑。第二種解決這一問題的方法是由FloydRW提出的算法，稱之為Floyd算法。

3.2每對頂點(diǎn)之間的最短路徑計算賦權(quán)圖中各對頂點(diǎn)之間最短路假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中：；之間沒有邊，在程序中以各邊都不可能達(dá)到的充分大的數(shù)代替；是i,j之間邊的長度，。假設(shè)圖權(quán)的鄰接矩陣為，F(xiàn)loyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列，其中表示從頂點(diǎn)到頂點(diǎn)的路徑上所經(jīng)過的頂點(diǎn)序號不大于k

的最短路徑長度。計算時用迭代公式：

k是迭代次數(shù)，。最后，當(dāng)k=n時，即是各頂點(diǎn)之間的最短通路值。

(例題見附件)Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列§4樹

4.1基本概念連通的無圈圖叫做樹，記之為T。4.2應(yīng)用—連線問題欲修筑連接n個城市的鐵路，已知城與城之間的鐵路造價為，設(shè)計一個線路圖，使總造價最低。連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。

§4樹

4.1基本概念定理設(shè)G是具有n個頂點(diǎn)的圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最最小連通圖）；6)G中任意兩頂點(diǎn)間有唯一一條路.定理設(shè)G是具有n個頂點(diǎn)的圖，則下述命題等價：1)G是樹找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法B破圈法找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法A避圈法

這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種方法可稱為“避圈法”或“加邊法”

在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.A避圈法這種方法就是在已給的圖G中，每步a)深探法

若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號為步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)若某點(diǎn)v已得標(biāo)號，檢端是否均已標(biāo)號.

若有邊vw之w未標(biāo)號,則給w代v，重復(fù)ii).i-1的r點(diǎn),以r代v,重復(fù)ii),直到全部點(diǎn)得到標(biāo)號為止.給以標(biāo)號0.查一端點(diǎn)為v的各邊，另一w以標(biāo)號i+1，記下邊vw.令012345678910111213例用深探法求出下圖10的一棵生成樹

a)深探法若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所有標(biāo)號i的點(diǎn)集為是否均已標(biāo)號.對所有未標(biāo)號之點(diǎn)均標(biāo)以i+1,記下這些iii)對標(biāo)號i+1的點(diǎn)重復(fù)步步驟ii)，直到全部點(diǎn)得到給u以標(biāo)號0.Vi,檢查[Vi,V\Vi]中的邊端點(diǎn)邊.例用廣探法求出下圖10的一棵生成樹

標(biāo)號為止.圖1031012213212234b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所B破圈法

相對于避圈法，還有一種求生成樹的方法叫做“破圈法”.這種方法就是在圖G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟直到圖G中沒有圈為止.例用破圈法求出下圖的一棵生成樹.圖的生成樹不是唯一的.B破圈法相對于避圈法，還有一種求生成樹的方法叫做AKruskal算法（或避圈法）步驟如下：1)選擇邊e1，使得w(e1)盡可能??；2)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)

是滿足i)的盡可能小的權(quán)，3)當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.最小生成樹與算法AKruskal算法（或避圈法）步驟如下：1)選擇例用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條

在中選取權(quán)值最小的邊中權(quán)值最小邊有,從中選任取一條邊會與已選邊構(gòu)成圈,故停止,得中選取在中選取

中選取.但與都例用Kruskal算法求下圖的最小樹.在左圖中B破圈法算法2

步驟如下：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中

立即生成一個圈.去掉此

圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余的弦，直到全部弦檢查完畢為止.例用破圈法求下圖的最小樹.B破圈法算法2步驟如下：1)從圖G中任選一棵樹T1.prim算法構(gòu)造最小生成樹設(shè)置兩個集合P和Q,其中P用于存放的最小生成樹G中的頂點(diǎn)，集合Q存放的最小生成樹G中的邊。令集合P的初值為（假設(shè)構(gòu)造最小生成樹時，從頂點(diǎn)出發(fā)），集合Q的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點(diǎn)v加入集合P中，將邊pv加入集合Q中，如此不斷重復(fù)，直到P=V時，最小生成樹構(gòu)造完畢，這時集合Q中包含了最小生成樹的所有邊。prim算法構(gòu)造最小生成樹例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)-1result=

temp=a(p,tb);temp=temp(:);

125447

d=min(temp);254673

[jb,kb]=find(a(p,tb)==d);504050304245

j=p(jb(1));k=tb(kb(1));result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];endresult例11用prim算法求右圖的最小生成樹。例從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113例從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(解：編寫程序如下：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);endendendend解：編寫程序如下：sum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1));endcircle=c1;sum=sum1;c1=[561:4];%改變初始圈，該算法的最后一個頂點(diǎn)不動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<sumsum=sum1;circle=c1;endcircle,sumsum1=0;圖論山東建筑大學(xué)賀長偉圖論山東建筑大學(xué)1引言

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)學(xué)家歐拉于1736年發(fā)表的“哥尼斯堡的七座橋”。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如果我們用點(diǎn)表示這些具體事物，用連接兩點(diǎn)的線段（直的或曲的）表示兩個事物的特定的聯(lián)系，就得到了描述這個“圖”的幾何形象。圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解。哥尼斯堡七橋問題就是一個典型的例子。在哥尼斯堡有七座橋?qū)⑵杖R格爾河中的兩個島及島與河岸聯(lián)結(jié)起來。問題是要從這四塊陸地中的任何一塊開始通過每一座橋正好一次，再回到起點(diǎn)。

1引言

圖論起源于18世紀(jì)。第一篇圖論論文是瑞士數(shù)圖論數(shù)學(xué)建模課件

當(dāng)然可以通過試驗(yàn)去嘗試解決這個問題，但該城居民的任何嘗試均未成功。歐拉為了解決這個問題，采用了建立數(shù)學(xué)模型的方法。他將每一塊陸地用一個點(diǎn)來代替，將每一座橋用連接相應(yīng)兩點(diǎn)的一條線來代替，從而得到一個有四個“點(diǎn)”，七條“線”的“圖”。問題成為從任一點(diǎn)出發(fā)一筆畫出七條線再回到起點(diǎn)。歐拉考察了一般一筆畫的結(jié)構(gòu)特點(diǎn)，給出了一筆畫的一個判定法則：這個圖是連通的，且每個點(diǎn)都與偶數(shù)線相關(guān)聯(lián)，將這個判定法則應(yīng)用于七橋問題，得到了“不可能走通”的結(jié)果，不但徹底解決了這個問題，而且開創(chuàng)了圖論研究的先河。當(dāng)然可以通過試驗(yàn)去嘗試解決這個問題，但該城居民的

我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題。例1最短路問題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2公路連接問題某一地區(qū)有若干個主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經(jīng)高速公路直接或間接到達(dá)另一個城市。假定已經(jīng)知道了任意兩個城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？我們首先通過一些例子來了解網(wǎng)絡(luò)優(yōu)化問題。例3指派問題（assignmentproblem）

一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，

每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員

工去完成同一項(xiàng)任務(wù)時所獲得的回報是不同的。

如何分配工作方案可以使總回報最大？

例4中國郵遞員問題（CPP－chinesepostman

problem）

一名郵遞員負(fù)責(zé)投遞某個街區(qū)的郵件。如何為他

（她）設(shè)計一條最短的投遞路線（從郵局出發(fā)，

經(jīng)過投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）

？由于這一問題是我國管梅谷教授1960年首先

提的，所以國際上稱之為中國郵遞員問題。例3指派問題（assignmentproblem）

例5運(yùn)輸問題（transportationproblem）某種原材料有個產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個使用這些原材料的工廠。假定個產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？上述問題有兩個共同的特點(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）問題。例5運(yùn)輸問題（transportationproble2圖與網(wǎng)絡(luò)的基本概念

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

記為或，被稱為該圖的一條從到的邊（edge）2圖與網(wǎng)絡(luò)的基本概念2.1無向圖一個圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有限。圖的頂點(diǎn)數(shù)用符號或表示，邊數(shù)用或表示。當(dāng)討論的圖只有一個時，總是用G來表示這個圖。從而在圖論符號中我們常略去字母G，例如:分別用代替。端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點(diǎn)。一個圖稱為有限圖，如果它的頂點(diǎn)集和邊集都有2.2有向圖定義一個有向圖（directedgraph或digraph）G是由一個非空有限集合V和V中某些元素的有序?qū)蠘?gòu)成的二元組，記為其中稱為圖的頂點(diǎn)集或節(jié)點(diǎn)集

.

稱為圖的弧集（arcset），A中的每一個元素(即中某兩個元素的有序?qū)?

記為或，

當(dāng)弧

時，

稱為尾（tail），為頭（head）.2.2有向圖2.3完全圖、二分圖每一對不同的頂點(diǎn)都有一條邊相連的簡單圖稱為完全圖(completegraph)。n個頂點(diǎn)的完全圖記為。若，，（這里表示集合X中的元素個數(shù)），X中無相鄰頂點(diǎn)對，Y中亦然，則稱G為二分圖(bipartitegraph)；特別地，若，則，則稱G為完全二分圖，記成。

2.3完全圖、二分圖2.4子圖如果,,圖H叫做圖G的子圖（subgraph），記作。若H是G的子圖，則G稱為H的母圖。2.5頂點(diǎn)的度設(shè)，G中與v關(guān)聯(lián)的邊數(shù)（每個環(huán)算作兩條邊）稱為v的度(degree)，記作。若是奇數(shù)，稱v是奇頂點(diǎn)(oddpoint)；若是偶數(shù)，稱v是偶頂點(diǎn)(evenpoint)。關(guān)于頂點(diǎn)的度，我們有如下結(jié)果：(i)(ii)任意一個圖的奇頂點(diǎn)的個數(shù)是偶數(shù)。2.4子圖2.6圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模型與算法．為了在計算機(jī)上實(shí)現(xiàn)網(wǎng)絡(luò)優(yōu)化的算法，首先我們必須有一種方法（即數(shù)據(jù)結(jié)構(gòu)）在計算機(jī)上來描述圖與網(wǎng)絡(luò)。這里我們介紹計算機(jī)上用來描述圖與網(wǎng)絡(luò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個簡單有向圖，，并假設(shè)V中的頂點(diǎn)用自然數(shù)1,2,…n表示或編號，A中的弧用自然數(shù)1,2,…m表示或編號。

2.6圖與網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)網(wǎng)絡(luò)優(yōu)化研究的是網(wǎng)絡(luò)上的各種優(yōu)化模（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲在計算機(jī)中。圖的鄰接矩陣是如下定義的：C是一個n*n的0-1矩陣，即也就是說，如果兩節(jié)點(diǎn)之間有一條弧，則鄰接矩陣中對應(yīng)的元素為1；否則為0。

（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adja例1對于所示的圖，可以用鄰接矩陣表示為同樣，對于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個矩陣表示這些權(quán)。例1對于所示的圖，可以用鄰接矩陣表示為（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲在計算機(jī)中．圖的關(guān)聯(lián)矩陣B是如下定義的：B是一個n*m的矩陣，即（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（inc如果一個節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點(diǎn)是一條弧的終點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為-1；如果一個節(jié)點(diǎn)與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為0。例2對于例1所示的圖，如果關(guān)聯(lián)矩陣中每列對應(yīng)弧的順序?yàn)?1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，則關(guān)聯(lián)矩陣表示為（列單位為?。?/p>

如果一個節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果（iii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲在計算機(jī)中。所謂圖的弧表，也就是圖的弧集合中的所有有序?qū)?。?，假設(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（iii）弧表示法弧表表示法將圖以弧表（arclist）的（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲在計算機(jī)中。所謂圖的鄰接表，也就是圖的所有節(jié)點(diǎn)的鄰接表的集合；而對每個節(jié)點(diǎn)，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點(diǎn)，用一個單向鏈表列出從該節(jié)點(diǎn)出發(fā)的所有弧，鏈表中每個單元對應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個單元除列出弧的另一個端點(diǎn)外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。

（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacen

對于有向圖，一般用表示節(jié)點(diǎn)的鄰接表，即節(jié)點(diǎn)的所有出弧構(gòu)成的集合或鏈表（實(shí)際上只需要列出弧的另一個端點(diǎn)，即弧的頭）。例如上面例子，，等。對于有向圖，一般用（v）星形表示法星形（star）表示法的思想與鄰接表表示法的思想有一定的相似之處。對每個節(jié)點(diǎn)，它也是記錄從該節(jié)點(diǎn)出發(fā)的所有弧，但它不是采用單向鏈表而是采用一個單一的數(shù)組表示。

記錄弧信息的數(shù)組弧編號12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)89640367（v）星形表示法星形（star）表示法的思想與鄰接表表示法的§3應(yīng)用—最短路問題3.1兩個指定頂點(diǎn)之間的最短路徑問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩頂點(diǎn)間的邊，得圖G。對G的每一邊e，賦以一個實(shí)數(shù)—直通鐵路的長度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖G的各邊的權(quán)和。問題就是求賦權(quán)圖中指定的兩個頂點(diǎn)間的具最小權(quán)的軌。這條軌叫做間的最短路，它的權(quán)叫做間的距離，亦記作?！?應(yīng)用—最短路問題3.1兩個指定頂點(diǎn)之間的最短路徑求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到的G各頂點(diǎn)的最短路和距離，直至（或直至的所有頂點(diǎn)），算法結(jié)束。為避免重復(fù)并保留每一步的計算信息，采用了標(biāo)號算法。下面是該算法。令，對令，，。(ii)對每個,用代替計算，把達(dá)到這個最小值的一個頂點(diǎn)記為，令。(iii)若，停止；若，用i+1代替

i，轉(zhuǎn)(ii)。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）找出u0到其他各點(diǎn)的最短路徑找出u0到其他各點(diǎn)的最短路徑圖論數(shù)學(xué)建模課件3.2每對頂點(diǎn)之間的最短路徑計算賦權(quán)圖中各對頂點(diǎn)之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到從每一個頂點(diǎn)到其它頂點(diǎn)的最短路徑。第二種解決這一問題的方法是由FloydRW提出的算法，稱之為Floyd算法。

3.2每對頂點(diǎn)之間的最短路徑計算賦權(quán)圖中各對頂點(diǎn)之間最短路假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中：；之間沒有邊，在程序中以各邊都不可能達(dá)到的充分大的數(shù)代替；是i,j之間邊的長度，。假設(shè)圖權(quán)的鄰接矩陣為，F(xiàn)loyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列，其中表示從頂點(diǎn)到頂點(diǎn)的路徑上所經(jīng)過的頂點(diǎn)序號不大于k

的最短路徑長度。計算時用迭代公式：

k是迭代次數(shù)，。最后，當(dāng)k=n時，即是各頂點(diǎn)之間的最短通路值。

(例題見附件)Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列§4樹

4.1基本概念連通的無圈圖叫做樹，記之為T。4.2應(yīng)用—連線問題欲修筑連接n個城市的鐵路，已知城與城之間的鐵路造價為，設(shè)計一個線路圖，使總造價最低。連線問題的數(shù)學(xué)模型是在連通賦權(quán)圖上求權(quán)最小的生成樹。賦權(quán)圖的具有最小權(quán)的生成樹叫做最小生成樹。

§4樹

4.1基本概念定理設(shè)G是具有n個頂點(diǎn)的圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最最小連通圖）；6)G中任意兩頂點(diǎn)間有唯一一條路.定理設(shè)G是具有n個頂點(diǎn)的圖，則下述命題等價：1)G是樹找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法B破圈法找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法A避圈法

這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種方法可稱為“避圈法”或“加邊法”

在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.A避圈法這種方法就是在已給的圖G中，每步a)深探法

若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號為步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)若某點(diǎn)v已得標(biāo)號，檢端是否均已標(biāo)號.

若有邊vw之w未標(biāo)號,則給w代v，重復(fù)ii).i-1的r點(diǎn),以r代v,重復(fù)ii),直到全部點(diǎn)得到標(biāo)號為止.給以標(biāo)號0.查一端點(diǎn)為v的各邊，另一w以標(biāo)號i+1，記下邊vw.令012345678910111213例用深探法求出下圖10的一棵生成樹

a)深探法若這樣的邊的另一端均已有標(biāo)號，就退到標(biāo)號b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所有標(biāo)號i的點(diǎn)集為是否均已標(biāo)號.對所有未標(biāo)號之點(diǎn)均標(biāo)以i+1,記下這些iii)對標(biāo)號i+1的點(diǎn)重復(fù)步步驟ii)，直到全部點(diǎn)得到給u以標(biāo)號0.Vi,檢查[Vi,V\Vi]中的邊端點(diǎn)邊.例用廣探法求出下圖10的一棵生成樹

標(biāo)號為止.圖1031012213212234b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所B破圈法

相對于避圈法，還有一種求生成樹的方法叫做“破圈法”.這種方法就是在圖G中任取一個圈，任意舍棄一條邊，將這個圈破掉，重復(fù)這個步驟直到圖G中沒有圈為止.例用破圈法求出下圖的一棵生成樹.圖的生成樹不是唯一的.B破圈法相對于避圈法，還有一種求生成樹的方法叫做AKruskal算法（或避圈法）步驟如下：1)選擇邊e1，使得w(e1)盡可能??；2)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)

是滿足i)的盡可能小的權(quán)，3)當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.最小生成樹與算法AKruskal算法（或避圈法）步驟如下：1)選擇例用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條

在中選取權(quán)值最小的邊中權(quán)值最小邊有,從中選任取一條邊會與已選邊構(gòu)成圈,故停止,得中選取在中選取

中選取.但與都例用Kruskal算法求下圖的最小樹.在左圖中B破圈法算法2

步驟如下：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中

立即生成一個圈.去掉此

圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余的弦，直到全部弦檢查完畢為止.例用破圈法求下圖的最小樹.B破圈法算法2步驟如下：1)從圖G中任選一棵樹T1.prim算法構(gòu)造最小生成樹設(shè)置兩個集合P和Q,其中P用于存放的最小生成樹G中的頂點(diǎn)，集合Q