運籌學第6章網絡分析

1、第第1頁頁網絡分析網絡分析Network AnalysisNetwork Analysis第第2頁頁|圖與子圖圖與子圖|圖的連通與割集圖的連通與割集|樹與支撐樹樹與支撐樹|最小樹最小樹|最短有向路最短有向路|最大流最大流|最小費用流最小費用流|最大對集最大對集第第3頁頁|圖與網絡圖與網絡 無向圖的基本概念無向圖的基本概念 網絡的基本概念網絡的基本概念|關聯(lián)矩陣和鄰接矩陣關聯(lián)矩陣和鄰接矩陣 關聯(lián)矩陣關聯(lián)矩陣 鄰接矩陣鄰接矩陣 主要結論主要結論|子圖子圖 第第4頁頁無向圖無向圖G：一個有序二元組一個有序二元組(N,E),記為記為G=(N,E)G的點集合的點集合： （例如：圖（例如：圖（1）中的）中

2、的 N=（1，2，3，4，5）是一個無向圖是一個無向圖 的點的集合）的點的集合）G的邊集合的邊集合：E=eij且且eij=ni,nj為右為右圖圖無序二無序二元組元組 eijij的端點的端點：有：有eijij=n=ni i,n,nj j ，則稱則稱ni i和和nj j為為 eijij的端點，且稱的端點，且稱eijij 連接點連接點 ni i和和nj j 圈圈：兩個端點重合為一點的邊：兩個端點重合為一點的邊 （例如右圖中的（例如右圖中的e11）孤立點孤立點：不與任何邊關聯(lián)的點：不與任何邊關聯(lián)的點 （例如右圖中（例如右圖中的的n5）34512第第5頁頁關聯(lián)關聯(lián)：一條邊的端點稱為這條邊的關聯(lián)：一條邊的

3、端點稱為這條邊的關聯(lián)鄰接鄰接：與同一條邊關聯(lián)的端點稱為是鄰接的，同時如果兩條：與同一條邊關聯(lián)的端點稱為是鄰接的，同時如果兩條邊有一個公共端點，則稱這兩條邊是鄰接的邊有一個公共端點，則稱這兩條邊是鄰接的有限圖有限圖：點和邊都是有限集合的圖：點和邊都是有限集合的圖空圖空圖：沒有任何邊的圖：沒有任何邊的圖平凡圖平凡圖：只有一個點的圖：只有一個點的圖簡單圖簡單圖：既沒有圈也沒有兩條邊連接同一對點的圖：既沒有圈也沒有兩條邊連接同一對點的圖 第第6頁頁完全圖完全圖：每一對點之間均有一條邊相連的圖：每一對點之間均有一條邊相連的圖二分圖二分圖 G G=(=(N N, ,E E) )：存在的一個二分劃存在的一個

4、二分劃( (S S, ,T T) )，使得使得G G的每條邊有一個端點在的每條邊有一個端點在S S中，另一個端點在中，另一個端點在T T中中完全二分圖完全二分圖 G G=(=(S S, ,T T, ,E E) )：S S中的每個點與中的每個點與T T中的每中的每個點都相連的簡單二分圖個點都相連的簡單二分圖簡單圖簡單圖G G的補圖的補圖 : :與與G G有相同頂點集合的簡單圖，有相同頂點集合的簡單圖， 且 中 的 兩 個 點 相 鄰 當 且 僅 當 它 們 在且 中 的 兩 個 點 相 鄰 當 且 僅 當 它 們 在G G中中 不相鄰不相鄰第第7頁頁有向圖有向圖G G：一個有序二員組一個有序二員

5、組( (N N, ,A A) )，記為記為G G=(=(N N, ,A A) ) G G的弧集合的弧集合：A A=a aijij 且且a aijij=n ni i, ,n nj j 為有序二元組為有序二元組 ，若，若a aijij=n ni i, ,n nj j ，則稱則稱a aijij從從n ni i連向連向n nj j， n ni i稱為稱為a aijij的尾，的尾， n nj j為為 a aijij的頭，的頭，n ni i稱為稱為n nj j的先輩，的先輩，n nj j稱為稱為 n ni i的后繼的后繼有向圖有向圖G G的基本圖的基本圖：對于：對于G G的每條弧用一條邊代替后得到的每條弧

6、用一條邊代替后得到的無向圖的無向圖（有向）網絡（有向）網絡G G：對（有向）圖對（有向）圖G G的每條邊（弧）都賦予的每條邊（?。┒假x予一個實數，并稱為邊（?。┑臋?，則連同它邊（?。┥弦粋€實數，并稱為邊（?。┑臋?，則連同它邊（弧）上的權稱為（有向）網絡。的權稱為（有向）網絡。第第8頁頁簡單圖簡單圖),(ENG 的的關聯(lián)矩陣：一個關聯(lián)矩陣：一個|EN 階矩陣階矩陣 )(ikbB ， 其中， 其中 簡單有向圖簡單有向圖),(ANG 的關聯(lián)矩陣：一個的關聯(lián)矩陣：一個|AN 階階矩矩 陣陣)(ikbB ，其中，其中 , 0 , 1 , 1 否則否則為頭為頭以點以點當弧當弧為尾為尾以點以點當弧當弧iai

7、abikikik , 0 , 1否否則則關關聯(lián)聯(lián)與與邊邊當當點點kibik第第9頁頁右圖的關聯(lián)矩陣是右圖的關聯(lián)矩陣是 右圖的關聯(lián)矩陣是右圖的關聯(lián)矩陣是 134521342 110100001010010001101010000110010000011154321 110001011001101000114321第第10頁頁圖（圖（7 7）的鄰接矩陣是）的鄰接矩陣是 圖（圖（8 8）的鄰接矩陣是）的鄰接矩陣是 134521342 01110101011101110101011105432154321 010000001100011043214321第第11頁頁命題命題 6.1.1 G 是二分圖當

8、且僅當是二分圖當且僅當 G 的鄰接矩陣可的鄰接矩陣可 表成如下形式表成如下形式 00TAAA 命題命題 6.1.2 |2 Edii ,其中其中id表示簡單圖表示簡單圖 G 中中點點 i 的次是指的次是指 G 中與中與點點 i 關聯(lián)的邊數關聯(lián)的邊數. 命題命題 6.1.3 iiiidAd|,其中其中 id表示簡單有向表示簡單有向 圖圖 G 中中點點 i 的入次是指的入次是指 G 中以中以點點 i 為頭的弧數；為頭的弧數； id 表示點表示點 i 的出次是指的出次是指 G 中以中以點點 i 為尾的弧數為尾的弧數. 第第12頁頁*圖圖G=(N,E)的的子子圖圖),(ENG ：NN 和和EE ，對對E

9、中中任任意意的的一一條條 邊邊,jiijnne ，都都有有Nni 和和Nnj *圖圖G的的支支撐撐子子圖圖G ：G 是是G的的子子圖圖，且且NN *點點導導出出子子圖圖NG ：以以N的的一一個個非非空空子子集集N作作為為點點集集、以以兩兩端端點點均均在在 N 中中的的所所有有邊邊為為邊邊集集的的子子圖圖 *邊邊導導出出子子圖圖EG ：以以E的的一一個個非非空空子子集集E作作為為邊邊集集、以以E中中邊邊的的所所 有有端端點點作作為為點點集集的的子子圖圖 *圖圖G的的不不相相交交子子圖圖G1和和G2：G1和和G2沒沒有有公公共共點點 *圖圖G的的邊邊不不重重子子圖圖G1和和G2：G1和和G2沒沒有

10、有公公共共邊邊 *子子圖圖G1和和G2的的并并21GG ：以以G1和和G2的的點點集集的的并并為為點點集集，以以G1和和 G2的的邊邊集集的的并并為為邊邊集集的的子子圖圖 *子子圖圖G1和和G2的的交交21GG ：以以G1和和G2的的點點集集的的交交為為點點集集，以以G1和和 G2的的邊邊集集的的交交為為邊邊集集的的子子圖圖 第第13頁頁| 圖的連通圖的連通 無向圖無向圖 有向圖有向圖| 圖的割集圖的割集 概概 念念 主要結論主要結論第第14頁頁135426圖圖G中路中路：一個點和邊交替序列：一個點和邊交替序列 ( (ni i, ,eijij, ,nj j, , ,nk k, ,eklkl,

11、,nl l) )，簡單路簡單路：邊不重的路：邊不重的路 初級路初級路：點不重的路：點不重的路 回路回路：在：在G中，一條至少包含一個中，一條至少包含一個 邊并且邊并且ni i= =nl l的的 ni i, ,nl l 路路簡單回路簡單回路：邊不重的回路：邊不重的回路初級回路初級回路：點不重的回路：點不重的回路第第15頁頁點點i i和和j j點是連通的點是連通的：G G中存在一條（中存在一條（i i，j j）路路G G是連通的是連通的：G G中任意兩點都是連通的中任意兩點都是連通的 連通分支連通分支：G G的極大連通子圖的極大連通子圖 命題命題.1 設設G G有有p p個連通分支

12、，則個連通分支，則G G的鄰接矩的鄰接矩 陣可以表示成分塊矩陣陣可以表示成分塊矩陣 第第16頁頁134256有向圖有向圖G G中的一條有向路中的一條有向路：個點和弧的交錯序列：個點和弧的交錯序列 ( (n ni i, ,a aijij, ,n nj j, , ,n nk k, ,a aklkl, ,n nl l) )，記為記為( (n ni i, ,n nl l) )有向路有向路 簡單有向路簡單有向路：弧不重的有向路：弧不重的有向路 初級有向路初級有向路：點不重的有向路：點不重的有向路 有向回路有向回路：至少包含一條弧且：至少包含一條弧且n ni i= =n nj j的的( (n ni i,

13、,n nj j) )有向路有向路 簡單有向回路簡單有向回路：弧不重的有向回路：弧不重的有向回路 初級有向回路初級有向回路：點不重的有向回路：點不重的有向回路第第17頁頁點點i i和點和點j j是強連通的是強連通的：G G中存在一條中存在一條( (i,j)i,j)有向有向路，也存在一條路，也存在一條( (j,i)j,i)有向路有向路G是強連通的是強連通的：G G中任意兩點都是強連通的中任意兩點都是強連通的 G的強連通分支的強連通分支：G G的極大連通子圖的極大連通子圖命題命題.2 設設G G有有p p個強連通分支，則個強連通分支，則G G的鄰接的鄰接矩陣可以表示成如下形式：矩陣可

14、以表示成如下形式：強強連通性連通性第第18頁頁圖圖 G 的的 割割 邊邊 ： 如如 果果 從從 G 中中 刪刪 去去 它它 就就 使使 圖圖 的的 連連 通通 分分 支支 數數 嚴嚴 格格 增增 加加 的的 邊邊 S, ,T 割割 ： 一一 個個 端端 點點 在在 S 中中 ， 另另 一一 個個 端端 點點 在在 T 中中 的的 邊邊 集集 合合 ， 其其 中中 S 和和 T 是是 N 的的 兩兩 個個 不不 相相 交交 子子 集集 圖圖 G 的的 邊邊 割割,SS： 從從 G 中中 刪刪 去去 它它 就就 使使 圖圖 的的 連連 通通 分分 支支 數數 嚴嚴 格格 增增 加加 的的 邊邊 集

15、集 合合 割割 集集 ： G 的的 極極 小小 邊邊 割割 圖圖 G 的的 割割 邊邊 ： 如如 果果 從從 G 中中 刪刪 去去 它它 就就 使使 圖圖 的的 連連 通通 分分 支支 數數 嚴嚴 格格 增增 加加 的的 邊邊 ( (S, ,T) )： 有有 向向 圖圖 G= =( (N, ,A) )中中 尾尾 在在 S 中中 ， 頭頭 在在 T 中中 的的 弧弧 集集 合合 有有 向向 圖圖 G 的的 弧弧 割割),(SS： 從從 G 中中 刪刪 去去 它它 就就 使使 圖圖 的的 強強 連連 通通 分分 支支 數數 嚴嚴 格格 增增 加加 的的 弧弧 集集 合合 有有 向向 割割 集集 ：

16、 G 的的 極極 小小 弧弧 割割 第第19頁頁命命題題 6.2.3 任任何何邊邊割割都都是是不不相相交交割割集集的的并并. 命命題題 6.2.4 任任給給圖圖 G，設設 C 是是 G 的的一一條條簡簡單單回回路路 ,TS 是是 G 的的一一個個割割集集，并并用用)(),( ECE分分別別 表表示示 ,C所所包包含含的的邊邊集集合合。若若 )()(ECE，則則 2| )()(| ECE 第第20頁頁|樹及其基本性質樹及其基本性質 概念及符號概念及符號 基本性質基本性質|支撐樹及其基本支撐樹及其基本性質性質 概念及符號概念及符號 基本性質基本性質第第21頁頁樹樹：一一個個連連通通且且無無回回路路

17、（除除非非特特別別聲聲明明，以以后后皆皆指指初初級級回回路路）的的圖圖 k樹樹（森森林林） ：有有 k 個個連連通通分分支支且且無無回回路路的的圖圖 21HH ：子子圖圖1H和和子子圖圖2H的的邊邊的的并并集集 21HH ：子子圖圖1H和和子子圖圖2H的的邊邊的的交交集集 21 HH：在在子子圖圖1H中中但但不不在在子子圖圖2H中中的的邊邊的的集集合合 G + e：在在圖圖 G 中中加加連連邊邊 e G - e：在在圖圖 G 中中去去掉掉邊邊 e G - i：在在圖圖 G 去去掉掉點點 i 及及與與點點 i 關關聯(lián)聯(lián)的的所所有有邊邊 第第22頁頁定定理理6.3.1 設設T=(N,E)是是3|

18、N的的一一個個圖圖，則則下下列列六六個個定定義義是是等等價價的的： （1）T連連通通且且無無回回路路； （2）T有有1| N條條邊邊且且無無回回路路； （3）T連連通通且且有有1| N條條邊邊； （4）T連連通通且且每每條條邊邊都都是是割割邊邊； （5）T的的任任兩兩點點間間都都有有唯唯一一的的路路相相連連； （6）T無無回回路路，但但在在任任一一對對不不相相鄰鄰的的點點間間加加連連一一條條邊邊，則則構構成成唯唯一一的的一一個個回回路路。 定定理理6.3.2 每每個個樹樹至至少少有有兩兩個個次次為為1的的點點。 第第23頁頁圖圖 G 的的支支撐撐樹樹：G的的一一個個是是樹樹的的支支撐撐子子圖圖

19、 G 的的反反樹樹：TGT* ，其其中中),(ENT 是是),(ENG 的的一一個個支支撐撐樹樹 )(e ：割割集集,21SS，其其中中21,SS為為eT 的的兩兩個個連連通通分分支支的的點點集集合合 第第24頁頁定定理理6.3.3 G 有有支支撐撐樹樹當當且且僅僅當當G 是是連連通通的的。 定定理理6.3.4 任任給給圖圖G，設設T 是是G 的的支支撐撐樹樹， e 是是T 的的一一條條 邊邊，則則存存在在唯唯一一的的一一個個割割集集)(e 包包含含于于eT *中中。 定定理理6.3.5 設設1T和和2T是是G 的的兩兩個個支支撐撐樹樹，且且kTT |21， 則則2T經經過過k 次次迭迭代代后

20、后就就得得到到1T. 第第25頁頁|最小樹及其性質最小樹及其性質|求最小樹的求最小樹的Kruskal算法算法 算法步驟算法步驟 算例算例 算法復雜性算法復雜性 |Dijkstra算法算法 算法步驟算法步驟 算例算例 算法復雜性算法復雜性第第26頁頁支撐樹支撐樹 T 的權（或長）的權（或長） ： EeeWTW)()( 最小支撐樹最小支撐樹：G 中權最小的支撐樹中權最小的支撐樹 定理定理 6.4.1 設設 T 是是 G 的支撐樹，則的支撐樹，則 T 是是 G 的最小樹當且僅當對任意邊的最小樹當且僅當對任意邊 *Te 有有 )(max)()(eWeWeCe 其中其中eTeC )(為一個唯一的回路。為

21、一個唯一的回路。 定理定理 6.4.2 設設 T 是是 G 的支撐樹，則的支撐樹，則 T 是是 G 的最小樹當且僅當對任意邊的最小樹當且僅當對任意邊 Te 有有 )(min)()(eWeWee 其中其中eTe *)(為一個唯一割集。為一個唯一割集。 定理定理 6.4.3 設設 T 是是 G 的支撐樹，則的支撐樹，則 T 是是 G 的唯一最小樹當且僅當對任意的唯一最小樹當且僅當對任意 邊邊TGe ，e 是是 C(e)中的唯一最大邊。中的唯一最大邊。 定理定理 6.4.4 設設 T 是是 G 的支撐樹，則的支撐樹，則 T 是是 G 的唯一最小樹當且僅當對任意的唯一最小樹當且僅當對任意 邊邊Te ，

22、e 是是)(e 中的唯一最大邊。中的唯一最大邊。 第第27頁頁第第 1 步步 開始把邊按權的大小由小到大排列起來，即開始把邊按權的大小由小到大排列起來，即 maaa,.,21 置置 S，0 i，1 j。 第第 2 步步 若若1| niS，則停。，則停。這時這時TSG 即為所求；否則，即為所求；否則， 轉向第轉向第 3 步。步。 第第 3 步步 若若jaSG不構成回路，則置不構成回路，則置jiae 1，1 ieSS，1 ii， 1 jj，轉向第，轉向第 2 步；否則，置步；否則，置1 jj，轉向第，轉向第 2 步。步。 第第28頁頁用用 K ru sk al 算算 法法 求求 解解 下下 圖圖

23、所所 示示 網網 絡絡 的的 最最 小小 樹樹 ， 其其 中中 每每 條條 邊邊 上上 的的 數數 表表 示示 該該 邊邊 的的 權權 值值 。 1 4 3 2 2 2 4 4 第第29頁頁 1 1 2 1 1 3 2 2 第第30頁頁首首先先，在在第第 1 步步中中把把邊邊按按權權的的大大小小由由小小到到大大排排列列起起來來，這這約約需需mm2log次次比比較較； 其其次次，第第 2 步步最最多多循循環(huán)環(huán) n 次次； 在在第第 3 步步中中，判判定定加加邊邊后后是是否否構構成成回回路路總總共共約約需需 m 次次比比較較，而而加加邊邊后后點點的的重重新新標標號號最最多多需需 n(n+1)次次比

24、比較較。 所所以以，總總的的計計算算量量為為 )log()1(log222nnOnnmnmm 第第31頁頁第第 1 步步 置置jjwu1 ， T, 1 R, ,.,3 , 2nS ； 第第 2 步步 取取 ikjSjkwuu min，置置ikeTT ，kRR ， kSS ； 第第 3 步步 若若 S，則則停停止止；否否則則，置置 ,minkjjSjkwuu ，Sj ， 返返回回第第 2 步步。 第第32頁頁用用 Dijkstra 算算法法求求解解下下圖圖所所示示網網絡絡的的最最小小樹樹，其其中中每每條條邊邊上上的的數數 表表示示該該邊邊的的權權值值。 1 4 3 2 2 2 4 4 第第33頁

25、頁第第34頁頁執(zhí)執(zhí)行行第第 2 步步時時，第第一一次次是是2 n次次比比較較， 第第二二次次為為3 n次次比比較較， 第第三三次次為為4 n次次比比較較， 因因此此總總的的比比較較為為2)1)(2( nn次次。 執(zhí)執(zhí)行行第第 3 步步時時，第第一一次次是是2 n次次比比較較， 第第二二次次為為3 n次次比比較較， 第第三三次次為為4 n次次比比較較， 因因此此總總的的比比較較為為)1)(2( nn次次。 所所以以，總總的的計計算算量量約約為為)(2nO。 第第35頁頁|最短有向路方程最短有向路方程|求最短有向路的求最短有向路的Dijkstral算法算法 算法步驟算法步驟 算例算例 算法復雜性算

26、法復雜性第第36頁頁給給定定有有向向網網絡絡),(WANG ，設設 P 為為 G 中中的的一一條條有有向向路路 P 的的權權（或或長長） ： PaaWPW)()( 問問題題：尋尋求求有有向向網網絡絡中中自自某某一一指指定定點點 i 到到另另一一指指定定點點 j 間間的的最最短短有有向向路路 定定理理 6.5.1 設設有有向向網網絡絡 G 中中不不含含非非正正有有向向回回路路，并并且且從從點點 1 到到其其余余點點都都有有有有限限長長度度的的有有向向路路，那那么么(6.5.2)有有唯唯一一有有限限解解。 njwuuukjkjkj,.,3 , 2 ,min 01 (6.5.2) 其其中中，ju和和

27、ku分分別別表表示示自自點點 1 到到點點 j 和和點點 k 的的最最短短有有向向路路的的長長度度，kjw表表示示弧弧),(jk的的長長度度。 定定理理 6.5.2 設設ju是是有有向向網網絡絡G中中自自點點 1 到到點點 j 的的最最短短有有向向路路的的長長度度，并并且且對對所所有有的的nj,.,3 , 2 ，ju為為有有限限值值， 若若網網絡絡 G 中中的的點點能能編編成成如如下下的的序序號號n,.,3 , 2，使使得得若若 ij，有有jiuu 且且0 jiw，但但等等號號不不同同時時成成立立或或者者 jiuu 且且 jiw，即即Aij ),(。則則方方程程(6.5.2)可可簡簡化化為為

28、njwuuukjkjkj,.,3 , 2 ,min 01 (6.5.3) 第第37頁頁定定理理6.5.3 設設),(WANG 是是一一個個弧弧權權為為正正值值的的有有向向網網絡絡，則則在在G中中， 任任意意一一條條最最短短有有向向路路的的長長都都大大于于它它的的真真子子有有向向路路的的長長。 G中中自自點點1到到其其他他各各最最短短有有向向路路的的長長可可按按大大小小排排列列如如下下 nuuu 210 算算法法步步驟驟： 第第1步步 (開開始始) 置置01 u，jjwu1 ，nj,.,3 , 2 ，1 P，,.,3 , 2nT 。 第第2步步 (指指出出永永久久標標號號) 在在T中中尋尋找找一

29、一點點k，使使得得minjTjkuu 。置置kPP ，kTT 。 若若 T，終終止止；否否則則，進進行行第第3步步。 第第3步步 (修修改改臨臨時時標標號號) 對對T中中每每一一點點j，置置,minkjkjjwuuu ，然然后后返返回回第第1步步。 第第38頁頁用用Dijkstra算法求解下圖所示有向網絡中自點算法求解下圖所示有向網絡中自點1到其他各點的最到其他各點的最短有向路。其中每條弧上的數表示其權值。短有向路。其中每條弧上的數表示其權值。 3 3 5 5 1 1 2 2 4 4 2 2 3 3 7 7 4 4 6 6 2 2 第第39頁頁第第40頁頁這個算法經過這個算法經過1 n次循環(huán)次

30、循環(huán)必結束必結束。必結束必結束。 在在第第 2 步中步中要做要做2)1)(2( nn次比較。次比較。 在在第第 3 步中步中要做要做2)1)(2( nn次加法和次加法和2)1)(2( nn次比較。次比較。 所以所以，總的計算量約為，總的計算量約為)(2nO。 第第41頁頁|最大流最小割定理最大流最小割定理 基本概念基本概念 主要結論主要結論|最大流算法最大流算法 算法步驟算法步驟 算例算例 算法復雜性算法復雜性第第42頁頁給給定定有有向向網網絡絡G=(N,A,C)，ijc表表示示弧弧Aji ),(的的容容量量，G有有一一個個發(fā)發(fā)點點s 和和一一個個收收點點t),(Nts 。 令令ijx通通過過

31、弧弧),(ji的的流流量量，則則流流)(ijxx 要要遵遵守守 ijijcx 0 (6.6.1) , , 0 ,tivtsisivxxjjijij (6.6.2) 可可行行流流：滿滿足足(6.6.1)和和 守守恒恒方方程程(6.6.2)的的流流，簡簡稱稱為為 ),(ts流流 設設P是是G中中從從s 到到t 的的有有向向路路，則則 P的的前前向向弧弧),(ji：其其方方向向是是從從s 到到t。 P的的背背向向弧弧),( ji：其其方方向向是是從從t 到到s。 流流)(ijxx 的的增增廣廣路路P：P的的每每個個前前向向弧弧),(ji有有ijijcx ，而而P的的每每個個背背向向弧弧),(ji有有

32、0 ijx。 ),(ts割割：弧弧割割),(TS，其其中中Ss ，Tt 。 割割),(TS的的容容量量： SiTjijcTSC),( 問問題題：求求一一個個可可行行流流)(*ijxx ，使使得得 jjtjsjxxv*達達到到最最大大值值。 第第43頁頁定理定理 6.6.1（增廣路定理）（增廣路定理）一個可行流是最大流當且僅當不存在一個可行流是最大流當且僅當不存在 關于它的從關于它的從 s 到到 t 的增廣路。的增廣路。 定理定理 6.6.2（整流定理）（整流定理）如果網絡中所有弧容量是整數，則存在如果網絡中所有弧容量是整數，則存在 值為整數的最大流。值為整數的最大流。 定理定理 6.6.3（最

33、大流最小割定理最大流最小割定理）一個一個(s,t)-流的最大值等于流的最大值等于(s,t)-割割 的最小容量。的最小容量。 第第44頁頁第第 1 步步 (開開始始)令令)(ijxx 是是任任意意可可行行流流，可可能能是是零零流流，給給 s 一一個個 永永久久標標號號),( 。 第第 2 步步 (找找增增廣廣路路) (2.1) 如如果果所所有有標標號號都都已已經經被被檢檢查查，轉轉到到第第 4 步步。 (2.2) 找找一一個個標標號號但但未未檢檢查查的的點點i，并并做做如如下下檢檢查查，對對每每一一個個弧弧 ),(ji，如如果果ijijcx 且且 j 未未標標號號，則則給給 j 一一個個標標號號

34、)(,(ji ， 其其中中)(,min)(ixcjijij ；對對每每一一個個弧弧),(ij，如如果果0 ijx 且且 j 未未標標號號，則則給給 j 一一個個標標號號)(,(ji ，其其中中)(,min)(ixjji 。 (2.3) 如如果果 t 已已被被標標號號，轉轉到到第第 3 步步；否否則則，轉轉到到(2.1)。 第第 3 步步 (增增廣廣)由由點點 t 開開始始，試試用用指指示示標標號號構構造造一一個個增增廣廣路路，指指示示標標 號號的的正正負負則則表表示示通通過過增增加加還還是是減減少少弧弧流流量量來來增增大大流流值值。抹抹去去 s 點點以以 外外的的所所有有標標號號，轉轉到到第第

35、 2 步步。 第第 4 步步 (構構造造最最小小割割)這這時時現(xiàn)現(xiàn)行行流流是是最最大大的的，若若把把所所有有標標號號點點的的集集合合記記 為為 S，所所有有未未標標號號點點的的集集合合記記為為 T，便便得得到到最最小小容容量量割割),(TS，計計算算完完成成。 第第45頁頁求解下圖所示有向網絡中自點求解下圖所示有向網絡中自點 1 到點到點 6 的最大流。其中每條弧的最大流。其中每條弧上的數表示其容量。上的數表示其容量。 5 8 3 9 6 6 2 5 7 8 第第46頁頁 (+1,2) 10 5,2 5,2 8,6 3,2 9,7 8,6 3,2 9,7 (+4,2) 6,6 6,4 6,6

36、6,4 2,1 5,1 7,0 2,1 5,1 7,0 8,6 8,6 (+1,1) (-2,2) (-3,1) (+2,1) 5,4 5,4 (-,)8,8 3,2 9,9 (+5,1) (-,)8,8 3,1 9,9 6,6 6,4 6,6 6,4 2,1 5,1 7,0 2,1 5,1 7,1 8,6 8,6 (+1,1) (-2,2) 第第47頁頁設設弧弧數數為為m，每每找找一一條條增增廣廣路路最最多多需需要要進進行行2m次次弧弧檢檢查查。 如如果果所所有有弧弧容容量量都都是是整整數數，則則最最多多需需要要v次次增增廣廣，其其中中v是是最最大大流流值值。 所所以以，總總的的計計算算量量

37、為為)(mvO。 第第48頁頁|最小費用流算法最小費用流算法 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例 算法復雜性算法復雜性|最特殊的最小費用流運輸問題最特殊的最小費用流運輸問題 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例 第第49頁頁基基本本假假設設： 給給定定有有向向網網絡絡),(WCANG ，其其中中ijc表表示示弧弧Aji ),(的的容容量量，ijw 表表示示單單位位流流通通過過弧弧Aji ),(的的費費用用。則則流流)(ijxx 的的費費用用為為 jiijijxw, 問問題題： 求求一一個個可可行行流流)(*ijxx ，使使其其流流值值為為得得v，并并且且費費用用達達到到最最小

38、小。 第第50頁頁 ),( ,0 , , , 0)( )( )( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij 第第51頁頁 ,)( ),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij無無限限制制 第第52頁頁第第 1 步步 (開開始始) 讓讓所所有有的的流流0 ijx是是，所所有有點點對對應應的的數數0)( ip。 第第 2 步步 (決決定定哪哪些些弧弧可可以以改改變變流流量量) 用用 I 表表示示這這樣樣的的弧弧集集合

39、合使使ijwipjp )()(，同同時時ijijcx 用用 R 表表示示這這樣樣的的弧弧集集合合使使ijwipjp )()(，同同時時0 ijx 用用 Q 表表示示不不在在RI 中中的的弧弧集集合合。 第第 3 步步 (改改變變流流量量) 用用最最大大流流算算法法，在在RI 上上找找增增廣廣路路，增增加加流流量量。如如果果從從s 到到t 的的流流量量已已經經是是 v，那那么么計計算算停停止止，已已經經得得到到一一個個流流量量是是 v 的的最最小小費費用用流流。 如如果果從從s 到到t 不不能能再再增增加加流流量量，檢檢查查在在RIQ中中是是否否能能找找到到增增 廣廣路路。如如果果不不能能找找到

40、到增增廣廣路路，那那么么該該網網絡絡的的最最大大流流達達不不到到 v；如如果果在在 RIQ中中能能找找到到增增廣廣路路，就就轉轉入入第第 4 步步。 第第 4 步步 (改改變變頂頂點點的的)(ip值值) 把把所所有有點點分分成成兩兩類類：S 是是標標上上號號的的點點的的集集合合，T 是是標標不不上上號號的的點點的的集集合合， 讓讓 S 中中的的點點)(ip值值不不變變，T 的的點點)(ip值值全全部部加加 1，再再轉轉回回第第 2 步步。 第第53頁頁求解下圖所示網絡中自點求解下圖所示網絡中自點 1 到點到點 4 其值為其值為 3 的最的最 小費用流。其中每條弧上的第一個數表示單位流的費小費用

41、流。其中每條弧上的第一個數表示單位流的費 用，第二個數表示容量。用，第二個數表示容量。 1,2 3,4 1,2 3,1 1,2 第第54頁頁stabstabstab 1，2，0 3,4,0 1,2,0 3,1,0 1,2,0stab),(stab(+s,2),(+a,2)stab(+s,2),(第第55頁頁stabstab),(stab(+s,2)stab(+a,2)(+b,2)stab),(-b,1)(+s,1)stab1,2,23,4,01,2,23,1,01,2,2第第56頁頁stabstab),(stab(-b,1)(+s,1)(+a,1)第第57頁頁設設網網絡絡的的點點數數為為 n，

42、弧弧數數為為 m，弧弧的的最最大大容容量量為為 w。 算算法法的的循循環(huán)環(huán)次次數數取取決決于于點點的的 p(i)值值修修正正的的次次數數最最多多進進行行 mw 次次， 因因此此第第 2 步步的的計計算算量量為為)(2wmO。 如如果果最最大大流流值值為為 v，則則留留增增廣廣最最多多進進行行 v 次次， 所所以以第第 3 步步的的計計算算量量為為)(mvO。 第第 4 步步的的計計算算量量為為)(nmvO 所所以以，總總的的計計算算量量為為)(2mvwmO 。 第第58頁頁ia表示發(fā)點表示發(fā)點 i 可供應的產品數量可供應的產品數量),.,2 , 1(mi ； jb表示收點表示收點 j 所需的產

43、品數量所需的產品數量),.,2 , 1(nj ； ijw表示從發(fā)點表示從發(fā)點 i 到收點到收點 j 的單位產品運輸費用；的單位產品運輸費用； ijx表示從發(fā)點表示從發(fā)點 i 分配給收點分配給收點 j 的產品數量。的產品數量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw 第第59頁頁 ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 第第60頁頁第第 1 步步 (開開始始)任任給給原原始始規(guī)規(guī)劃劃的的可可行行解解ijx。 第第 2 步步 (計計算算

44、對對偶偶解解) 對對于于原原始始規(guī)規(guī)劃劃的的可可行行解解ijx，計計算算出出對對偶偶規(guī)規(guī)劃劃的的一一個個解解,jivu。 第第 3 步步 (計計算算檢檢驗驗數數)對對于于對對偶偶規(guī)規(guī)劃劃的的解解,jivu，計計算算 njmivuwwjiijij,.,2 , 1 ;,.,2 , 1 , 若若所所有有的的ijw均均非非負負，則則計計算算結結束束，這這時時得得到到的的ijx和和,jivu分分別別為為原原始始規(guī)規(guī)劃劃和和對對偶偶規(guī)規(guī)劃劃的的最最優(yōu)優(yōu)解解；否否則則，轉轉第第 4 步步。 第第 4 步步 (調調整整原原始始可可行行解解)令令0|min, ijijjistwww 即即選選擇擇stx進進入入基

45、基。對對應應于于網網絡絡中中，即即在在支支撐撐樹樹上上加加入入弧弧),(ts，從從而而得得到到一一個個回回路路。并并選選擇擇其其流流量量 stx，使使這這個個回回路路上上的的流流量量通通過過加加 或或減減 以以達達到到去去掉掉一一條條弧弧的的目目的的，從從而而得得到到一一個個新新的的被被改改進進的的原原始始可可行行解解ijx，轉轉第第 2 步步。 第第61頁頁求如圖所示運輸問題的最優(yōu)解求如圖所示運輸問題的最優(yōu)解1231234-45-20-30-30355040 8 6 9 9 9 12 13 7 14 9 16 5第第62頁頁2131234 15 20 30 20 10 30 初始原可行解初始

46、原可行解 第第63頁頁213123486121014對偶解對偶解第第64頁頁w w8 -6 -10 -29 809 -12 513 -7 5114 29 -116 -5 -486121 u V第第65頁頁 15- 20 30+ 20- 10 302131234調整原始可行解調整原始可行解第第66頁頁213123403666101對偶解對偶解第第67頁頁8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610 -1 第第68頁頁 20- 45 15+ 5 10- 302131234調整原始可行解調整原始可行解第第69頁頁102131234033662對偶

47、解對偶解第第70頁頁w w8 26 -10 -9 709 -12 313 -7 2314 59 -16 35 -366102 u V第第71頁頁v二分圖對集二分圖對集 基本概念基本概念 主要定理主要定理v二分圖的最大基數對集二分圖的最大基數對集 基本思想基本思想 算法步驟算法步驟 算例算例 算法復雜性算法復雜性v二分圖的最大權對集分派問題二分圖的最大權對集分派問題 規(guī)劃形式規(guī)劃形式 算法步驟算法步驟 算例算例第第72頁頁圖圖 G=(N,E)的的對對集集 M：M 是是 E 的的子子集集，且且 M 中中任任意意兩兩邊邊均均不不相相鄰鄰。 M - 飽飽和和點點 i：Ni ，且且 i 同同 M 的的一

48、一條條邊邊關關聯(lián)聯(lián)。 M - 非非飽飽和和點點 i：Ni ，且且 i 不不同同 M 的的任任一一條條邊邊關關聯(lián)聯(lián)。 G 的的完完美美對對集集 M：G 的的每每一一個個點點都都是是 M - 飽飽和和點點。 G 的的最最大大基基數數對對集集 M：不不存存在在另另外外一一個個對對集集另另外外一一個個對對集集 M，使使得得|MM ， 其其中中| M表表示示 M 的的基基數數。 G 的的一一條條 M -交交錯錯路路：邊邊在在對對集集 M 和和ME 中中交交錯錯出出現(xiàn)現(xiàn)的的路路。 G 的的一一條條 M - 增增廣廣路路：起起點點和和終終點點都都是是 M 非非飽飽和和的的一一條條 M - 交交錯錯路路。 圖

49、圖 G=(N,E)的的覆覆蓋蓋 K：K 是是 N 的的子子集集，且且 G 的的每每條條邊邊都都至至少少有有一一個個端端點點在在 K 中中。 圖圖 G 的的最最小小覆覆蓋蓋 K：G 不不存存在在另另外外一一個個覆覆蓋蓋 K，使使得得|KK 。 第第73頁頁定定理理 6.8.1 圖圖 G 中中的的一一個個對對集集 M 是是最最大大基基數數對對集集當當且且僅僅當當 G 不不包包含含 M - 增增廣廣路路。 定定理理 6.8.2 設設 G 為為具具有有二二分分劃劃(S,T)的的一一個個二二分分圖圖，則則 G 含含有有飽飽和和 S 的的每每個個點點的的對對 集集當當且且僅僅當當對對任任意意的的SX ，有

50、有| )(|XX 。 引引理理 6.8.1 設設 M 是是一一個個對對集集，K 是是一一個個覆覆蓋蓋，它它們們滿滿足足|KM ，則則 M 必必定定是是 最最大大基基數數對對集集，而而 K 是是最最小小覆覆蓋蓋。 定定理理 6.8.3 在在二二分分圖圖中中，最最大大基基數數對對集集的的邊邊數數等等于于最最小小覆覆蓋蓋的的點點數數。 第第74頁頁從從圖圖 G 的任意一個對集的任意一個對集 M 開始，若開始，若 M 飽和飽和 S 的所有點，則的所有點，則M是是 G 的最大基數對集；否則，由的最大基數對集；否則，由 S 的的 M - 非飽和點出發(fā)，用一個系統(tǒng)方非飽和點出發(fā)，用一個系統(tǒng)方 法法搜索一條搜

51、索一條 M - 增廣路增廣路 P。若若 P 存在，則通過交換存在，則通過交換 P 在在 M 和不在和不在 M 中的邊，便得到一個其基數增加中的邊，便得到一個其基數增加 1 的對集，然后從新的對集開始，繼的對集，然后從新的對集開始，繼 續(xù)迭代。續(xù)迭代。若若 P 不存在，則現(xiàn)行的對集就是不存在，則現(xiàn)行的對集就是 G 的最大基數對集。的最大基數對集。 第第75頁頁第第 1 步步 (開開始始)給給定定二二分分圖圖 G=(S,T,E)，令令 M 是是一一個個任任意意對對集集，可可能能是是空空對對集集，這這時時沒沒有有點點被被標標號號。 第第 2 步步 (標標號號) (2.0) 在在 S 中中，每每個個非

52、非飽飽和和點點給給以以標標號號“0”。 (2.1) 如如果果不不存存在在未未檢檢查查的的標標號號點點，轉轉向向第第 4 步步；否否則則，找找一一個個具具有有未未檢檢查查的的標標號號點點 i，如如果果Si ， 轉轉向向（2.2） ；如如果果Ti ，轉轉向向（2.3） (2.2) 檢檢查查點點 i 的的標標號號如如下下：對對每每個個同同點點 i 關關聯(lián)聯(lián)的的邊邊i , j，除除非非 j 已已經經被被標標號號；否否則則，給給點點 j 標標號號“i”， 轉轉向向(2.1)。 (2.3) 檢檢查查點點 i 的的標標號號如如下下：如如果果點點 i 是是非非飽飽和和點點，轉轉向向第第 3 步步；否否則則，辨

53、辨認認同同點點 i 關關聯(lián)聯(lián)的的屬屬于于 M 的的 唯唯一一邊邊i , j，給給點點 j 標標號號“i”，轉轉向向(2.1)。 第第 3 步步 (增增廣廣) 終終止止在在 i 的的一一條條增增廣廣路路被被找找到到，通通過過方方向向追追蹤蹤辨辨認認在在路路上上點點 i 的的前前點點，通通過過把把路路上上不不在在 M 中中的的邊邊加加入入 M，而而把把路路中中在在 M 中中的的邊邊從從 M 中中除除去去來來增增廣廣 M，抹抹掉掉所所有有標標號號，轉轉回回(2.0)。 第第 4 步步 (匈匈牙牙利利標標號號) 標標號號是是匈匈牙牙利利的的，這這時時沒沒有有增增廣廣路路存存在在，M 是是最最大大基基數

54、數對對集集。令令TSL ，表表示示所所有有標標號號點點的的集集 合合，則則)()(LTLSK 是是對對偶偶于于 M 的的最最小小覆覆蓋蓋。 第第76頁頁求下圖求下圖a a所示的二分圖所示的二分圖G G的最大基數對集，若初始解如下圖的最大基數對集，若初始解如下圖b b所示所示1234567A98a1234567A98b第第77頁頁1234567A9831333標號標號1234567A98333517810標號標號1234567A98增廣路增廣路1234567A98增廣路增廣路第第78頁頁1234567A981257108標號標號1234567A98增廣路增廣路第第79頁頁若令若令mS |，nT |，且，且nm 。 在找到一個匈牙利樹或找到一條增廣路之前，在找到一個匈牙利樹或找到一條增廣路之前， 標標號程序最多進行號程序最多進行)(mnO次；次； 在求出所需的對集之前，初始對集最多能增廣在求出所需的對集之前，初始對集最多能增廣 m 次；次； 所以，總的計算量為所以，總的計算量為)(2nmO。 第第80頁頁設二分網絡是完全的設二分網絡是完全的),(WTSTSG ， mS |，nT |，且且nm ),.,2 , 1;,.,2 , 1( , 0 ),.,2 , 1( , 1 ),.,2 , 1( , 1 . t . s max,njmixnjxmixxwi