圖論數(shù)學建模

圖論數(shù)學建模第一頁，共四十三頁，2022年，8月28日1引言

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

第二頁，共四十三頁，2022年，8月28日第三頁，共四十三頁，2022年，8月28日

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

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

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

每人一項。由于各員工的特點不同，不同的員

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

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

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

problem）

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

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

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

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

提的，所以國際上稱之為中國郵遞員問題。第六頁，共四十三頁，2022年，8月28日例5運輸問題（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)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化（netwokoptimization）問題。第七頁，共四十三頁，2022年，8月28日2圖與網(wǎng)絡(luò)的基本概念

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

記為或，被稱為該圖的一條從到的邊（edge）第八頁，共四十三頁，2022年，8月28日一個圖稱為有限圖，如果它的頂點集和邊集都有限。圖的頂點數(shù)用符號或表示，邊數(shù)用或表示。當討論的圖只有一個時，總是用G來表示這個圖。從而在圖論符號中我們常略去字母G，例如:分別用代替。端點重合為一點的邊稱為環(huán)(loop)。一個圖稱為簡單圖(simplegraph)，如果它既沒有環(huán)也沒有兩條邊連接同一對頂點。第九頁，共四十三頁，2022年，8月28日2.2有向圖定義一個有向圖（directedgraph或digraph）G是由一個非空有限集合V和V中某些元素的有序?qū)蠘?gòu)成的二元組，記為其中稱為圖的頂點集或節(jié)點集

.

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

記為或，當弧時，稱為尾（tail），為頭（head）.第十頁，共四十三頁，2022年，8月28日2.3完全圖、二分圖每一對不同的頂點都有一條邊相連的簡單圖稱為完全圖(completegraph)。n個頂點的完全圖記為。若，，（這里表示集合X中的元素個數(shù)），X中無相鄰頂點對，Y中亦然，則稱G為二分圖(bipartitegraph)；特別地，若，則，則稱G為完全二分圖，記成。

第十一頁，共四十三頁，2022年，8月28日2.4子圖如果,,圖H叫做圖G的子圖（subgraph），記作。若H是G的子圖，則G稱為H的母圖。2.5頂點的度設(shè)，G中與v關(guān)聯(lián)的邊數(shù)（每個環(huán)算作兩條邊）稱為v的度(degree)，記作。若是奇數(shù)，稱v是奇頂點(oddpoint)；若是偶數(shù)，稱v是偶頂點(evenpoint)。關(guān)于頂點的度，我們有如下結(jié)果：(i)(ii)任意一個圖的奇頂點的個數(shù)是偶數(shù)。第十二頁，共四十三頁，2022年，8月28日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ò)的5種常用表示方法：鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、弧表表示法、鄰接表表示法和星形表示法。在下面數(shù)據(jù)結(jié)構(gòu)的討論中，我們首先假設(shè)是一個簡單有向圖，，并假設(shè)V中的頂點用自然數(shù)1,2,…n表示或編號，A中的弧用自然數(shù)1,2,…m表示或編號。

第十三頁，共四十三頁，2022年，8月28日（i）鄰接矩陣表示法鄰接矩陣表示法是將圖以鄰接矩陣（adjacencymatrix）的形式存儲在計算機中。圖的鄰接矩陣是如下定義的：C是一個n*n的0-1矩陣，即也就是說，如果兩節(jié)點之間有一條弧，則鄰接矩陣中對應(yīng)的元素為1；否則為0。

第十四頁，共四十三頁，2022年，8月28日例1對于所示的圖，可以用鄰接矩陣表示為同樣，對于網(wǎng)絡(luò)中的權(quán)，也可以用類似鄰接矩陣的矩陣表示。只是此時一條弧所對應(yīng)的元素不再是1，而是相應(yīng)的權(quán)而已。如果網(wǎng)絡(luò)中每條弧賦有多種權(quán)，則可以用多個矩陣表示這些權(quán)。第十五頁，共四十三頁，2022年，8月28日（ii）關(guān)聯(lián)矩陣表示法關(guān)聯(lián)矩陣表示法是將圖以關(guān)聯(lián)矩陣（incidencematrix）的形式存儲在計算機中．圖的關(guān)聯(lián)矩陣B是如下定義的：B是一個n*m的矩陣，即第十六頁，共四十三頁，2022年，8月28日如果一個節(jié)點是一條弧的起點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點是一條弧的終點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為-1；如果一個節(jié)點與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為0。例2對于例1所示的圖，如果關(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)矩陣表示為（列單位為弧）

第十七頁，共四十三頁，2022年，8月28日（iii）弧表示法弧表表示法將圖以弧表（arclist）的形式存儲在計算機中。所謂圖的弧表，也就是圖的弧集合中的所有有序?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，則弧表表示如下：

起點11234455終點23423534權(quán)89640367第十八頁，共四十三頁，2022年，8月28日（iv）鄰接表表示法鄰接表表示法將圖以鄰接表（adjacencylists）的形式存儲在計算機中。所謂圖的鄰接表，也就是圖的所有節(jié)點的鄰接表的集合；而對每個節(jié)點，它的鄰接表就是它的所有出弧。鄰接表表示法就是對圖的每個節(jié)點，用一個單向鏈表列出從該節(jié)點出發(fā)的所有弧，鏈表中每個單元對應(yīng)于一條出弧。為了記錄弧上的權(quán)，鏈表中每個單元除列出弧的另一個端點外，還可以包含弧上的權(quán)等作為數(shù)據(jù)域。圖的整個鄰接表可以用一個指針數(shù)組表示。

第十九頁，共四十三頁，2022年，8月28日

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

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

i，轉(zhuǎn)(ii)。第二十三頁，共四十三頁，2022年，8月28日找出u0到其他各點的最短路徑第二十四頁，共四十三頁，2022年，8月28日第二十五頁，共四十三頁，2022年，8月28日3.2每對頂點之間的最短路徑計算賦權(quán)圖中各對頂點之間最短路徑，顯然可以調(diào)用Dijkstra算法。具體方法是：每次以不同的頂點作為起點，用Dijkstra算法求出從該起點到其余頂點的最短路徑，反復(fù)執(zhí)行次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。第二種解決這一問題的方法是由FloydRW提出的算法，稱之為Floyd算法。

第二十六頁，共四十三頁，2022年，8月28日假設(shè)圖權(quán)的鄰接矩陣為，來存放各邊長度，其中：；之間沒有邊，在程序中以各邊都不可能達到的充分大的數(shù)代替；是i,j之間邊的長度，。第二十七頁，共四十三頁，2022年，8月28日Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列，其中表示從頂點到頂點的路徑上所經(jīng)過的頂點序號不大于k

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

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

(例題見附件)第二十八頁，共四十三頁，2022年，8月28日§4樹

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

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

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

在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.第三十二頁，共四十三頁，2022年，8月28日a)深探法

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

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

第三十三頁，共四十三頁，2022年，8月28日b)廣探法步驟如下：i)在點集V中任取一點u,ii)令所有標號i的點集為是否均已標號.對所有未標號之點均標以i+1,記下這些iii)對標號i+1的點重復(fù)步步驟ii)，直到全部點得到給u以標號0.Vi,檢查[Vi,V\Vi]中的邊端點邊.例用廣探法求出下圖10的一棵生成樹

標號為止.圖1031012213212234第三十四頁，共四十三頁，2022年，8月28日B破圈法

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

ii)

是滿足i)的盡可能小的權(quán)，3)當?shù)?)步不能繼續(xù)執(zhí)行時，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.最小生成樹與算法第三十六頁，共四十三頁，2022年，8月28日例用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條

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

中選取.但與都第三十七頁，共四十三頁，2022年，8月28日B破圈法算法2

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

立即生成一個圈.去掉此

圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余的弦，直到全部弦檢查完畢為止.例用破圈法求下圖的最小樹.第三十八頁，共四十三頁，2022年，8月28日prim算法構(gòu)造最小生成樹設(shè)置兩個集合P和Q,其中P用于存放的最小生成樹G中的頂點，集合Q存放的最小生成樹G中的邊。令集合P的初值為（假設(shè)構(gòu)造最小生成樹時，從頂點出發(fā)），集合Q的初值為。prim算法的思想是，從所有，的邊中，選取具有最小權(quán)值的邊，將頂點v加入集合P中，將邊pv加入集合Q中，如此不斷重復(fù)，直到P=V時，最小生成樹構(gòu)造完畢，這時集合Q中包含了最小生成樹的所有邊。第三十九頁，共四十三頁，2022年，8月28日例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)-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第四十頁，共四十三頁，2022年，8月28日例從北京（Pe）乘飛機到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL5635215160M5621577870N35213