[小學(xué)教育]第7講圖與網(wǎng)絡(luò)模型-展示頁(yè)
2024-10-25 18:12本頁(yè)面
【正文】 4 4 3 10 6 5 v2 V7 （乙地） v3 v4 v5 v6 管 理 運(yùn) 籌 學(xué) 9 167。也可直接在無向圖中用 Dijkstra算法來求解。 解：這是一個(gè)求無向圖的最短路的問題。 2 最短路問題 例 2 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？下圖給出了甲乙兩地間的交通圖。 { ( , ) | , }i j i jv v v I v J??管 理 運(yùn) 籌 學(xué) 7 167。在所有的 sij中，找到其值為最小的弧。如果上述的弧的集合不是空集，則轉(zhuǎn)下一步。如果 vt已標(biāo)號(hào)（ lt,kt），則 vs到 vt的距離為 lt，而從 vs到 vt的最短路徑，則可以從 kt 反向追蹤到起點(diǎn)vs 而得到。這條路上所有弧的權(quán)數(shù)的總和被稱為從 Vs到 Vt的距離。 管 理 運(yùn) 籌 學(xué) 6 167。 ? 賦權(quán)圖： 對(duì)一個(gè)無向圖 G的每一條邊 (vi,vj)，相應(yīng)地有一個(gè)數(shù) wij，則稱圖 G為賦權(quán)圖， wij稱為邊 (vi,vj)上的權(quán)。 ? 連通圖 ： 對(duì)無向圖 G，若任何兩個(gè)不同的點(diǎn)之間，至少存在一條鏈，則 G為連通圖。 1 圖與網(wǎng)絡(luò)的基本概念 ? 無向圖： 由點(diǎn)和邊構(gòu)成的圖，記作 G=（ V， E）。相互認(rèn)識(shí)用兩條反向的弧表示。 1 圖與網(wǎng)絡(luò)的基本概念 a1 a2 a3 a4 a14 a7 a8 a9 a6 a5 a10 a12 a11 a13 a15 (v1) 趙 (v2)錢 (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 圖 113 如果我們把上面例子中的“相互認(rèn)識(shí)”關(guān)系改為“認(rèn)識(shí)” 的關(guān)系，那么只用兩點(diǎn)之間的聯(lián)線就很難刻畫他們之間的關(guān)系了，這是我們引入一個(gè)帶箭頭的聯(lián)線，稱為弧。 1 圖與網(wǎng)絡(luò)的基本概念 當(dāng)然圖論不僅僅是要描述對(duì)象之間關(guān)系，還要研究特定關(guān)系之間的內(nèi)在規(guī)律，一般情況下圖中點(diǎn)的相對(duì)位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長(zhǎng)短曲直，對(duì)于反映對(duì)象之間的關(guān)系并不是重要的，如對(duì)趙等七人的相互認(rèn)識(shí)關(guān)系我們也可以用圖 112來表示，可見圖論中的圖與幾何圖、工程圖是不一樣的。 例如：在一個(gè)人群中，對(duì)相互認(rèn)識(shí)這個(gè)關(guān)系我們可以用圖來表示，圖 111就是一個(gè)表示這種關(guān)系的圖。 4 最大流問題 管 理 運(yùn) 籌 學(xué) 2 167。 2 最短路問題 167。管 理 運(yùn) 籌 學(xué) 1 第七講 圖與網(wǎng)絡(luò)模型 167。 1 圖與網(wǎng)絡(luò)的基本概念 167。 3 最小生成樹問題 167。 1 圖與網(wǎng)絡(luò)的基本概念 圖論中圖是由點(diǎn)和邊構(gòu)成，可以反映一些對(duì)象之間的關(guān)系。 (v1) 趙 (v2)錢 (v3)孫 (v4)李 (v5) 周 (v6)吳 (v7)陳 e2 e1 e3 e4 e5 圖 111 管 理 運(yùn) 籌 學(xué) 3 167。 (v1) 趙 (v2)錢 孫 (v3) 李 (v4) 周 (v5) 吳 (v6) 陳 (v7) e2 e1 e3 e4 e5 圖 112 管 理 運(yùn) 籌 學(xué) 4 167。圖 113就是一個(gè)反映這七人“認(rèn)識(shí)”關(guān)系的圖。 管 理 運(yùn) 籌 學(xué) 5 167。 ? 有向圖： 由點(diǎn)和弧構(gòu)成的圖，記作 D=（ V， A）。 ? 回路： 若路的第一個(gè)點(diǎn)和最后一個(gè)點(diǎ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ò)。 2 最短路問題 ? 最短路問題：對(duì)一個(gè)賦權(quán)的有向圖 D中的指定的兩個(gè)點(diǎn) Vs和 Vt找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權(quán)數(shù)的總和最小，這條路被稱之為從 Vs到 Vt的最短路。 一、求解最短路的 Dijkstra算法 (雙標(biāo)號(hào)法） 步驟： V1以標(biāo)號(hào) (0,s) I，沒標(biāo)號(hào)的點(diǎn)的集合 J以及弧的集合 3. 如果上述弧的集合是空集，則計(jì)算結(jié)束。如果 vt 未標(biāo)號(hào)，則可以斷言不存在從 vs到 vt的有向路。 4. 對(duì)上述弧的集合中的每一條弧，計(jì)算 sij=li+cij 。不妨設(shè)此弧為（ Vc,Vd），則給此弧的終點(diǎn)以雙標(biāo)號(hào)（ scd,c） ,返回步驟 2。 2 最短路問題 例 1 求下圖中 v1到 v6的最短路 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 各點(diǎn)的標(biāo)號(hào)圖如下： v2 3 5 2 7 5 3 1 5 1 2 v1 v6 v5 v3 v4 (3,1) v2 3 5 2 7 5 3 1 5 1 2 V1 （ 0,s) v5 (8,4) v6 (2,1) v3 (3,3) v4 管 理 運(yùn) 籌 學(xué) 8 167。權(quán)數(shù)表示兩地間公路的長(zhǎng)度（單位：公里）?？梢园褵o向圖的每一邊（ vi,vj）都用方向相反的兩條?。?vi,vj）和（ vj,vi）代替，就化為有向圖，即可用 Dijkstra算法來求解。只要在算法中把從已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的弧的集合改成已標(biāo)號(hào)的點(diǎn)到未標(biāo)號(hào)的點(diǎn)的邊的集合即可。 2 最短路問題 例 2最終解得： 最短路徑 v1 v3 v5 v6 v7，每點(diǎn)的標(biāo)號(hào)見下圖 （ 0,s） V1 （甲地） 15 17 6 2 4 4 3 10 6 5 (13,3) v2 (22,6) V7 （乙地） V5 (14,3) V6 (16,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1