【正文】 弧上的 “ 權(quán) ” 。度為奇數(shù)的點稱為奇點，度為偶數(shù)的點稱為偶點。一條方向從 vi指向 vj 的弧，記作 (vi , vj)。 有 7個人圍桌而坐 ， 如果要求每次相鄰的人都與以前完全不同 ， 試問不同的就座方案共有多少種 ？ 用頂點表示人 ， 用邊表示兩者相鄰 ， 因為最初任何兩個人都允許相鄰 ， 所以任何兩點都可以有邊相連 。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個圖是由點集 和 中元素的無序?qū)Φ囊粋€集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點 ， V 表示圖 G 的點集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 有向完全圖則是指任意兩個頂點之間有且僅有一條有向邊的簡單圖。 有向圖中 ， 以 vi 為始點的邊數(shù)稱為點 vi的出次 ， 用 表示 ；以 vi 為終點的邊數(shù)稱為點 vi 的入次 ， 用 表示； vi 點的出次和入次之和就是該點的次 。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點均不相同的鏈稱為初等鏈 , 也稱通路。 （ 3） 樹 中任意兩個頂點之間，恰有且僅有一條鏈（初等鏈）。 用破圈法求出下圖的一個生成樹。 6 5 5 1 7 2 3 4 4 v1 v2 v3 v4 v5 v6 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 36 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 20 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 15 9 16 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 25 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 28 17 4 1 23 v1 v7 v4 v3 v2 v5 v6 9 3 17 4 1 23 總造價 =1+4+9+3+17+23=57 v1 v2 v3 v4 v5 1 4 2 3 1 3 5 2 避圈法 ：開始選一條 權(quán)最小 的邊 ， 以后每一步中 ，總從未被選取的邊中選一條權(quán)盡可能小 ， 且與已選邊不構(gòu)成圈的邊 。若全部節(jié)點均為 P標(biāo)號，則停止，否則用 vk代替 vi， 返回步驟（ 2）。本例中 V1 到 V8 的最短路線是： v1 → v 2 → v 5→ v 6 → v 8 1v2v3v4v5v9v8v7v6v6 2 3 1 2 1 6 4 10 3 6 2 3 4 2 10 1v 3v 2v 5v 8v（二）、 逐次逼近法 算法的基本思路與步驟： 首先設(shè)任一點 vi到任一點 vj都有一條弧。 求解步驟： 1） 畫賦權(quán)有向圖： 設(shè) Vi 表示第 i年初 ， (Vi ,Vj )表示第 i 年初購買新設(shè)備用到第 j年初 （ j1年底 ） ， 而 Wi j 表示相應(yīng)費用 ，則 5年的一個更新計劃相當(dāng)于從 V1 到 V6的一條路 。 網(wǎng)絡(luò) D上的流，是指定義在弧集合 E上的一個函數(shù) 其中 f(vi ,vj) =fij 叫做弧 (vi， vj)上的流量。 即 中的每一條弧都是非飽和弧 ??即 中的每一條弧都是非零流弧 ??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) ? ?7766633232211 ),(,),(,),(,),(, vvvvvvvvvvvvv??? ?),(),(),( 766321 vvvvvv??? ? ?),( 23 vv????是一個增廣鏈 顯然圖中增廣鏈不止一條 容量網(wǎng)絡(luò) G =（ V， E， C） ， vs為始點 ，vt為終點 。 ?? ?? ???? ?jiji ddfd )(若 * 是從 vs到 vt的增廣鏈中費用最小的增廣鏈，則稱 * 是最小費用增廣鏈。 （ 4） 如果存在最短路 ， 則在可行流 f (k－ 1)的圖中得到與此最短路相對應(yīng)的增廣鏈 ， 在增廣鏈上 ， 對 f (k－ 1)進(jìn)行調(diào)整 ， 調(diào)整量為： ?????? ?? ???? )(m i n,)(m i nm i n)1()1( kjikjiji ffc ??????????????????????????),(),(),()1()1()1()(jikjijikjijikjikjivvfvvfvvff令 得到新可行流 f (k) 。 （ 2） 如果邊 e=（ u,v） 上的重復(fù)邊多于一條 ， 則可從重復(fù)邊中去掉偶數(shù)條 ， 使得其重復(fù)邊至多為一條 ， 圖中的頂點仍全部都是偶頂點 。 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 6 4 3 4 5 5 l12+2 l23+2 l36+2 l89+2 l78+l69+l14+2 l47=51 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 v1 v2 v3 v4 v5 v6 v7 v8 v9 2 4 3 4 4 9 5 5 6 4 3 4 。 推論 一個多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個奇點 。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 Evv ij ?),( 0?ijf),( jiv ?? ),m i n ( iijj f ?? ?Evv ji ?),( ijij cf ?),( jiv ?? ),m i n ( ijijij fc ?? ??調(diào)整過程 設(shè) 1． 令 2． 去掉所有標(biāo)號 ， 回到第一步 ， 對可行流重新標(biāo)號 。 f 是一個可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關(guān)于 f 的一條增廣鏈。 對于 D中的每一個弧 （ vi , vj） ∈ E ,都有一個非負(fù)數(shù) cij,叫做弧的容量 。 解： （ 1） 分析：可行的購置方案 （ 更新計劃 ） 是很多的 ， 如： 1） 每年購置一臺新的 ， 則對應(yīng)的費用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購置新的 ， 一直用到第五年年底 ， 則總費用為： 11+5+6+8+11+18 = 59 顯然不同的方案對應(yīng)不同的費用。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長，同時也求出了從 V1 到 任意一點 的最短路長。 vi 為剛得到 P標(biāo)號的點，考慮點 vj， 其中 ，且 vj為 T標(biāo)號。 破圈法 ：在原圖中 ， 任選一個圈 ， 從圈中去掉權(quán)最大 的一條邊 。 ),( 1EVK ?),( 1EVK ?（一） 破圈法：在圖中任選一個圈，從這個圈中去掉一條邊。 樹的性質(zhì)： （ 1） 樹必連通，但無回路（圈）。 如 :v0 ， e1， v1， e2， v2， e3 ， v3 ,… ,vn1 , en ， vn， 記作（ v0 ， v1 ， v2， v3 , … , vn1 ， vn ）， e3 v1 v2 v3 v4 v5 v6 e7 e8 e1