《運籌學(xué)與圖論》

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

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

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

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

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

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

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

去掉G中所有邊，得到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為等邊三角形，，連接三頂點的路線（稱為網(wǎng)絡(luò)）。這種網(wǎng)絡(luò)有許多個，其中最短路線者顯然是二邊之和（如AB∪AC）。ABC.ABCP

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

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