運籌學圖與網(wǎng)絡ppt課件-免費閱讀
【正文】 如圖。如果不存在這樣的路，則已經(jīng)求得最大流。 ? 已知：設備每年年初的價格表 ? 設備維修費如下表 年份 1 2 3 4 5 年初價格 11 11 12 12 13 使用年數(shù) 01 12 23 34 45 每年維修費用 5 6 8 11 18 ? 例 3的解：將問題轉(zhuǎn)化為最短路問題，如下圖： 用 vi表示“第 i年年初購進一臺新設備” ,弧（ vi,vj）表示第 i年年初購進的 設備一直使用到第 j年年初?？梢园褵o向圖的每一邊（ vi,vj）都用方向相反的兩條?。?vi,vj）和（ vj,vi）代替，就化為有向圖，即可用 Dijkstra算法來求解。如果 vt 未標號，則可以斷言不存在從 vs到 vt的有向路。 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 網(wǎng)絡概念 ? 節(jié)點與（有向）邊 每一條邊和兩個節(jié)點關聯(lián)，一條邊可以用兩個節(jié)點的標號表示（ i， j） j i ■ 路徑（ Path） 前后相繼并且方向相同的邊序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 ■ 網(wǎng)絡由節(jié)點和邊組成 網(wǎng)絡概念 ■ 回路（ Circuit） 起點和終點重合的路徑稱為 回路 μ={(1,2),(2,4),(4,1)} 回路中各條邊方向相同 4 2 3 1 ■ 鏈（ Chain） 前后相繼并且方向不一定相同的邊序列稱為 鏈 C={(1,2),(3,2),(3,4)} 4 2 3 1 網(wǎng)絡概念 ■ 連通圖 任意兩個節(jié)點之間至少有一條鏈的圖稱為 連通圖 2 4 3 5 1 ■ 圈 (Cycle) 起點和終點重合的鏈稱為 圈 ρ ={(1,2),(2,4),(3,4),(1,3)} 圈中各條邊方向不一定相同 4 2 3 1 ■ 樹 (Tree) 無圈的連通圖稱為樹 樹中只與一條邊關聯(lián)的節(jié)點稱為 懸掛節(jié)點 網(wǎng)絡概念 ? 平面圖 (planar graph)，若在平面上可以畫出該圖而沒有任何邊相交 ? 走過圖中所有邊且每條邊僅走一次的閉行走稱為歐拉回路 ? 定理 ：偶圖一定存在歐拉回路 (一筆畫定理 ) ? 圖中都是偶點的圖稱為偶圖 (even graph) 哈密爾頓回路 ( Hamiltonian circuit)問題 ? 連通圖 G(V,E)中的回路稱為哈密爾頓回路，若該回路包括圖中所有的點。 定理 以下關于樹的六種不同描述是等價的： 1. 無圈連通圖 。 ? 而有些關系是不對稱的，例如父子關系、上下級關系、加工工序的先后順序等都具有單向性，用圖來表示這些關系時，得到的邊是具有方向的，用帶箭頭的線來表示，稱為 弧 。 ? 例如圖中， v1和 v6之間沒有通路，因此它不是連通圖，而如果去掉 v6，則構(gòu)成一個連通圖。 ? 若 v0 ≠vn則稱該鏈為開鏈 ，反之稱為 閉鏈 或 回路 。 ? 次為 1的點稱為 懸掛點 ，與懸掛點連接的邊稱作懸掛邊 ； ? 次為 0的點稱為 孤立點 。 ? 例如圖中的圖 G， p(G)=6，q(G)=9， ? v1， v2是 e1和 e2的端點， e1和 e2都是 v1和 v2的關聯(lián)邊。 圖的表示 ],[ 211 ???e ],[ 212 ???e],[ 413 ???e ],[ 314 ???e],[ 315 ???e ],[ 426 ???e],[ 437 ???e ],[ 448 ???e],[ 549 ???e),(),( 987654321654321 eeeeeeeeeE ?? ???????e1 e2 e3 e4 e5 v2 v3 v1 v4 v5 v6 e6 e7 e8 e9 點與邊 ? 頂點數(shù) 集合 V中元素的個數(shù) ，記作 p(G)。 ? 含有多重邊的圖稱作 多重圖 。 ? 設 V1和 V2分別是圖 G中次數(shù)為奇數(shù)和偶數(shù)的頂點集合。除起點和終點外點均不相同的閉鏈，稱為 初等回路 或稱為 圈 。 ? 部分圖 若 V1=V2，E1?E2 ，則稱 G1為 G2的一個 部分圖 。 ? 除起點和終點外點均不相同的回路稱為 初等回路 。 6. 每一對頂點之間有一條且僅有一條鏈 。 ? 最短路問題是網(wǎng)絡分析中的一個基本問題 ，它不僅可以直接應用于解決生產(chǎn)實際的許多問題 ， 如管道鋪設 、 線路安排 、 廠區(qū)布局等 ，而且經(jīng)常被作為一個基本工具 ， 用于解決其它的優(yōu)化問題 。 ? 例 1 求下圖中 v1到 v6的最短路 ? 解：采用 Dijkstra算法，可解得最短路徑為 v1 v3 v4 v6 ? 各點的標號圖如下： 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) v
教學課件相關推薦
鄂ICP備17016276號-1