【正文】 是該點的次 。 以點 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)。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個圖是由點集 和 中元素的無序?qū)Φ囊粋€集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點 ， V 表示圖 G 的點集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 ? ?jvV ? }{ keE ?jvke Vv1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 例 ? ?654321 , vvvvvv? },{ 10987654321 eeeeeeeeeeE ，?},{ 211 vve ? },{ 212 vve ? },{ 323 vv 434 ,315e ? },{ 536 vve ? },{ 537 vv , 658 , 669e ? },{ 6110 vve ?圖 1 如果一個圖是由點和邊所構(gòu)成的 ， 則稱其為無向圖 ， 記作G = (V， E)， 連接點的邊記作 [vi , vj]， 或者 [vj , vi]。 如果兩個端點之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀? v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 度為零的點稱為弧立點，度為 1的點稱為懸掛點。 )(vd圖中 d(v1)= 4， d(v6)= 4（ 環(huán)計兩度 ） 定理 1 所有頂點度數(shù)之和等于所有邊數(shù)的 2倍。 )( id ? )( i? 設(shè) G1=（ V1 , E1 ）， G2 =（ V2 ,E2 ） 如果 V2 ?V1 , E2 ?E1 稱 G2 是 G1 的子圖；如果 V2 = V1 , E2 ?E1 稱 G2 是 G1 的部分圖或支撐子圖。 Avv ji ?),(jiw 由兩兩相鄰的點及其相關(guān)聯(lián)的邊構(gòu)成的點邊序列稱為鏈。 （ 二 ） 、 圖的矩陣表示 對于網(wǎng)絡(luò) （ 賦權(quán)圖 ） G=（ V， E） ， 其中邊 有權(quán) ， 構(gòu)造矩陣 ， 其中： 稱矩陣 A為網(wǎng)絡(luò) G的權(quán)矩陣 。 樹中次為 1的點稱為樹葉，次大于 1的點稱為分支點。 （ 4）樹 連通，但去掉任一條邊， 必變?yōu)椴贿B通。 ),( 1EVK ?一個圖 G 有生成樹的充要條件是 G 是連通圖。 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 最小生成樹問題 如果圖 是圖 G的一個生成樹 ， 那么稱 E1上所有邊的權(quán)的和為生成樹 T 的權(quán) ， 記作 S(T)。即： 最小。對 vj的 T標號進行如下修改： T標號的節(jié)點，把最小者改為 P標號，即： 當存在兩個以上最小者時，可同時改為 P標號。 0)( 1 ?v)6,3,2()( ????? ivT i（ 2） （ 3） 3]30,min[])(,)(min[)( 12122 ??????? lvPvTvT 5]50,min[])(,)(min[) 13133 ??????? lvPvT3)( 2 ?vP（ 4） 4]13,5min[])(,)(min[)( 23233 ????? lvPvTvT 5]23,min[])(,)(min[)( 24244 ??????? lvPvTv 5]23,min[])(,)(min[) 25255 ??????? lvPvTTv1 v2 v3 v4 v6 v5 3 5 2 2 4 2 4 2 1 4)( 3 ?vP（ 5） （ 6） 8]44,6min[])(,)(min[)( 35355 ????? lvPvTvT 5)( 4 ?vP 5)( 5 ?vP 9]45,min[])(,)(min[)( 46466 ??????? lvPvTvT 7]25,min[])(,)()(56566 ?????l7)( 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 求從 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。將從V1 到 任一點的最短路權(quán)標在圖上，即可求出從 V1 到 任一點的最短路線。 設(shè) P1j表示從 v1到 vj的最短路長 ， P1i表示從 v1到vi的最短路長 ， 則有下列方程： 開始時 ， 令 即用 v1到 vj的直接距離做初始解 。 第 i年度 1 2 3 4 5 購置費 11 11 12 12 13 設(shè)備役齡 01