管理系統(tǒng)工程第十八章圖與網(wǎng)絡-全文預覽
【正文】 ????????即，? ?rjir1ij ddmi nd ??）（再構造矩陣 D(2)，令 則 D(2)給出網(wǎng)絡中任意兩點直接到達，經(jīng)過一至三個中間點時的最短距離。計劃期（五年）中每年的 li與如 Ci表 18— 1所示，工廠要制定今后五年的設備更新計劃，問采取何種方案，使總費用最小。 （ 4）重復第 3步，直到 vT點得到標號為止。對起點 vs，將 Lss=0填進 vs近旁的圓括號內(nèi)，表示vs點已標號。然后在余下圖中，重復上述過程，直到無圈為止。 一個連通圖的部分樹是不唯一的，其中使各邊權的總和最小的那棵部分樹，稱為最小部分樹。 所謂丟邊破圈法，就是取圖 G中任意一個圈，丟去圈上任意一邊，然后重復這一步驟，直到圖中無圈為止，則剩下的圖為無圈的連通圖，就是 G的一棵部分樹。 T中的邊稱為樹枝。 2．在樹 T中去掉任意一條邊，則 T成為非連通圖。 定理：連通的多重圖 G是歐拉圖的充要條件是 G中無奇點。 一筆畫問題 歐拉鏈：給定一個連通圖 G,若存在一條鏈，過每邊一次且僅一次，則稱這條鏈為歐拉鏈。 2121 EEVV ?? ，）， 222111 EV(G)EV(G ??2121 EEVV ?? ，2121 EEVV ?? ，第二節(jié) 連通圖 定義 設是一個圖， Q為 G中一個由部分頂點和邊交錯組成的非空有限序列 其中 則稱 Q為從到的一條鏈，如果 Q中，而且與重合，則稱 Q為圈（或稱閉鏈）。 應當指出，從圖 G2的頂點集合 V2中任選一些頂點，從圖 G2的邊集合 E2中任選一些邊，不一定就能組成G2的子圖 G1而只有當所有被選入 G1的邊的端點也都被選入 G1時， G1才是 G2的子圖。 定理 2 在任一圖中，奇點的個數(shù)必為偶數(shù)。 （ 9）若 d（ v） =0，則稱 v為孤立點。 （ 5）若兩點之間多于一條邊，稱之為多重邊。 例 18— 1 圖 18— 4中的圖可表示為 G=（ V， E），其中 ? ?? ?987654321654321e,e,e,e,e,e,e,e,eEv,v,v,v,v,vV??定義 設 G=（ V， E） （ 1）圖 G中含頂點的個數(shù)，記為 p（ G），稱 為圖 G的階；圖 G中含邊的條數(shù)，記為 q（ G），稱為圖的邊數(shù)。 —— 一筆畫問題 2. 中國郵遞員問題 郵遞員送信送報要走完全部所負責的街道，最后回到郵局，如何走路程最短？ 第一節(jié) 圖的基本概念 一、圖的概念 定義 圖是由點與邊組成的集合，記為 G=(V， E)，其中 V表示圖 G中點的集合，是一個非空集合，記為 V（ G），這些點稱為頂點， E表示圖 G中邊的集合，記為 E（ G）。 （ 4）若 e的兩個端點重合，則稱 e為環(huán)。 （ 8）若 d（ v） =1，則稱 v為懸掛點，與懸掛點 相關聯(lián)的邊稱為懸掛邊。即 這是顯然的，因為在計算各點的次時，每條邊都用過兩次，所以，所有頂點次的和等于邊數(shù)的兩倍。 三、子圖 定義 設 ， 如果 ，則稱 G1是 G2的子圖。例如圖 18— 6（ c）就是圖 18— 6（ a）的一個真子圖。 ? ?kk iiiiii veevevQ ， 12211 ?? ?），（， 1k321r]vv[e 1rrr iii ??? ? ?定義 如果在圖中的任何兩個頂點之間都至少有一條連接這兩個頂點的鏈，則稱圖 G為連通圖，否則，稱 G為非連通圖。 能一筆畫的圖一定是歐拉圈或含有歐拉鏈。 關于樹 T，具有下列性質(zhì)： 1．在樹 T中，任意兩個頂點之間必有一條且僅有一條鏈。 二、圖的部分樹 定義 如果圖的部分圖是樹，其中，則稱 T為 G的一個部分樹（或生成樹）。 用丟邊破圈法，可找出連通圖 G的部分樹。 三、最小部分樹 定義 若圖 G的每一條邊 （ vi， vj) 都相應地有一個數(shù)wij，則稱這樣的圖 G為賦權圖， wij稱為邊 （ vi， vj) 上的權。 算法 Ⅱ （破圈法）：其基本思想是，從
公司管理相關推薦
鄂ICP備17016276號-1