管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)-在線瀏覽
2025-02-26 05:27本頁(yè)面
【正文】 單圈，過(guò)每邊一次，則稱這個(gè)圈為歐拉圈。 能一筆畫(huà)的圖一定是歐拉圈或含有歐拉鏈。 推論：連通的多重圖 G有歐拉鏈的充要條件是 G中恰有兩個(gè)奇點(diǎn)。 關(guān)于樹(shù) T，具有下列性質(zhì)： 1．在樹(shù) T中，任意兩個(gè)頂點(diǎn)之間必有一條且僅有一條鏈。 3．在樹(shù) T中不相鄰的兩個(gè)頂點(diǎn)之間添上一條邊，恰好構(gòu)成一個(gè)圈。 二、圖的部分樹(shù) 定義 如果圖的部分圖是樹(shù)，其中，則稱 T為 G的一個(gè)部分樹(shù)（或生成樹(shù)）。 由這個(gè)定義，顯然可以得到：若圖 G有部分樹(shù)，則 G必定是連通圖。 用丟邊破圈法，可找出連通圖 G的部分樹(shù)。 也可以用避圈法找 G的部分樹(shù)。 三、最小部分樹(shù) 定義 若圖 G的每一條邊 （ vi， vj) 都相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖 G為賦權(quán)圖， wij稱為邊 （ vi， vj) 上的權(quán)。 )EV(T ?? ? ，)EV(G ，?設(shè)有一個(gè)賦權(quán)的連通圖 ，求 G的一棵部分樹(shù) ，使 取得最小值。 算法 Ⅱ （破圈法）：其基本思想是，從 G中任選一個(gè)圈，去掉圈上權(quán)最大的邊。 例 :某工廠內(nèi)聯(lián)結(jié)六個(gè)車(chē)間的道路網(wǎng)如圖所示，已知每條道路的長(zhǎng)，要求沿道架設(shè)聯(lián)結(jié)六個(gè)車(chē)間的電話線網(wǎng)，使電話線的總長(zhǎng)最小。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分，前者表示它的標(biāo)號(hào)是從哪一點(diǎn)來(lái)的；后者表示從起點(diǎn) vs到該點(diǎn)的最短距離。 （ 2）從 vS點(diǎn)出發(fā)，找出與 vS相鄰的頂點(diǎn)中距離最小的一個(gè) vr，將 Lsr=Lss+dsr的值填入 vr近旁圓括號(hào)內(nèi)，表示 vr已經(jīng)標(biāo)號(hào)。若 式中 vs， vr為已標(biāo)點(diǎn)， vp為未標(biāo)號(hào)點(diǎn)，則對(duì) vp進(jìn)行標(biāo)號(hào)。 rsrpsrspsssp ]dLdLm in[L， ???例 4 求如圖 18— 15所示的網(wǎng)絡(luò)圖中 v1到 v6的最短距離及其路線。若購(gòu)買(mǎi)新設(shè)備，每年需支付購(gòu)置費(fèi)用（第 i年的購(gòu)置費(fèi)設(shè)為 li）；若繼續(xù)使用舊設(shè)備，則要支付維修與運(yùn)行費(fèi)用（第 i年的維修與運(yùn)行費(fèi)為 Ci）。表 18— 1 2．矩陣計(jì)算法例 6 網(wǎng)絡(luò)圖如圖 18— 15所示，用矩陣計(jì)算法求各點(diǎn)之間的最短距離。 ????????????????????666564636261565554535251464544434241353534333231262524232221161514131211dddddddddddddddddddddddddddddddddddd?????????????????????????????????043402313203302313204340 先考慮 vi與 vj之間有一個(gè)中間點(diǎn)情況，如圖 18— 15中的最短距離為 為此可以構(gòu)造一個(gè)新的矩陣 D(1)，令 D(1)，中每個(gè)元素為 則矩陣 D(1)給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)和經(jīng)過(guò)一個(gè)中間點(diǎn)時(shí)的最短距離。 一般， 矩陣給出網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，經(jīng)過(guò)一個(gè)，兩個(gè)， … ，到個(gè)中間點(diǎn)時(shí)比較得到的最短距離。 ? ?),(m a x)( jiVvivvdvdj ??? ?)(m in)( iVv vdvdi ?? ?求中心 村莊之間的最短距離 dij * 村莊 max v1 v2 v3 v4 v5 v6 v7 v1 10 0 5 2 7 7 6 10 v2 8 5 0 7 2 5 4 8 v3 7 2 7 0 6 5 4 8 v4 7 7 2 6 0 3 2 6 v5 7 7 5 5 3 0 1 3 v6 6* 6 4 4 2 1 0 4 v7 10 10 8 8 6 3 4 0 求重心 在一個(gè)連通圖 G中，設(shè) w(vi)為點(diǎn) vi的權(quán)重，令 表示將點(diǎn) vi的物資運(yùn)到點(diǎn) vj的總運(yùn)輸量。 ),...,2,1(),()()(1njvvdvwvgnijiij ?? ??? ?
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1