【正文】 有 對(duì)于收點(diǎn) vt ， 有 對(duì)于中間點(diǎn)，有 ? ?? ???Evv Evvsjjsjs sjWff),( ),( ?? ? ???Evv Evv tjjtjt tj Wff),( ),(? ?? ? ??Evv Evv ijjiji ijff),( ),(0可行流中 fij＝ cij 的弧叫做飽和弧， fij＜ cij的弧叫做非飽和弧。 截集 中所有弧的容量之和 ，稱為這個(gè)截集的容量 ， 記為 。當(dāng) f * 是最大流時(shí)，就是最小費(fèi)用最大流。 例 求網(wǎng)絡(luò)的最小費(fèi)用最大流，弧旁權(quán)是（ bij , cij） (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 3 vs v2 v1 vt v3 1 6 4 1 2 2 (1) L(f (0)) (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) 0 vs v2 v1 vt v3 3 0 0 3 3 3 (2) f ( 1) ?1=3 W(f(1))=3 － 1 (3) L(f (1)) － 2 3 vs v2 v1 vt v3 1 6 4 1 2 － 1 － 2 1 vs v2 v1 vt v3 4 0 0 3 4 3 (4 ) f ( 2) ?2=1 W(f(2))=4 (3 ,2) vs v2 v1 vt v3 (1 ,4) (6 ,7) (4 ,8) (1 ,6) (2 ,5) (2 ,3) (5) L(f (2)) － 3 vs v2 v1 vt v3 － 1 4 1 2 － 2 － 2 3 － 1 6 6 1 vs v2 v1 vt v3 4 0 1 4 5 3 (6 ) f ( 3) ?3=1 W(f(3))=5 (7) L(f (3)) vs v2 v1 vt v3 － 3 － 1 4 1 2 － 2 3 － 1 6 1 vs v2 v1 vt v3 4 3 4 4 5 0 (8 ) f ( 4) ?4=3 W(f(4))=8 0 vs v2 v1 vt v3 4 4 5 5 5 0 ?5=1 W(f(5))=9 (10 )f ( 5) － 1 2 3 － 1 vs v2 v1 vt v3 － 3 4 1 2 6 (9) L( f ( 4)) 4 6 3 － 1 2 － 1 4 (11) L( f ( 5)) 1 2 6 － 4 vs v2 v1 vt v3 － 6 第六節(jié) 中國(guó)郵遞員問題 一 、 歐拉回路與道路 定義 連通圖 G中 ， 若存在一條道路 ， 經(jīng)過每邊一次且僅一次 ， 則稱這條路為歐拉道路 。 如果存在一個(gè)圈 ， 重復(fù)邊的總長(zhǎng)大于該圈總長(zhǎng)的一半時(shí) ， 則將這個(gè)圈中的重復(fù)邊去掉 ， 再將該圈中原來(lái)沒有重復(fù)邊的各邊加上重復(fù)邊 ， 其它各圈的邊不變 ， 返回步驟 （ 2） 。 07:38:3007:38:3007:38Saturday, February 4, 2023 ? 1乍見翻疑夢(mèng)，相悲各問年。 07:38:3007:38:3007:382/4/2023 7:38:30 AM ? 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 上午 7時(shí) 38分 30秒 上午 7時(shí) 38分 07:38: ? 楊柳散和風(fēng)，青山澹吾慮。 2023年 2月 上午 7時(shí) 38分 :38February 4, 2023 ? 1業(yè)余生活要有意義，不要越軌。 07:38:3007:38:3007:38Saturday, February 4, 2023 ? 1知人者智，自知者明。 2023年 2月 4日星期六 上午 7時(shí) 38分 30秒 07:38: ? 1楚塞三湘接，荊門九派通。 2023年 2月 上午 7時(shí) 38分 :38February 4, 2023 ? 1行動(dòng)出成果，工作出財(cái)富。 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 ? 靜夜四無(wú)鄰，荒居舊業(yè)貧。 推論 一個(gè)多重連通圖 G有歐拉道路的充分必要條件是 G有且僅有兩個(gè)奇點(diǎn) 。 （ 3） 在 L( f (k1) )中 ， 尋求從 vs到 vt的最短路 。 Ev ij ?),( 0?ijf ),( ji ?? ),min ( iijj f ?? ? Evv ji ?),( ijij cf ? ),( ji ?? ),min ( ijijij fc ?? ??調(diào)整過程 設(shè) 1． 令 2． 去掉所有標(biāo)號(hào) ， 回到第一步 ， 對(duì)可行流重新標(biāo)號(hào) 。 f 是一個(gè)可行流 ， 如果滿足： 則稱 為從 vs到 vt 的關(guān)于 f 的一條增廣鏈。 對(duì)于 D中的每一個(gè)弧 （ vi , vj） ∈ E ,都有一個(gè)非負(fù)數(shù) cij,叫做弧的容量 。 解： （ 1） 分析：可行的購(gòu)置方案 （ 更新計(jì)劃 ） 是很多的 ， 如： 1） 每年購(gòu)置一臺(tái)新的 ， 則對(duì)應(yīng)的費(fèi)用為： 11+11+12+12+13 +5+5+5+5+5 = 84 2 )第一年購(gòu)置新的 ， 一直用到第五年年底 ， 則總費(fèi)用為： 11+5+6+8+11+18 = 59 顯然不同的方案對(duì)應(yīng)不同的費(fèi)用。 min L(μ)=10 ⑧ P=T=10 由此看到，此方法不僅求出了從 V1 到 V8 的最短路長(zhǎng)，同時(shí)也求出了從 V1 到 任意一點(diǎn) 的最短路長(zhǎng)。 vi 為剛得到 P標(biāo)號(hào)的點(diǎn)，考慮點(diǎn) vj， 其中 ，且 vj為 T標(biāo)號(hào)。 一般設(shè)已有 {e1，e2， … ， ek}， 找一條與 {e1， e2， … ， ek}中任何一些邊不構(gòu)成圈的邊 ek+1， 重復(fù)這個(gè)過程，直到不能進(jìn)行為止。 （ 3） 樹 中任意兩個(gè)頂點(diǎn)之間，恰有且僅有一條鏈（初等鏈）。若鏈中所含的邊均不相同，則稱此鏈為簡(jiǎn)單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈 , 也稱通路。 有向圖中 ， 以 vi 為始點(diǎn)的邊數(shù)稱為點(diǎn) vi的出次 ， 用 表示 ；以 vi 為終點(diǎn)的邊數(shù)稱為點(diǎn) vi 的入次 ， 用 表示； vi 點(diǎn)的出次和入次之和就是該點(diǎn)的次 。 有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡(jiǎn)單圖。（連線可帶箭頭，也可不帶，前者叫弧，后者叫邊） 一個(gè)圖是由點(diǎn)集 和 中元素的無(wú)序?qū)Φ囊粋€(gè)集合 構(gòu)成的二元組 ， 記為 G =(V， E)， 其中 V 中的元素 叫做頂點(diǎn) ， V 表示圖 G 的點(diǎn)集合； E 中的元素 叫做邊 ， E 表示圖 G 的邊集合 。 如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀? )(vd圖中 d(v1)= 4， d(v6)= 4（ 環(huán)計(jì)兩度 ） 定理 1 所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的 2倍。 Avv ji ?),(jiw 由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。 樹中次為 1的點(diǎn)稱為樹葉，次大于 1的點(diǎn)稱為分支點(diǎn)。 ),( 1EVK ?一個(gè)圖 G 有生成樹的充要條件是 G 是連通圖。即： 最小。 0)( 1 ?v)6,3,2()( ????? ivT i（ 2） （ 3） 3]30,min[])(,)(min[)( 12122 ??????? lvPvTvT 5]50,min[])(,)(min[) 13133 ??????? lvPvT