圖與網(wǎng)絡(luò)分析

(GraphTheoryandNetworkAnalysis)1.圖的基本概念與模型2.最小生成樹問題3.最短路問題本章主要內(nèi)容：.圖論運(yùn)籌學(xué)的重要分支主要應(yīng)用領(lǐng)域物理學(xué)、化學(xué)、控制論、信息論、科學(xué)管理、電子計(jì)算機(jī)等圖論理論和方法應(yīng)用實(shí)例在組織生產(chǎn)中，為完成某項(xiàng)生產(chǎn)任務(wù)，各工序之間怎樣銜接，才能使生產(chǎn)任務(wù)完成得既快又好。一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的路線走，所走的路程最短。各種通信網(wǎng)絡(luò)的合理架設(shè)，交通網(wǎng)絡(luò)的合理分布等問題，應(yīng)用圖論的方法求解都很簡(jiǎn)便。.圖論的起源與發(fā)展歐拉在1736年發(fā)表了圖論方面的第一篇論文，解決了著名的哥尼斯堡七橋問題。七橋問題：哥尼斯堡城中有一條河叫普雷格爾河，該河中有兩個(gè)島，河上有七座橋。當(dāng)時(shí)那里的居民熱衷于這樣的問題：一個(gè)散步者能否走過七座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)。圖(a)歐拉將此問題歸結(jié)為如圖(b)所示圖形的一筆畫問題。即能否從某一點(diǎn)開始，不重復(fù)地一筆畫出這個(gè)圖形，最后回到出發(fā)點(diǎn)。歐拉證明了這是不可能的，因?yàn)閳D(b)中的每個(gè)點(diǎn)都只與奇數(shù)條線相關(guān)聯(lián)，不可能將這個(gè)圖不重復(fù)地一筆畫成。.圖：由點(diǎn)及點(diǎn)與點(diǎn)的連線構(gòu)成，反映了實(shí)際生活中某些對(duì)象之間的某些特定關(guān)系。點(diǎn)：代表研究的對(duì)象；連線：表示兩個(gè)對(duì)象之間特定的關(guān)系。圖：是反映對(duì)象之間關(guān)系的一種抽象。一般情況下，圖中點(diǎn)的相對(duì)位置如何，點(diǎn)與點(diǎn)之間連線的長(zhǎng)短曲直，對(duì)反映對(duì)象之間的關(guān)系并不重要。1.圖的基本概念與模型.(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示。.a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。下圖就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。相互認(rèn)識(shí)用兩條反向的弧表示。無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。.圖的概念圖是由一些點(diǎn)及一些點(diǎn)之間的連線(不帶箭頭或帶箭頭)組成的圖形。兩點(diǎn)之間不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。如果一個(gè)圖G由點(diǎn)及邊所構(gòu)成，則稱之為無向圖(也簡(jiǎn)稱為圖)，記為，式中V，E分別是G的點(diǎn)集合和邊集合。一條連結(jié)點(diǎn)的邊記為［］(或［］)。如果一個(gè)圖D由點(diǎn)及弧所構(gòu)成，則稱為有向圖，記為D=(V，A)，式中V，A分別表示D的點(diǎn)集合和弧集合。一條方向是從vi指向vj的弧，記為()。.無向圖的例子其中無向圖.有向圖的例子其中有向圖.v3e7e4e8e5e6e1e2e3v1v2v4v5邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。端點(diǎn),關(guān)聯(lián)邊,相鄰.如果邊e的兩個(gè)端點(diǎn)相重合，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對(duì)無環(huán)、無多重邊的圖稱作簡(jiǎn)單圖。v3e7e4e8e5e6e1e2e3v1v2v4v5環(huán),多重邊,簡(jiǎn)單圖.圖中某些點(diǎn)和邊的交替序列，若其中各邊互不相同，且對(duì)任意vi,t-1和vit均相鄰稱為鏈。用μ表示：v3e7e4e8e5e6e1e2e3v1v2v4v5起點(diǎn)與終點(diǎn)重合的鏈稱作圈。如果每一對(duì)頂點(diǎn)之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱圖不連通。鏈，圈，連通圖.設(shè)圖G＝（V，E），對(duì)G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等。端點(diǎn)無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256

網(wǎng)絡(luò)（賦權(quán)圖）.圖的模型應(yīng)用例6.1有甲,乙,丙,丁,戊,己6名運(yùn)動(dòng)員報(bào)名參加A,B,C,D,E,F6個(gè)項(xiàng)目的比賽。下表中打√的是各運(yùn)動(dòng)員報(bào)告參加的比賽項(xiàng)目。問6個(gè)項(xiàng)目的比賽順序應(yīng)如何安排，做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。ABCDEF甲√√乙√√√丙√√丁√√戊√√√己√√√.解：用圖來建模。把比賽項(xiàng)目作為研究對(duì)象，用點(diǎn)表示。如果2個(gè)項(xiàng)目有同一名運(yùn)動(dòng)員參加，在代表這兩個(gè)項(xiàng)目的點(diǎn)之間連一條線，可得下圖。ABCDEF在圖中找到一個(gè)點(diǎn)序列，使得依次排列的兩點(diǎn)不相鄰，即能滿足要求。如：1)A,C,B,F,E,D2)D,E,F,B,C,A.一個(gè)班級(jí)的學(xué)生共計(jì)選修A、B、C、D、E、F六門課程，其中一部分人同時(shí)選修D(zhuǎn)、C、A，一部分人同時(shí)選修B、C、F，一部分人同時(shí)選修B、E，還有一部分人同時(shí)選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。思考題.思考題解答：

以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個(gè)符合要求的考試課程表。.AFEDCB.AFEDCB.樹是圖論中結(jié)構(gòu)最簡(jiǎn)單但又十分重要的圖。在自然和社會(huì)領(lǐng)域應(yīng)用極為廣泛。樹就是一個(gè)無圈的連通圖。上圖中，(a)就是一個(gè)樹，而(b)因?yàn)閳D中有圈所以就不是樹，(c)因?yàn)椴贿B通所以也不是樹。v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)2.最小生成樹問題.

例6.2乒乓求單打比賽抽簽后，可用樹圖來表示相遇情況，如下圖所示。ABCDEFGH運(yùn)動(dòng)員.例6.3某企業(yè)的組織機(jī)構(gòu)圖也可用樹圖表示。廠長(zhǎng)人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長(zhǎng)經(jīng)營(yíng)副廠長(zhǎng)開發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科銷售科檢驗(yàn)科動(dòng)力科.性質(zhì)1：任何樹中必存在次為1的點(diǎn)。性質(zhì)2：n個(gè)頂點(diǎn)的樹必有n-1條邊。性質(zhì)3：樹中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈。性質(zhì)4：樹連通，但去掉任一條邊，必變?yōu)椴贿B通。性質(zhì)5：樹無回圈，但不相鄰的兩個(gè)點(diǎn)之間加一條邊，恰得到一個(gè)圈。v1v2v3v4v5v6.

給了一個(gè)圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在下圖中，(b)和(c)都是(a)的生成子圖。如果圖G的一個(gè)生成子圖還是一個(gè)樹，則稱這個(gè)生成子圖為生成樹，在下圖中，(c)就是(a)的生成樹。

最小生成樹問題就是指在一個(gè)賦權(quán)的連通的無向圖G中找出一個(gè)生成樹，并使得這個(gè)生成樹的所有邊的權(quán)數(shù)之和為最小。(a)(b)(c).(1)破圈法求生成樹的方法：破圈法和避圈法.生成樹.（2）避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5.破圈法：算法的步驟：1、在給定的賦權(quán)的連通圖上任找一個(gè)圈。2、在所找的圈中去掉一個(gè)權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521邊數(shù)＝n-1=5賦權(quán)圖中求最小樹的方法：破圈法和避圈法.v1v2v3v4v5v643521得到最小樹：MinC(T)=15.避圈法:

去掉G中所有邊，得到n個(gè)孤立點(diǎn)；然后加邊。加邊的原則為：從最短邊開始添加，加邊的過程中不能形成圈，直到點(diǎn)點(diǎn)連通(即:n-1條邊)。5v1v2v3v4v5v6843752618.v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15.v1v7v4v3v2v5v620159162532817412336練習(xí)：應(yīng)用破圈法求最小樹.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v6201591625328174123.v1v7v4v3v2v5v6201591625328174123.v1v7v4v3v2v5v61591625328174123.v1v7v4v3v2v5v61591625328174123.v1v7v4v3v2v5v691625328174123.v1v7v4v3v2v5v691625328174123.v1v7v4v3v2v5v6925328174123.v1v7v4v3v2v5v6925328174123.v1v7v4v3v2v5v69328174123.v1v7v4v3v2v5v69328174123.v1v7v4v3v2v5v693174123min=1+4+9+3+17+23=57.練習(xí)：應(yīng)用避圈法求最小樹v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336.v1v7v4v3v2v5v620159162532817412336min=1+4+9+3+17+23=57.3.最短路問題問：如何用最短的線路將三部電話連起來？

此問題可抽象為設(shè)△ABC為等邊三角形，，連接三頂點(diǎn)的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個(gè)，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC.ABCP

但若增加一個(gè)周轉(zhuǎn)站（新點(diǎn)P），連接4點(diǎn)的新網(wǎng)絡(luò)的最短路線為PA＋PB＋PC。最短新路徑之長(zhǎng)N比原來只連三點(diǎn)的最短路徑O要短。這樣得到的網(wǎng)絡(luò)不僅比原來節(jié)省材料，而且穩(wěn)定性也更好。.最短路問題：從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路.有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。.最短路問題的求解算法----狄克斯拉(Dijkstra)標(biāo)號(hào)算法狄克斯拉(Dijkstra)標(biāo)號(hào)算法的基本思路：若序列{vs,v1…..vn-1,vn

}是從vs到vt間的最短路，則序列{vs,v1…..vn-1

}必為從vs到vn-1的最短路。

假定v1→v2→v3→v4是v1

→v4的最短路，則v1→v2

→v3一定是v1

→v3的最短路，v2

→v3

→v4也一定是v2

→v4的最短路。v1v2v3v4v5.求網(wǎng)絡(luò)圖的最短路，設(shè)圖的起點(diǎn)是vs,終點(diǎn)是vt

,以vi為起點(diǎn)vj為終點(diǎn)的弧記為(i,j)，距離為dijP標(biāo)號(hào)(臨時(shí)標(biāo)號(hào))：b(j)—起點(diǎn)vs到點(diǎn)vj的最短路長(zhǎng)；T標(biāo)號(hào)(固定標(biāo)號(hào))：k(i,j)=b(i)+dij，步驟：1.令起點(diǎn)vs的標(biāo)號(hào)為：b(s)＝0。