運籌學基礎(chǔ)圖論方法(1)-文庫吧資料
2025-05-22 22:18本頁面
【正文】 最小樹杈 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 破圈法答案 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 此為最小樹杈，最小線路長度為 15 避圈法答案 v3 v2 1 v4 2 v5 3 v6 4 v1 5 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 此為最小樹杈，最小線路長度為 15 練習：求最小樹杈 2 5 3 1 2 2 3 4 5 3 3 2 3 2 2 2 167。 此為最小樹杈，最小線路長度為 54 v1 v2 v3 v4 v5 25 20 10 9 15 12 30 又例 在住宅小區(qū)安裝供水管道。在余下的圖中重復這個步驟，直到得到一連通的不含圈的圖為止。 破圈法 v1 v2 v3 v5 e2 e3 e5 e1 e6 e7 e8 e4 v4 v1 v2 e1 v3 e2 e4 v4 v5 e6 避圈法 破圈法 (克魯斯喀爾法 ) 例：已知連接五個城市的公交線路圖，在要在五個城市間架設電話線，為了便于維修要求電話線必須沿公路架設，并且電話線總長度最小。 方案一 不連通 方案三 方案二 有圈 樹 問題：如何構(gòu)建才能是最短路徑的樹 — 最小枝權(quán)樹問題 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 接上節(jié)、求最小樹杈問題 最小樹杈問題 是關(guān)于在一個網(wǎng)絡中，從 一個起點 出發(fā)到 所有點 ，找出一條或幾條路線，以使在這樣一些路線中所采用的全部支線的 總長度是最小的 ，或鋪設費用最少。 樹圖的任意兩個點之間有一條且僅有一條唯一的通路，是最脆弱的連通圖 樹：一個無圈的連通圖稱為樹。 A B C D E F A B C D E F甲 √ √ √乙 √ √ √丙 √ √丁 √ √戊 √ √ √己 √ √ √A C B F E D 167。 v1 v2 v3 v4 v5 v6 e2 e4 e5 e6 e7 e8 e1 e3 v7 v8 e9 e10 圖的名詞和基本概念 v1 v2 v3 v4 v5 v6 e2 e4 e5 e6 e7 e1 e3 懸掛節(jié)點 : 次為 1的點稱為 懸掛節(jié)點 : 次： 與一個點相關(guān)聯(lián)的邊的數(shù)目稱為 次 , 如 v1 的次為 2， v5的次為 3，次為奇數(shù)的點稱為 奇點 ，次為偶數(shù)的點稱為 偶點 ，次為 0的點稱為 孤立點 ，如 v6 利用圖可以對象之間的關(guān)系 例：有甲、乙、丙、丁、戊、己六名運動員參加 A、 B、C、 D、 E、 F六個項目的比賽。 連通圖 ：一個圖中，任意兩個頂點至少存在一條鏈，則稱這樣的圖為連通圖。例如 (v1 ,e1 ,v2 , e2 ,v4 ,e3 ,v3 ,e4 ,v1 ) 。 甲 乙 丙 丁 戊 ?。喝酎c與點之間的連線有方向，稱為弧，由此構(gòu)成的圖為有向圖。 圖的名詞和基本概念 邊 ：若點與點之間的連線沒有方向，稱為邊。 太原 石家莊 保定
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1