运筹学第6章网络分析

1、第第1页页网络分析网络分析Network AnalysisNetwork Analysis第第2页页|图与子图图与子图|图的连通与割集图的连通与割集|树与支撑树树与支撑树|最小树最小树|最短有向路最短有向路|最大流最大流|最小费用流最小费用流|最大对集最大对集第第3页页|图与网络图与网络 无向图的基本概念无向图的基本概念 网络的基本概念网络的基本概念|关联矩阵和邻接矩阵关联矩阵和邻接矩阵 关联矩阵关联矩阵 邻接矩阵邻接矩阵 主要结论主要结论|子图子图 第第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）孤立点孤立点：不与任何边关联的点：不与任何边关联的点 （例如右图中（例如右图中的的n5）34512第第5页页关联关联：一条边的端点称为这条边的关联：一条边的

3、端点称为这条边的关联邻接邻接：与同一条边关联的端点称为是邻接的，同时如果两条：与同一条边关联的端点称为是邻接的，同时如果两条边有一个公共端点，则称这两条边是邻接的边有一个公共端点，则称这两条边是邻接的有限图有限图：点和边都是有限集合的图：点和边都是有限集合的图空图空图：没有任何边的图：没有任何边的图平凡图平凡图：只有一个点的图：只有一个点的图简单图简单图：既没有圈也没有两条边连接同一对点的图：既没有圈也没有两条边连接同一对点的图 第第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的每条边（弧）都赋予的每条边（弧）都赋予一个实数，并称为边（弧）的权，则连同它边（弧）上一个实数，并称为边（弧）的权，则连同它边（弧）上的权称为（有向）网络。的权称为（有向）网络。第第8页页简单图简单图),(ENG 的的关联矩阵：一个关联矩阵：一个|EN 阶矩阵阶矩阵 )(ikbB ， 其中， 其中 简单有向图简单有向图),(ANG 的关联矩阵：一个的关联矩阵：一个|AN 阶阶矩矩 阵阵)(ikbB ，其中，其中 , 0 , 1 , 1 否则否则为头为头以点以点当弧当弧为尾为尾以点以点当弧当弧iai

7、abikikik , 0 , 1否否则则关关联联与与边边当当点点kibik第第9页页右图的关联矩阵是右图的关联矩阵是 右图的关联矩阵是右图的关联矩阵是 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 关联的边数关联的边数. 命题命题 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 关关联联的的所所有有边边 第第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 步步最最多多循循环环 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页页执执行行第第 2 步步时时，第第一一次次是是2 n次次比比较较， 第第二二次次为为3 n次次比比较较， 第第三三次次为为4 n次次比比较较， 因因此此总总的的比比较较为为2)1)(2( nn次次。 执执行行第第 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次循环次

30、循环必结束必结束。必结束必结束。 在在第第 2 步中步中要做要做2)1)(2( nn次比较。次比较。 在在第第 3 步中步中要做要做2)1)(2( nn次加法和次加法和2)1)(2( nn次比较。次比较。 所以所以，总的计算量约为，总的计算量约为)(2nO。 第第41页页|最大流最小割定理最大流最小割定理 基本概念基本概念 主要结论主要结论|最大流算法最大流算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第42页页给给定定有有向向网网络络G=(N,A,C)，ijc表表示示弧弧Aji ),(的的容容量量，G有有一一个个发发点点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 步步 (构构造造最最小小割割)这这时时现现行行流流是是最最大大的的，若若把把所所有有标标号号点点的的集集合合记记 为为 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页页|最小费用流算法最小费用流算法 规划形式规划形式 算法步骤算法步骤 算例算例 算法复杂性算法复杂性|最特殊的最小费用流运输问题最特殊的最小费用流运输问题 规划形式规划形式 算法步骤算法步骤 算例算例 第第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。 算算法法的的循循环环次次数数取取决决于于点点的的 p(i)值值修修正正的的次次数数最最多多进进行行 mw 次次， 因因此此第第 2 步步的的计计算算量量为为)(2wmO。 如如果果最最大大流流值值为为 v，则则留留增增广广最最多多进进行行 v 次次， 所所以以第第 3 步步的的计计算算量量为为)(mvO。 第第 4 步步的的计计算算量量为为)(nmvO 所所以以，总总的的计计算算量量为为)(2mvwmO 。 第第58页页ia表示发点表示发点 i 可供应的产品数量可供应的产品数量),.,2 , 1(mi ； jb表示收点表示收点 j 所需的产

43、品数量所需的产品数量),.,2 , 1(nj ； ijw表示从发点表示从发点 i 到收点到收点 j 的单位产品运输费用；的单位产品运输费用； ijx表示从发点表示从发点 i 分配给收点分配给收点 j 的产品数量。的产品数量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw 第第59页页 ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 第第60页页第第 1 步步 (开开始始)任任给给原原始始规规划划的的可可行行解解ijx。 第第 2 步步 (计计算算

44、对对偶偶解解) 对对于于原原始始规规划划的的可可行行解解ijx，计计算算出出对对偶偶规规划划的的一一个个解解,jivu。 第第 3 步步 (计计算算检检验验数数)对对于于对对偶偶规规划划的的解解,jivu，计计算算 njmivuwwjiijij,.,2 , 1 ;,.,2 , 1 , 若若所所有有的的ijw均均非非负负，则则计计算算结结束束，这这时时得得到到的的ijx和和,jivu分分别别为为原原始始规规划划和和对对偶偶规规划划的的最最优优解解；否否则则，转转第第 4 步步。 第第 4 步步 (调调整整原原始始可可行行解解)令令0|min, ijijjistwww 即即选选择择stx进进入入基

45、基。对对应应于于网网络络中中，即即在在支支撑撑树树上上加加入入弧弧),(ts，从从而而得得到到一一个个回回路路。并并选选择择其其流流量量 stx，使使这这个个回回路路上上的的流流量量通通过过加加 或或减减 以以达达到到去去掉掉一一条条弧弧的的目目的的，从从而而得得到到一一个个新新的的被被改改进进的的原原始始可可行行解解ijx，转转第第 2 步步。 第第61页页求如图所示运输问题的最优解求如图所示运输问题的最优解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二分图的最大权对集分派问题二分图的最大权对集分派问题 规划形式规划形式 算法步骤算法步骤 算例算例第第72页页图图 G=(N,E)的的对对集集 M：M 是是 E 的的子子集集，且且 M 中中任任意意两两边边均均不不相相邻邻。 M - 饱饱和和点点 i：Ni ，且且 i 同同 M 的的一

48、一条条边边关关联联。 M - 非非饱饱和和点点 i：Ni ，且且 i 不不同同 M 的的任任一一条条边边关关联联。 G 的的完完美美对对集集 M：G 的的每每一一个个点点都都是是 M - 饱饱和和点点。 G 的的最最大大基基数数对对集集 M：不不存存在在另另外外一一个个对对集集另另外外一一个个对对集集 M，使使得得|MM ， 其其中中| M表表示示 M 的的基基数数。 G 的的一一条条 M -交交错错路路：边边在在对对集集 M 和和ME 中中交交错错出出现现的的路路。 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 - 非饱和点出发，用一个系统方非饱和点出发，用一个系统方 法法搜索一条搜

51、索一条 M - 增广路增广路 P。若若 P 存在，则通过交换存在，则通过交换 P 在在 M 和不在和不在 M 中的边，便得到一个其基数增加中的边，便得到一个其基数增加 1 的对集，然后从新的对集开始，继的对集，然后从新的对集开始，继 续迭代。续迭代。若若 P 不存在，则现行的对集就是不存在，则现行的对集就是 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 关关联联的的边边i , j，除除非非 j 已已经经被被标标号号；否否则则，给给点点 j 标标号号“i”， 转转向向(2.1)。 (2.3) 检检查查点点 i 的的标标号号如如下下：如如果果点点 i 是是非非饱饱和和点点，转转向向第第 3 步步；否否则则，辨

53、辨认认同同点点 i 关关联联的的属属于于 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