管理系統(tǒng)工程第十八章圖與網(wǎng)絡(luò)-wenkub.com
2025-01-06 05:27 本頁面
【正文】 例： 電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問如何架設(shè)使其光纜線路最短？圖 76給出了甲、乙兩地間的交通圖，圖中的點(diǎn) v1 ， v2 ， … ， v7表示 7個(gè)地名，其中 v1表示甲地， v7表示乙地，點(diǎn)之間的聯(lián)線（邊）表示兩地之間的公路，邊的賦權(quán)數(shù)表示兩地間公路的長度（單位為公里）。這樣得到一個(gè)新的可行流，對(duì)新的可行流重新轉(zhuǎn)入標(biāo)號(hào)過程。 先給發(fā)點(diǎn) vS標(biāo)號(hào)，即 ，然后從已標(biāo)號(hào)點(diǎn) vi出發(fā)，找出與之相鄰的未標(biāo)號(hào)點(diǎn) vj，考慮： （ 1）如果連接 vi與 vj的弧（ vi， vj）是前向弧，且 ，則給 vj標(biāo)號(hào)，即 。 定理 3：可行流 f是最大流的充分與必要條件是不存在關(guān)于 f的增廣鏈。 定義 設(shè)有 D中一條從 vS到 vT的鏈 μ ，如果 μ 的所有前向弧是非飽和弧， μ 的所有后向弧為非零流弧，則稱 μ 為增廣鏈。 fijCij的弧（ vi， vj）為非飽和弧。 （ 3）對(duì)于發(fā)點(diǎn) vS，收點(diǎn) vT，有 其中 v（ f）為非負(fù)數(shù)，稱為可行流的流量。對(duì)于有多個(gè)發(fā)（收）點(diǎn)的網(wǎng)絡(luò)，只要假設(shè)一個(gè)總發(fā)（收）點(diǎn)，并分別與各發(fā)（收）點(diǎn)連起來，這樣多個(gè)發(fā)（收）點(diǎn)的網(wǎng)絡(luò)問題就轉(zhuǎn)化為單個(gè)發(fā)（收）點(diǎn)的網(wǎng)絡(luò)問題了。 一、基本概念 1．容量 在 D=（ V， A）上的每條?。?vi， vj），都規(guī)定對(duì)應(yīng)一個(gè)正數(shù) Cij，稱為?。?vi， vj）的容量，在運(yùn)輸網(wǎng)絡(luò)中 Cij表示?。?vi， vj）的最大通過能力。問中心倉庫應(yīng)建在那個(gè)分廠，能使每月總的運(yùn)輸量最小。 用避圈法或破圈法求出最小部分樹見圖。設(shè)點(diǎn)v1— v7為某公司的 7個(gè)分廠，邊表示經(jīng)過測繪的交通路線，邊旁的數(shù)字表示兩點(diǎn)之間的距離。 ),...,2,1(),()()(1njvvdvwvgnijiij ?? ??? ?)(m in)( jVv vgvgj ??v例：上例中， v1， v2， v3， v4， v5， v6， v7為七個(gè)村子，現(xiàn)決定要辦一所小學(xué)，已知各村學(xué)生人數(shù)分別為： v1—— 30， v2—— 40， v3—— 25， v4——20， v5—— 50， v6—— 60, v7—— 60， 問小學(xué)應(yīng)建在那個(gè)村子，使學(xué)生上學(xué)走的路程最短。 一般， 矩陣給出網(wǎng)絡(luò)中任意兩點(diǎn)直接到達(dá)，經(jīng)過一個(gè)，兩個(gè)， … ，到個(gè)中間點(diǎn)時(shí)比較得到的最短距離。表 18— 1 2．矩陣計(jì)算法例 6 網(wǎng)絡(luò)圖如圖 18— 15所示，用矩陣計(jì)算法求各點(diǎn)之間的最短距離。 rsrpsrspsssp ]dLdLm in[L， ???例 4 求如圖 18— 15所示的網(wǎng)絡(luò)圖中 v1到 v6的最短距離及其路線。 （ 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)。 例 :某工廠內(nèi)聯(lián)結(jié)六個(gè)車間的道路網(wǎng)如圖所示，已知每條道路的長，要求沿道架設(shè)聯(lián)結(jié)六個(gè)車間的電話線網(wǎng)，使電話線的總長最小。 )EV(T ?? ? ，)EV(G ，?設(shè)有一個(gè)賦權(quán)的連通圖 ，求 G的一棵部分樹 ，使 取得最小值。 也可以用避圈法找 G的部分樹。 由這個(gè)定義，顯然可以得到：若圖 G有部分樹，則 G必定是連通圖。 3．在樹 T中不相鄰的兩個(gè)頂點(diǎn)之間添上一條邊，恰好構(gòu)成一個(gè)圈。 推論：連通的多重圖 G有歐拉鏈的充要條件是 G中恰有兩個(gè)奇點(diǎn)。 歐拉圈：若存在一個(gè)簡單圈，過每邊一次，則稱這個(gè)圈為歐拉圈。如果鏈（圈） Q中含的邊均不相同，則稱 Q為簡單鏈（圈）。并且： （ 1）若 ,則稱 G1是 G2的一個(gè)部分圖，例如圖 18— 6（ b）就是圖 18— 6（ a）的一個(gè)部分圖。 ???Vvq2)v(d二、圖的同構(gòu) 定義 設(shè)是兩個(gè)圖，如果頂點(diǎn)集合 V1與 V2之間以及邊的集合 E1與 E2之間都建立了一一對(duì)應(yīng)關(guān)系，并且圖形的兩頂點(diǎn)之間的邊對(duì)應(yīng)于另一圖形對(duì)應(yīng)頂點(diǎn)的邊，則稱圖 G1與圖 G2是同構(gòu)的。 （ 10）若 d（ v） =奇數(shù)，則稱
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1