管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)-文庫(kù)吧
2024-12-25 05:27 本頁(yè)面
【正文】 次，則稱這條鏈為歐拉鏈。 歐拉圈：若存在一個(gè)簡(jiǎn)單圈，過(guò)每邊一次，則稱這個(gè)圈為歐拉圈。 歐拉圖：有歐拉圈的圖稱為歐拉圖。 能一筆畫(huà)的圖一定是歐拉圈或含有歐拉鏈。 定理：連通的多重圖 G是歐拉圖的充要條件是 G中無(wú)奇點(diǎn)。 推論：連通的多重圖 G有歐拉鏈的充要條件是 G中恰有兩個(gè)奇點(diǎn)。 第三節(jié) 樹(shù) 一、樹(shù)的概念及性質(zhì) 定義 如果圖 G是一個(gè)無(wú)圈的連通圖，則稱 G為樹(shù)。 關(guān)于樹(shù) T，具有下列性質(zhì)： 1．在樹(shù) T中，任意兩個(gè)頂點(diǎn)之間必有一條且僅有一條鏈。 2．在樹(shù) T中去掉任意一條邊，則 T成為非連通圖。 3．在樹(shù) T中不相鄰的兩個(gè)頂點(diǎn)之間添上一條邊，恰好構(gòu)成一個(gè)圈。 4．樹(shù)的邊數(shù)恰等于樹(shù)的頂點(diǎn)數(shù)減 1。 二、圖的部分樹(shù) 定義 如果圖的部分圖是樹(shù)，其中，則稱 T為 G的一個(gè)部分樹(shù)（或生成樹(shù)）。 T中的邊稱為樹(shù)枝。 由這個(gè)定義，顯然可以得到：若圖 G有部分樹(shù)，則 G必定是連通圖。反之，若圖 G是連通圖，則 G必有部分樹(shù)。 用丟邊破圈法，可找出連通圖 G的部分樹(shù)。 所謂丟邊破圈法，就是取圖 G中任意一個(gè)圈，丟去圈上任意一邊，然后重復(fù)這一步驟，直到圖中無(wú)圈為止，則剩下的圖為無(wú)圈的連通圖，就是 G的一棵部分樹(shù)。 也可以用避圈法找 G的部分樹(shù)。 所謂避圈法，就是在連通圖 G中任意取一邊 e1，找一條不與 e1構(gòu)成圈的邊 e2，然后再找一條不與 {e1， e2}構(gòu)成圈的 e3，這樣繼續(xù)下去，直到這一過(guò)程不能進(jìn)行時(shí)為止，這樣得到的圖，就是連通圖 G的一棵部分樹(shù)。 三、最小部分樹(shù) 定義 若圖 G的每一條邊 （ vi， vj) 都相應(yīng)地有一個(gè)數(shù)wij，則稱這樣的圖 G為賦權(quán)圖， wij稱為邊 （ vi， vj) 上的權(quán)。 一個(gè)連通圖的部分樹(shù)是不唯一的，其中使各邊權(quán)的總和最小的那棵部分樹(shù)，稱為最小部分樹(shù)。 )EV(T ?? ? ，)EV(G ，?設(shè)有一個(gè)賦權(quán)的連通圖 ，求 G的一棵部分樹(shù) ，使 取得最小值。 ? ?? ??? ? Tvv ijji w)T(w ，求最小部分樹(shù)的兩種方法 算法 Ⅰ （ Kruskal算法）：其基本思想是，每一步從未選的邊中，選一條具有最小權(quán)的邊，使與已選的邊不構(gòu)成圈，直到每一條邊都選查過(guò)為止。 算法 Ⅱ （破圈法）：其基本思想是，從 G中任選一個(gè)圈，去掉圈上權(quán)最大的邊。然后在余下圖中，重復(fù)上述過(guò)程，直到無(wú)圈為止。 例 :某工廠內(nèi)聯(lián)結(jié)六個(gè)車間的道路網(wǎng)如圖所示，已知每條道路的長(zhǎng)，要求沿道架設(shè)聯(lián)結(jié)六個(gè)車間的電話線網(wǎng)，使電話線的總長(zhǎng)最小。 第四節(jié) 最短路問(wèn)題 1．狄克斯特拉（ Dijkstra）算法 步驟如下： （ 1）對(duì)起點(diǎn) vs進(jìn)行標(biāo)號(hào)。每個(gè)標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)包含兩部分，前者表示它的標(biāo)號(hào)是從哪一點(diǎn)來(lái)的；后者表示從起點(diǎn) vs到該點(diǎn)的最短距離。對(duì)起點(diǎn) vs，將 Lss=0填進(jìn) vs近旁的圓括號(hào)內(nèi)，表示vs點(diǎn)已標(biāo)號(hào)。 （ 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)。 （ 3）從已標(biāo)號(hào)的頂點(diǎn)出發(fā)，找出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)。若 式中 vs， vr為已標(biāo)點(diǎn)， vp為未標(biāo)號(hào)點(diǎn)，則對(duì) vp進(jìn)行標(biāo)號(hào)。 （ 4）重復(fù)第 3步，直到 vT點(diǎn)得到標(biāo)號(hào)為止。 rsrpsrspsssp ]dLdLm in[L， ???例 4 求如圖 18— 15所示的網(wǎng)絡(luò)圖中 v1到 v6的最短距離及其路線。 例 5 某廠使用一種設(shè)備，每年年初都要決定該設(shè)備是否需要更新。若購(gòu)買新設(shè)備，每年需支付購(gòu)置費(fèi)用（第 i年的購(gòu)置費(fèi)設(shè)為 li）；若繼續(xù)使用舊設(shè)備，則要支付維修與運(yùn)行費(fèi)用（第 i年的維修與運(yùn)行費(fèi)為 Ci）。計(jì)劃期（五年）中每年的 li與如 Ci表 18— 1所示，工廠要制定今后五年的設(shè)備更新計(jì)劃，問(wèn)采取何種方案，使總費(fèi)用最小。表 18— 1 2．矩陣計(jì)算法例 6 網(wǎng)絡(luò)圖如圖 18— 15所示，用矩陣計(jì)算法求各點(diǎn)之間的最短距離。 解 設(shè) dij表示相鄰兩點(diǎn) vi與 vj間的距離，若 vi與 vj不相鄰時(shí)，令 dij=∞ 。 ????????????
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1