數(shù)學(xué)建模選修課課件圖與網(wǎng)絡(luò)模型

1圖與網(wǎng)絡(luò)模型§1圖與網(wǎng)絡(luò)的基本概念§2最短路問題§3最小生成樹問題2§1圖與網(wǎng)絡(luò)的基本概念

圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對象之間的關(guān)系。例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示，圖11-1就是一個表示這種關(guān)系的圖。(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5圖11-13

當(dāng)然圖論不僅僅是要描述對象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的，如對趙等七人的相互認(rèn)識關(guān)系我們也可以用圖11-2來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5圖11-24a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳圖11-3

如果我們把上面例子中的“相互認(rèn)識”關(guān)系改為“認(rèn)識”的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。圖11-3就是一個反映這七人“認(rèn)識”關(guān)系的圖。相互認(rèn)識用兩條反向的弧表示。5無向圖：由點(diǎn)和邊構(gòu)成的圖，記作G=（V，E）。有向圖：由點(diǎn)和弧構(gòu)成的圖，記作D=（V，A）。連通圖：對無向圖G，若任何兩個不同的點(diǎn)之間，至少存在一條鏈，則G為連通圖?；芈罚喝袈返牡谝粋€點(diǎn)和最后一個點(diǎn)相同，則該路為回路。賦權(quán)圖：對一個無向圖G的每一條邊(vi,vj)，相應(yīng)地有一個數(shù)wij，則稱圖G為賦權(quán)圖，wij稱為邊(vi,vj)上的權(quán)。網(wǎng)絡(luò)：

在賦權(quán)的有向圖D中指定一點(diǎn)，稱為發(fā)點(diǎn)，指定另一點(diǎn)稱為收點(diǎn)，其它點(diǎn)稱為中間點(diǎn)，并把D中的每一條弧的賦權(quán)數(shù)稱為弧的容量，D就稱為網(wǎng)絡(luò)。6§2最短路問題最短路問題：對一個賦權(quán)的有向圖D中的指定的兩個點(diǎn)Vs和Vt找到一條從Vs

到Vt

的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權(quán)數(shù)的總和被稱為從Vs到Vt的距離。一、求解最短路的Dijkstra算法(雙標(biāo)號法）步驟：1.給出點(diǎn)V1以標(biāo)號(0,s)2.找出已標(biāo)號的點(diǎn)的集合I，沒標(biāo)號的點(diǎn)的集合J以及弧的集合3.如果上述弧的集合是空集，則計(jì)算結(jié)束。如果vt已標(biāo)號（lt,kt），則vs到vt的距離為lt，而從vs到vt的最短路徑，則可以從kt

反向追蹤到起點(diǎn)vs

而得到。如果vt

未標(biāo)號，則可以斷言不存在從vs到vt的有向路。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。4.對上述弧的集合中的每一條弧，計(jì)算sij=li+cij

。在所有的sij中，找到其值為最小的弧。不妨設(shè)此弧為（Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號（scd,c）,返回步驟2。7§2最短路問題

例1求下圖中v1到v6的最短路解：采用Dijkstra算法，可解得最短路徑為v1v3v4v6

各點(diǎn)的標(biāo)號圖如下：v23527531512v1v6v5v3v4(3,1)v23527531512V1（0,s)v5(8,4)v6(2,1)v3(3,3)v48§2最短路問題

例2電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。權(quán)數(shù)表示兩地間公路的長度（單位：公里）。解：這是一個求無向圖的最短路的問題?？梢园褵o向圖的每一邊（vi,vj）都用方向相反的兩條?。╲i,vj）和（vj,vi）代替，就化為有向圖，即可用Dijkstra算法來求解。也可直接在無向圖中用Dijkstra算法來求解。只要在算法中把從已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的弧的集合改成已標(biāo)號的點(diǎn)到未標(biāo)號的點(diǎn)的邊的集合即可。V1（甲地）1517624431065v2V7（乙地）v3v4v5v69§2最短路問題例2最終解得：最短路徑v1v3v5v6v7，每點(diǎn)的標(biāo)號見下圖（0,s）

V1（甲地）1517624431065(13,3)v2(22,6)V7（乙地）V5(14,3)V6(16,5)V3(10,1)V4(18,5)10§3最小生成樹問題樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。

圖11-11中，(a)就是一個樹，而(b)因?yàn)閳D中有圈所以就不是樹，(c)因?yàn)椴贿B通所以也不是樹。圖11-11v1v2v3v4v5v6v7v8v9v1v2v3v5v8v7v6v4v1v2v3v4v5v7v6v8v9(a)(b)(c)11§3最小生成樹問題

給了一個無向圖G=(V,E)，我們保留G的所有點(diǎn)，而刪掉部分G的邊或者說保留一部分G的邊，所獲得的圖G，稱之為G的生成子圖。在圖11-12中，(b)和(c)都是(a)的生成子圖。如果圖G的一個生成子圖還是一個樹，則稱這個生成子圖為生成樹，在圖11-12中，(c)就是(a)的生成樹。最小生成樹問題就是指在一個賦權(quán)的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權(quán)數(shù)之和為最小。圖11-12(a)(b)(c)12§3最小生成樹問題一、求解最小生成樹的破圈算法算法的步驟：1、在給定的賦權(quán)的連通圖上任找一個圈。2、在所找的圈中去掉一個權(quán)數(shù)最大的邊（如果有兩條或兩條以上的邊都是權(quán)數(shù)最大的邊，則任意去掉其中一條）。3、如果所余下的圖已不包含圈，則計(jì)算結(jié)束，所余下的圖即為最小生成樹，否則返回第1步。13§3最小生成樹問題例4用破圈算法求圖（a）中的一個最小生成樹v1331728541034v7v6v5v4v27v6v5v4v2v133725434v7v6v5v4v2v3v3v31v13372434v7v6v5v4v2v31v1337234v7v6v5v4v2v31v133723v7v6v5v4v2v31(a)(b)(c)(d)(e)(f)圖11-1314§3最小生成樹問題

例5、某大學(xué)準(zhǔn)備對其所屬的7個學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)，這個網(wǎng)絡(luò)的可能聯(lián)通的途徑如下圖，圖中v1,…,v7

表示7個學(xué)院辦公室，請?jiān)O(shè)計(jì)一個網(wǎng)絡(luò)能聯(lián)通7個學(xué)院辦公室，并使總