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