運(yùn)籌學(xué)——圖與網(wǎng)絡(luò)分析-文庫吧資料
2025-05-22 22:11本頁面
【正文】 V1 V1VV *1*1,OR3 32 ? 注意：容量網(wǎng)絡(luò)圖 D的截集不是唯一的，截集個數(shù)是有限的。 ? 最大流問題就是求一個流 f=｛ fij｝使其流量 達(dá)到最大，并且滿足： ? 注意：尋求網(wǎng)絡(luò)中的最大流就相當(dāng)于求線性規(guī)劃模型的最優(yōu)解。如果 D=(V,A,C)中沒有給出弧上的流量 fij，可認(rèn)為 fij＝ 0。 注意：任一 D=(V,A,C)都存在可行流。 對發(fā)點(diǎn) vs，有 。 1）容量限制條件 : 對 D中的每一條弧（ vi， vj） ，有 0≤ fij ≤cij。 OR3 28 ? 流 ? 在 D=(V,A,C)中，如果實(shí)際通過每一?。?vi， vj）的流量是 fij，則稱集合 f=｛ fij｝為網(wǎng)絡(luò) D=(V,A,C)上的一個流。 ? 尋找最短路徑的方法：反向追蹤法。 即為從 v1到各點(diǎn)的最短路。即為則該有：，＝步，對所有的若進(jìn)行到某一步，如第對（（vvvdvvdvvdwvvdvvdwvvdsjskjskjskijistijstsjjspjkpjktpj),(),(),(. .. ,21), .. .,2,1(),(),(, .. .,2), .. .,2,1(),())1())1()()1(m i n?????????OR3 20 ? 基本步驟： ? 令 ，其中，若 v1與 vj間沒弧，則記w1j=+∞。 一般的，最多逼近 n1次即得到最短路。） ? 公式來源分析： ? ?wvvvvijisijsjiisvvjisddvvvvvvvjs?????),(),(,...,...,...,...,m i n???????? ??? ??最短路最短路的最短路到OR3 18 ? 基本思路： 用 逐次逼近 來求網(wǎng)絡(luò)中的最短路：每次求出從始點(diǎn)到網(wǎng)絡(luò)中其余各點(diǎn) 有限制 的最短路。 ? 假設(shè)前提：任意兩點(diǎn) vi, vj之間都有一條弧。 Si： P標(biāo)號節(jié)點(diǎn)的集合。 187。 187。 OR3 14 – 最短路算法 ? Dijkstra算法 ：有向圖 ， wij≥0 ? 一般結(jié)論： – Dijkstra算法基本思想 : – 采用標(biāo)號法 : P標(biāo)號和 T標(biāo)號 187。 OR3 13 最短路問題 引例 : – 單行線交通網(wǎng)： v1到 v8使總費(fèi)用最小的旅行路線。令 Ei＝ Ei1 ∪｛ ei｝ ,如果這樣的邊不存在，則 T=(V, Ei1)是最小樹。 OR3 12 避圈法的基本步驟 P259 ? 第一步：令 i＝ 1， E0＝空集。 求最小支撐樹的方法： 破圈法：在連通圖中任取一個圈，去掉一條權(quán)數(shù)最大的邊，在余下的圖中重復(fù)上述步驟，直至無圈為止。 避圈法：在圖中每次任取一條邊，與已經(jīng)取得的任何一些邊不夠成圈，重復(fù)這個過程，直到不能進(jìn)行為止。 定理 7：圖 G有支撐樹的充要條件是圖 G是連通的。 定量 5：圖 G=（ V,E)是一個樹的充要條件是 G是連通圖，并且 q(G)= p(G) 1. 定量 6：圖 G=（ V,E)是一個樹的充要條件是任意兩個頂點(diǎn)之間恰好有一條鏈。 定理： 定量 3：設(shè)圖 G=（ V,E)是一個樹， p(G) ≥2,則 G中至少有兩個懸掛點(diǎn)。 （ 5）路：在有向圖中，如果鏈上每條弧的箭線方向與鏈行進(jìn)方向相同，則稱之為路。 支撐子圖：對 G=(V,E)，若 G’=(V’,E’)，使 V’＝ V， E’包含于E，則 G’是 G的一個支撐子圖。 （ 4）連通圖：任意兩點(diǎn)之間至少有一條鏈的圖。 基本定理： 圖 G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的兩倍，即 任一圖中，奇點(diǎn)的個數(shù)為偶數(shù)。 e7 OR3 7 ?
法律信息相關(guān)推薦
鄂ICP備17016276號-1