管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)-文庫吧資料
2025-01-15 05:27本頁面
【正文】 或 v6。第二個問題就是求中心問題。現(xiàn)該企業(yè)欲修建正規(guī)道路使各分廠互通，并欲在某一分廠建一俱樂部。 求重心 村莊之間的最短距離 dij * 村莊 人數(shù) wi v1 v2 v3 v4 v5 v6 v7 v1 30 0 5 2 7 7 6 10 v2 40 5 0 7 2 5 4 8 v3 25 2 7 0 6 5 4 8 v4 20 7 2 6 0 3 2 6 v5 50 7 5 5 3 0 1 3 v6 60 6 4 4 2 1 0 4 v7 60 10 8 8 6 3 4 0 ∑ wi dij * 1700 1335 1430 1070 835 770* 1330 例：下圖為一大型企業(yè)區(qū)域交通網(wǎng)絡(luò)圖。 解：計算見表。若滿足 則稱點 為圖 G的重心。 ? ?）（）（）（ 1rj1ir2ij ddmi nd ??? ?）（）（）（ 1krj1kirkij ddmi nd ?? ??? ?? ?? ? ? ?23210437594023153205377350235132049573400437540231532053773502351320457340DDDD?????????????????????????????????????????????求中心 在一個連通圖 G中，設(shè) d(vi ,vj)為 vi至 vj的最短距離，令： 為點 vi至點 vj的最大距離 ,若 G中的一點 v*滿足： 則稱點 v*為圖 G的中心。 ? ?? ?4rr16r1641654154414341324121411ddm i nddddddddddddm i n?????????即，? ?rjir1ij ddmi nd ??）（再構(gòu)造矩陣 D(2)，令 則 D(2)給出網(wǎng)絡(luò)中任意兩點直接到達(dá)，經(jīng)過一至三個中間點時的最短距離。 解 設(shè) dij表示相鄰兩點 vi與 vj間的距離，若 vi與 vj不相鄰時，令 dij=∞ 。計劃期（五年）中每年的 li與如 Ci表 18— 1所示，工廠要制定今后五年的設(shè)備更新計劃，問采取何種方案，使總費用最小。 例 5 某廠使用一種設(shè)備，每年年初都要決定該設(shè)備是否需要更新。 （ 4）重復(fù)第 3步，直到 vT點得到標(biāo)號為止。 （ 3）從已標(biāo)號的頂點出發(fā)，找出與已標(biāo)號點相鄰的所有未標(biāo)號點。對起點 vs，將 Lss=0填進(jìn) vs近旁的圓括號內(nèi)，表示vs點已標(biāo)號。 第四節(jié) 最短路問題 1．狄克斯特拉（ Dijkstra）算法 步驟如下： （ 1）對起點 vs進(jìn)行標(biāo)號。然后在余下圖中，重復(fù)上述過程，直到無圈為止。 ? ?? ??? ? Tvv ijji w)T(w ，求最小部分樹的兩種方法 算法 Ⅰ （ Kruskal算法）：其基本思想是，每一步從未選的邊中，選一條具有最小權(quán)的邊，使與已選的邊不構(gòu)成圈，直到每一條邊都選查過為止。 一個連通圖的部分樹是不唯一的，其中使各邊權(quán)的總和最小的那棵部分樹，稱為最小部分樹。 所謂避圈法，就是在連通圖 G中任意取一邊 e1，找一條不與 e1構(gòu)成圈的邊 e2，然后再找一條不與 {e1， e2}構(gòu)成圈的 e3，這樣繼續(xù)下去，直到這一過程不能進(jìn)行時為止，這樣得到的圖，就是連通圖 G的一棵部分樹。 所謂丟邊破圈法，就是取圖 G中任意一個圈，丟去圈上任意一邊，然后重復(fù)這一步驟，直到圖中無圈為止，則剩下的圖為無圈的連通圖，就是 G的一棵部分樹。反之，若圖 G是連通圖，則 G必有部分樹。 T中的邊稱為樹枝。 4．樹的邊數(shù)恰等于樹的頂點數(shù)減 1。 2．在樹 T中去掉任意一條邊，則 T成為非連通圖。 第三節(jié) 樹 一、樹的概念及性質(zhì) 定義 如果圖 G是一個無圈的連通圖，則稱 G為樹。 定理：連通的多重圖 G是歐拉圖的充要條件是 G中無奇點。 歐拉圖：有歐拉圈的圖稱為歐拉圖。 一筆畫問題 歐拉鏈：給定
公司管理相關(guān)推薦
鄂ICP備17016276號-1