【正文】 稱這條路為歐拉道路 。 如果存在一個圈 ， 重復(fù)邊的總長大于該圈總長的一半時 ， 則將這個圈中的重復(fù)邊去掉 ， 再將該圈中原來沒有重復(fù)邊的各邊加上重復(fù)邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 判定標(biāo)準(zhǔn) 2 : 在最優(yōu)郵遞路線上 ， 圖中每一個圈的重復(fù)邊總權(quán)小于或等于該圈總權(quán)的一半 。 具有歐拉回路的圖稱為歐拉圖 。 ??????????jijijijijiji cfcfdl當(dāng)當(dāng)???????????00jijijiij ffdl當(dāng)當(dāng)Evv ji ?),(步驟： （ 1）取零流為初始可行流 ， f (0) ={0}。 2． 取一個已標(biāo)號的點 vi， 對于 vi一切未標(biāo)號的鄰接點 vj 按下列規(guī)則處理： （ 1）如果邊 ，且 ，那么給 vj 標(biāo)號 ，其中： （ 2） 如果邊 ， 且 ， 那么給 vj 標(biāo)號 ， 其中： 3． 重復(fù)步驟 2， 直到 vt被標(biāo)號或標(biāo)號過程無法進(jìn)行下去 ， 則標(biāo)號結(jié)束 。 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 圖中 為零流弧，其余為非飽和弧。計劃期（五年）內(nèi)中每年的購置費、維修費與運行費如表所示，工廠要制定今后五年設(shè)備更新計劃，問采用何種方案才能使包括購置費、維修費與運行費在內(nèi)的總費用最小。 從第二步起，使用遞推公式： 求 ，當(dāng)進(jìn)行到第 t步，若出現(xiàn) 則停止計算， 即為 v1到各點的最短路長。 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 求從 V1 到 V8 的最短路線 。 ),( EVG ?jil ???jil ts vv ,? sv),( ji vv ji vv ,tv?????),()(ji vvjilL(一 )、 狄克斯屈拉 (Dijkstra)算法 適用于 wij≥0， 給出了從 vs到任意一個點 vj的最短路 。 具有最小權(quán)的生成樹 ， 稱為最小生成樹 。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 設(shè)圖 是圖 G=(V , E )的一支撐子圖， 如果圖 是一個樹 ,那么稱 K 是 G 的一個生成樹（支撐樹），或簡稱為圖 G 的樹。 v1 v2 v3 v4 v5 v6 一個連通的無圈的無向圖叫做樹。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。 以點 v為端點的邊的個數(shù)稱為點 v 的度（次），記作 。 v4 v6 v1 v2 v3 v5 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 圖 2 一條邊的兩個端點是相同的 ,那么稱為這條邊是環(huán)。 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 1 2 3 7 6 4 5 得到第一次就座方案是（ 1， 2， 3， 4，5， 6， 7， 1），繼續(xù)尋求第二次就座方案時就不允許這些頂點之間繼續(xù)相鄰，因此需要從圖中刪去這些邊。 1 2 3 7 6 4 5 引論 圖的用處 某公司的 組織機構(gòu)設(shè)置圖 總公司 分公司 工廠或辦事處 一、 圖與網(wǎng)絡(luò)的基本知識 （一）、 圖與網(wǎng)絡(luò)的基本概念 E A D C B 一個圖是由點和連線組成。 每一對頂點間都有邊相連的無向簡單圖稱為完全圖。 所有頂點的入次之和等于所有頂點的出次之和。 其鏈長為 n ， 其中 v0 ， vn 分別稱為鏈的起點和終點 。 （ 2） n 個頂點的樹必有 n1 條邊 。在余下的圖中重復(fù)這個步驟，直到得到一不含圈的圖為止。 在余下的圖中重復(fù)這個步驟 ，直到得到一不含圈的圖為止 。對 vj的 T標(biāo)號進(jìn)行如下修改： T標(biāo)號的節(jié)點，把最小者改為 P標(biāo)號，即： 當(dāng)存在兩個以上最小者時，可同時改為 P標(biāo)號。將從V1 到 任一點的最短路權(quán)標(biāo)在圖上，即可求出從 V1 到 任一點的最短路線。 第 i年度 1 2 3 4 5 購置費 11 11 12 12 13 設(shè)備役齡 01 12 23 34 45 維修費用 5 6 8 11 18 （ 2） 方法：將此問題用一個賦權(quán)有向圖來描述 ， 然后求這個賦權(quán)有向圖的最短路 。 我們把這樣的圖 D叫做一個容量網(wǎng)絡(luò) ， 簡稱網(wǎng)絡(luò) ， 記做 D=（ V， E， C） 。 ?? ? ???? ?????????????????),(0),(0jijijijijijivvcfvvcf?推論 可行流 f 是最大流的充分必要條件是不存在從 vs到 vt 的關(guān)于 f 的一條可增廣鏈。 }),(m i n {1 ???? ?? jijiji vvfc}),(m i n{2 ??? ?? jiji vvf),m i n ( 21 ??? ??????????????? ???????),(),(),(jijijijijijijivvfvvfvvff 求下圖所示網(wǎng)絡(luò)中的最大流，弧旁數(shù)為 ),( jiji fc(1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) (1 ,1) v2 v1 v4 v3 vs vt (3 , 3) (5 , 1) (1 , 1) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,1) （ 0， +∞） （ v1, 1） （ + vs , 4） （ v2 ， 1） （ +v2， 1） (+ v3 ， 1) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) (1 ,0) v2 v1 v4 v3 vs vt (3 , 3) (5 , 2) (1 , 0) (4 ,3) (2 , 2) (3 ,0) (5 ,3) (2 ,2) （ 0， +∞） （ + vs , 3） )},(,),{( 4321 ts vvvvvv最小截集 2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 2v1v3v4v5v6v7v 13 (11) 9 (9) 4 (0) 5 (5) 6(6) 5 (5) 5 (4) 5 (4) 4 (4) 4 (3) 9 (9) 10 (7) 截集 1 截集 2 最小截量為： 9+6+5=20 1sv2v2sv1v1tv2tv3v70（ 70） 70（ 50） 130（ 100） 150（ 130） 150（ 150） 50（ 20） 50（ 50） 120（ 30） 100（ 100） svtv∞ （ 120 ） ∞ （ 230 ） ∞ （ 150 ） ∞ （ 200 ） 第五節(jié) 最小費用最大流問題 定義 已知網(wǎng)絡(luò) G =（ V， E， C， d） ， f是 G上的一個可行流 ， 為一條從 vs到 vt的增廣鏈 ， 稱為鏈的費用 。 若不存在最短路 ， 則 f (k1)就是最小費用最大流；否則轉(zhuǎn) (4)。 A B C D 二、 奇偶點圖上作業(yè)法 （ 1） 找出圖 G中的所有的奇頂點 ， 把它們兩兩配成對 ， 而每對奇點之間必有一條通路 ， 把這條通路上的所有邊作為重復(fù)邊追加到圖中去 ， 這樣得到的新連通圖必?zé)o奇點