【正文】 判定標準 1: 在最優(yōu)郵遞路線上 ， 圖中的每一條邊至多有一條重復(fù)邊 。 若存在一條回路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條回路為歐拉回路 。 ????尋找關(guān)于 f 的最小費用增廣鏈： 構(gòu)造一個關(guān)于 f 的賦權(quán)有向圖 L(f ) ，其頂點是原網(wǎng)絡(luò) G的頂點，而將 G中的每一條弧 ( vi, vj )變成兩個相反方向的?。?vi， vj） 和 (vj , vi)， 并且定義圖中弧的權(quán) lij為： ， 令 （ vj， vi） 為原來網(wǎng)絡(luò) G中（ vi， vj） 的反向弧，令 在網(wǎng)絡(luò) G中尋找關(guān)于 f 的最小費用增廣鏈等價于在 L(f )中尋求從 vs 到 vt 的最短路。 SS, SvSv ts ?? ,S),( SS ),( SS),( SSCvs v1 v2 v4 v3 vt 3 7 4 5 5 6 3 7 8 S ),( 2vvS s? ),( 431 tvvvvS ?? ?),(,),(,),(),( 32421 vvvvvvSS s?18567),( 23241 ??????? lllSSC s2v1v3v4v5v6v7v 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) ? ?),(),(),(),( 75423121 vvvvvvVV ?設(shè) ， ? ?5211 , vvvV ? 則截集為 ? ?76432 , vvvvV ?不是該集中的弧和而 ),( ),( 5423 vvvv容量為 24 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) 設(shè) ， ? ?211 , vvV ?? 則截集為 ? ?765432 , vvvvvV ??? ?),(),(),(),( 52423121 vvvvvvVV ???容量為 20 （ 二 ） 、 求最大流的標號法 標號過程： 1． 給發(fā)點 vs 標號（ 0， +∞）。 fij＞ 0 的弧為非零流弧，fij＝ 0 的弧叫做零流弧。若購置設(shè)備，每年需支付購置費用；若繼續(xù)使用舊設(shè)備，需要支付維修與運行費用，而且隨著設(shè)備的老化會逐年增加。設(shè) P1j表示從 v1到 vj的最短路長， P1i表示從 v1到 vi的最短路長，則有下列方程： 開始時，令 即用 v1到 vj的直接距離做初始解。 0)( 1 ?vP )6,3,2()( ????? ivT i（ 2） （ 3) 3]30,m i n [])(,)(m i n [)( 12122 ??????? lvPvTvT5]50,m i n [])(,)(m i n [)( 13133 ??????? lvPvTvT3)( 2 ?vP（ 4） 4]13,5m i n [])(,)(m i n [)(23233 ????? lvPvTvT5]23,m i n [])(,)(m i n [)( 24244 ??????? lvPvTvT5]23,m i n [])(,)(m i n [)( 25255 ??????? lvPvTvTv1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 ?vP（ 5） （ 6） 8]44,6m i n [])(,)(m i n [)(35355 ????? lvPvTvT5)( 4 ?vP 5)( 5 ?vP9]45,m i n [])(,)(m i n [)( 46466 ??????? lvPvTvT7]25,m i n [])(,)(m i n [)( 56566 ??????? lvPvTvT7)( 6 ?vP（ 7） （ 8） （ 9） （ 10） 反向追蹤得 v1到 v6的最短路為： 6521 vvvv ???2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 練習 \作業(yè) :求從 1到 8的最短路徑 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1}, w1=0 min {c12,c14,c16}=min {0+2,0+1,0+3}=min {2,1,3}=1 X={1,4}, p4=1 p4=1 p1=0 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,4} min {c12,c16,c42,c47}=min {0+2,0+3,1+10,1+2}=min {2,3,11,3}=2 X={1,2,4}, p2=2 p1=0 p4=1 p2=2 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4} min {c13,c23,c25,c47}=min {0+3,2+6,2+5,1+2}=min {3,8,7,3}=3 X={1,2,4,6}, p6=3 p2=2 p4=1 p1=0 p6=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6} min {c23,c25,c47,c67}=min {2+6,2+5,1+2,3+4}=min {8,7,3,7}=3 X={1,2,4,6,7}, p7=3 p2=2 p4=1 p1=0 p6=3 p7=3 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c25,c75,c78}=min {2+6,2+5,3+3,3+8}=min {8,7,6,11}=6 X={1,2,4,5,6,7}, p5=6 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,4,6,7} min {c23,c53,c58,c78}=min {2+6,6+9,6+4,3+8}=min {8,15,10,11}=8 X={1,2,3,4,5,6,7}, p3=8 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7} min {c38,c58,c78}=min {8+6,6+4,3+7}=min {14,10,11}=10 X={1,2,3,4,5,6,7,8}, p8=10 p2=2 p4=1 p1=0 p6=3 p7=3 p5=6 p3=8 p8=10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X={1,2,3,4,6,7,8} 1到 8的最短路徑為 {1， 4， 7， 5， 8}，長度為 10。即： 最小。 最小生成樹問題 一棵生成樹所有樹枝上權(quán)的總和為這個生成樹的權(quán) 。 v1 v2 v3 v4 v5 v6 一個圖 G 有生成樹的充要條件是 G 是連通圖。 654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB?????????????????????例 權(quán)矩陣為： 鄰接矩陣為： v5 v1 v2 v3 v4 v6 4 3 3 2 2 5 6 4 3 7 654321654321 030303302021020576305020007204346040vvvvvvvvvvvvA????????????????????? 二 、 樹及最小樹問題 已知有六個城市 ， 它們之間 要架設(shè)電話線 ， 要求任意兩個城市均可以互相通話 ， 并且電話線的總長度最短 。對每一條弧 ，對應(yīng)一個數(shù) ，稱為