第6章图与网络分析

1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外图与网络分析图与网络分析Graphs and Network AnalysisGraphs and Network Analysis第第2页页Leonhard Euler(公元1707-1783年)欧拉1707年出生在瑞士的巴塞尔城，13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰.伯努利的精心指导。他从19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数

2、，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。 1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。第第3页页哥尼斯堡七桥问题能否从某个地方出发，穿过所有的桥各一次能否从某个地方出发，穿过所有的桥各一次后再回到出发点。后再回到出发点。ACDB图论模型第第4页页|6.1 图与子

3、图图与子图|6.2 图的连通性图的连通性|6.3 树与支撑树树与支撑树|6.4 最小树问题最小树问题|6.5 最短有向最短有向路路问题问题|6.6 最大最大流流问题问题|6.7 最小费用最小费用流流问题问题|6.8 最大最大对集对集问题问题第第5页页|图与网络图与网络 无向图的基本概念无向图的基本概念 有向图和网络有向图和网络|关联矩阵和邻接矩阵关联矩阵和邻接矩阵 关联矩阵关联矩阵 邻接矩阵邻接矩阵 主要结论主要结论|子图子图 第第6页页1n1n 图6.1.12n3n4n11e12e14e24e23e34e34e5n关联关联：一条边的端点称为与这条边的关联：一条边的端点称为与这条边的关联邻接邻

4、接：与同一条边关联的端点称为是邻接的，同时如果两条边：与同一条边关联的端点称为是邻接的，同时如果两条边 有一个公共端点，则称这两条边是邻接的有一个公共端点，则称这两条边是邻接的有限图有限图：任何图：任何图G=(N,E),G=(N,E),若若N N和和E E都是有限集合都是有限集合, ,则称则称G G为为空图空图：没有任何边的图：没有任何边的图平凡图平凡图：只有一个点的图：只有一个点的图简单图简单图：一个图：一个图, ,既没有环既没有环, ,也没有重边也没有重边, ,则称为则称为 例如例如:(a):(a)是是 一简单图一简单图, ,但但(b)(b)就不是简单图就不是简单图. .(a)(b)续1第

5、第8页页完全图完全图：每一对点之间均有一条边相连的图：每一对点之间均有一条边相连的图二分图二分图 G=G=( (N,EN,E) )：存在的一个二分划存在的一个二分划( (S S, ,T T) )，使得使得G G的的每条边有一个端点在每条边有一个端点在S S中，另一个端点在中，另一个端点在T T中中完全二分图完全二分图 G=(S,T,E)G=(S,T,E)：S S中的每个点与中的每个点与T T中的每个点中的每个点都相连的简单二分图都相连的简单二分图简单图简单图G G的补图的补图 : :与与G G有相同顶点集合的简单图，且补有相同顶点集合的简单图，且补图中的两个点相邻当且仅当它们在图中的两个点相邻

6、当且仅当它们在G G中不相邻中不相邻图6.1.3(b)(a)续23n1n4n2n续3第第10页页7BADC2358设G是一个图（有向图），若对G的每条边（弧）都赋予一个实数，并称为这条边（弧）的权，则G连同它边（弧）上的权称为一个（有向）网络或赋权（有向）图，记为G=(N,E,W).1543212224443图6.4.1续4无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间存在边。存在边。 有向完全图有向完全图：在有向图中，如果任意两顶点之间都：在有向图中，如果任意两顶点之间都有存在方向互为相反的两条弧。有存在方向互为相反的两条弧。 含有含有n个顶点的无向

7、完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？ 0123012n(n-1)/2n(n-1)续5续6右图的关联矩阵是右图的关联矩阵是 右图的关联矩阵是右图的关联矩阵是 135241 111000002 100110003 010101104 001001015 00001011143211110000210111103010101140000101图6.1.7图6.1.8续7续8图（图（6.1.76.1.7）的邻接矩阵是）的邻接矩阵是 图（图（6.1.86.1.8）的邻接矩阵是）的邻接矩阵是 0111010101110111

8、0101011105432154321 010000001100011043214321143213524图6.1.7图6.1.8续9第第16页页握手定理握手定理续10第第17页页续11第第18页页图6.2.1:(1,2,3,4,2,3,5,6)是一条1,6路；(1,2,4,5,3,4,6)是一条1,6简单路；(1,2,3,5,6）一条1,6初级路；(1,2,4,3,2,4,5,3,1)是一条回路；(1,2,3,4,5,3,1）是一条简单回路；(1,2,4,5,3,1)是一条初级回路。165432图6.2.11.图的连通第第19页页点点i i和和j j点是点是连通的连通的：G G中存在一条中存

9、在一条ii，jj路路G G是是连通的连通的：G G中任意两点都是连通的中任意两点都是连通的 连通分支连通分支：G G的极大连通子图的极大连通子图 图图6.2.16.2.1中（中（a a）是连通图；（）是连通图；（b b）是一个具有）是一个具有三个连通分支的非连通图。三个连通分支的非连通图。 图6.2.2（a）（b）第第20页页第第21页页有向图有向图G G中的一条有向路中的一条有向路：个点和弧的交错序列：个点和弧的交错序列 ( (n ni i, ,a aijij, ,n nj j, , ,n nk k, ,a aklkl, ,n nl l) )， 记为记为( (n ni i, ,n nl l)

10、 )有向路有向路 简单有向路简单有向路：弧不重的有向路：弧不重的有向路 初级有向路初级有向路：点不重的有向路：点不重的有向路 有向回路有向回路：至少包含一条弧且：至少包含一条弧且n ni i= =n nj j的的( (n ni i, ,n nj j) )有向路有向路 简单有向回路简单有向回路：弧不重的有向回路：弧不重的有向回路 初级有向回路初级有向回路：点不重的有向回路：点不重的有向回路第第22页页如下图：(1,2,4,3,2,4,6)是一条(1,6)有向路; (1,2,4,5,3,4,6)是一条(1，6)简单有向路; (1,2,3,4,6)是一条（1，6）初级有向路；(1,2,4,3,2,4

11、,5,3,1)是一条有向回路；(1,2,3,4,5,3,1)是一条简单有向回路；(1,2,4,5,3,1)是一条初级有向回路。165432第第23页页点点i i和点和点j j是强连通的是强连通的：G G中存在一条中存在一条( (i,j)i,j)有向路有向路, ,也也存在一条存在一条( (j,i)j,i)有向路有向路G是强连通的是强连通的：G G中任意两点都是强连通的中任意两点都是强连通的 G的强连通分支的强连通分支：G G的极大连通子图的极大连通子图图图6.2.4中，（中，（a）是一个强连通分支，（）是一个强连通分支，（b）是一个）是一个具有三个强连通分支的非强连通图。具有三个强连通分支的非强

12、连通图。(a)(b)图6.2.4第第24页页如何编写判断一个图（有向图）是否（强如何编写判断一个图（有向图）是否（强）连通的算法呢？）连通的算法呢？第第25页页第第26页页1765423图6.2.5中2，4和6，7都是割边图6.2.6中，边集2，1，2，4，2，3和边集2，3，2，4，1，4，1，5均为割集15432图6.2.5图6.2.6第第27页页第第28页页1 1、树及其性质、树及其性质第第29页页-树的性质第第30页页-支撑树及其性质第第31页页|最小树及其性质最小树及其性质|求最小树的求最小树的KruskalKruskal算法算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性 |

13、求最小树的求最小树的DijkstraDijkstra算法（又称算法（又称PrimPrim算法）算法） 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第32页页第第33页页第第34页页DCBEAF251234192646382517例：例：第第35页页用用Kruskal算法求解下图所示网络的最小树，其中每条算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。边上的数表示该边的权值。 1543212224443图6.4.1第第36页页154321154321215432122154321223第第37页页本算法遗留问题：本算法复杂性是如何算出来的？如何判断加入一条边后是否构成回路？“

14、点的重新标号”是什么意思？a) 按什么数据结构存储和如何编程才能使得此算法节省时间？第第38页页注：在许多教科书上此算法叫Prim算法第第39页页U=A U=A，F 例：例：DCBEAF251234192646381725U=A，F，C U=A，F，C，D U=A，F，C，D，E U=A，F，C，D，E，B 第第40页页例：例：DCBEAF251234192646381725(A, )(A, 34)(A, )(A, 46)(A, 19)(A, )第第41页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(F,25)(C

15、,17)第第42页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第43页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第44页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)第第45页页例：例：DCBEAF251234192646381725(A, )(E, 12)(F, 26)(F, 25)(A, 19)(C,17)第第46

16、页页1543212224443图6.4.1用用算法求解下图所示网络的最小树，其中每条边上的算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。数表示该边的权值。第第47页页1543212224443154321222444315432122244431543212224443第第48页页第第49页页|最短有向路方程最短有向路方程|求最短有向路的求最短有向路的Dijkstra算法算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第50页页第第51页页第第52页页注：本算法仅适用于弧的权值为正数的有向网络！第第53页页 用用Dijkstra算法求解下图所示有向网络中自点算法求解下图

17、所示有向网络中自点1到到其他各点的最短有向路。其中每条弧上的数表示其他各点的最短有向路。其中每条弧上的数表示其权值。其权值。16534251225343647图图6.5.1第第54页页165342512253436471653425122534364705340354（1 1） （2 2）第第55页页1653425122534364716534251225343647050343104588（3 3） （4 4）第第56页页1653425122534364716534251225343647003434588858（5 5） （6 6）第第57页页DEBCA501030101002060(A,

18、 )(A, 10)(A, 30)(A, 100)(0, 0）当前状态下当前状态下v到此点的到此点的距离距离dist(i)当前状态下，当前状态下，v到此点的到此点的最短路上的最后的顶点最短路上的最后的顶点加加入入边边信信息息的的存存储储后后的的算算法法第第58页页加加入入边边信信息息的的存存储储后后的的算算法法DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)第第59页页DEBCA501030101002060(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)(D, 50)(D, 90)加加入入边边信信息息

19、的的存存储储后后的的算算法法第第60页页DEBCA501030101002060(A, 10)(A, 30)(D, 90)(0, 0）(D, 50)(C, 60)加加入入边边信信息息的的存存储储后后的的算算法法第第61页页DEBCA501030101002060(A, 10)(A, 30)(0, 0）(D, 50)(C, 60)加加入入边边信信息息的的存存储储后后的的算算法法第第62页页如果大家想知道怎样求所有点对之间的最短路算法请大家看相关的参考资料第第63页页|最大流最小割定理最大流最小割定理 基本概念基本概念 主要结论主要结论|最大流算法最大流算法 算法步骤算法步骤 算例算例 算法复杂性

20、算法复杂性第第64页页第第65页页定定理理6.6.1（增增广广路路定定理理）一一个个可可行行流流是是最最大大流流当当且且仅仅当当不不存存在在 关关于于它它的的从从s到到t的的增增广广路路。 定定理理6.6.2（整整流流定定理理）如如果果网网络络中中所所有有弧弧容容量量是是整整数数，则则存存在在 值值为为整整数数的的最最大大流流。 定定理理6.6.3（最最大大流流最最小小割割定定理理）一一个个(s,t)-流流的的最最大大值值等等于于(s,t)-割割 的的最最小小容容量量。 第第66页页第第67页页 求解下图所示有向网络中自点求解下图所示有向网络中自点1到点到点6的最大流。的最大流。其中每条弧上的

21、数表示其容量。其中每条弧上的数表示其容量。1653428695625378图图6.6.4第第68页页1653428,66,49,75,26,62,15,13,27,08,61653428,66,49,75,26,62,15,13,27,08,6( ,) ( 4,2)( 2,2)( 1,1)( 2,2)( 1,2)1653428,86,49,95,46,62,15,13,27,08,6( ,) ( 5,1)( 2,1)( 1,1)( 2,1)( 3,1)1653428,86,49,95,46,52,25,13,17,18,6( ,) 图图6.6.5第第69页页第第70页页|最小费用流算法最小费用

22、流算法 规划形式规划形式 算法步骤算法步骤 算例算例 算法复杂性算法复杂性|最特殊的最小费用流运输问题最特殊的最小费用流运输问题 规划形式规划形式 算法步骤算法步骤 算例算例 第第71页页第第72页页 ),( ,0 , , , 0)( )( )( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij 第第73页页 ,)( ),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij无无限限制制 第第74页页第第75页页 求解下图所示网络中自

23、点求解下图所示网络中自点1到点到点4其值为其值为3的的最小费用流。其中每条弧上的第一个数表示最小费用流。其中每条弧上的第一个数表示单位流的费用，第二个数表示容量。单位流的费用，第二个数表示容量。stba1,21,21,23,43,1图图6.7.1第第76页页stba1,2,01,2,01,2,03,4,03,1,00000stba( ,) stba1,2,01,2,01,2,03,4,03,1,00111stba( ,) (,2)s第第77页页stba1,2,01,2,01,2,03,4,03,1,00220stba( ,) stba1,2,01,2,01,2,03,4,03,1,00231s

24、tba( ,) (,2)a(,2)s(,2)b(,2)a第第78页页stba1,2,21,2,21,2,03,4,03,1,00231stba( ,) stba1,2,21,2,21,2,23,4,03,1,00342stba( ,) (,1)b第第79页页stba1,2,21,2,21,2,23,4,03,1,00352stba( ,) stba1,2,21,2,21,2,13,4,13,1,1(,1)b(,1)s(,1)a第第80页页设设网网络络的的点点数数为为 n，弧弧数数为为 m，弧弧的的最最大大容容量量为为 w。 算算法法的的循循环环次次数数取取决决于于点点的的 p(i)值值修修正正

25、的的次次数数最最多多进进行行 mw 次次， 因因此此第第 2 步步的的计计算算量量为为)(2wmO。 如如果果最最大大流流值值为为 v，则则留留增增广广最最多多进进行行 v 次次， 所所以以第第 3 步步的的计计算算量量为为)(mvO。 第第 4 步步的的计计算算量量为为)(nmvO 所所以以，总总的的计计算算量量为为)(2mvwmO 。 第第81页页ia表示发点表示发点 i 可供应的产品数量可供应的产品数量),.,2 , 1(mi ； jb表示收点表示收点 j 所需的产品数量所需的产品数量),.,2 , 1(nj ； ijw表示从发点表示从发点 i 到收点到收点 j 的单位产品运输费用；的单

26、位产品运输费用； ijx表示从发点表示从发点 i 分配给收点分配给收点 j 的产品数量。的产品数量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ijijijjiijjiijijxnjbxmiaxxw 第第82页页 ),.,2 , 1;,.,2 , 1( , . t . s maxnjmiwvuvbuaijjijjjiii 第第83页页第第84页页 求如图所示运输问题的最优解求如图所示运输问题的最优解14321328106355169147131299-30-30-20-454050图图6.7.4第第85页页2131234 15 20 30 20 10 30

27、初始原可行解初始原可行解 第第86页页213123486121014对偶解对偶解第第87页页w w8 -6 -10 -29 809 -12 513 -7 5114 29 -116 -5 -486121 u V第第88页页 15- 20 30+ 20- 10 302131234调整原始可行解调整原始可行解第第89页页213123403666101对偶解对偶解第第90页页8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610-1 第第91页页 20- 45 15+ 5 10- 302131234调整原始可行解调整原始可行解第第92页页1021312340

28、33662对偶解对偶解第第93页页w w8 26 -10 -9 709 -12 313 -7 2314 59 -16 35 -366102 u V第第94页页v二分图的对集二分图的对集 基本概念基本概念 主要定理主要定理v二分图的最大基数对集二分图的最大基数对集 基本思想基本思想 算法步骤算法步骤 算例算例 算法复杂性算法复杂性v二分网络的最大权对集分派问题二分网络的最大权对集分派问题 规划形式规划形式 算法步骤算法步骤 算例算例第第95页页第第96页页第第97页页第第98页页第第99页页求下图求下图a a所示的二分图所示的二分图G G的最大基数对集，若初始解如下图的最大基数对集，若初始解如下

29、图b b所示所示1234567A98a1234567A98b第第100页页1234567A9831333标号标号1234567A98333517810标号标号1234567A98增广路增广路1234567A98增广路增广路第第101页页1234567A981257108标号标号1234567A98增广路增广路第第102页页若令若令mS |，nT |，且，且nm 。 在找到一个匈牙利树或找到一条增广路之前，在找到一个匈牙利树或找到一条增广路之前， 标标号程序最多进行号程序最多进行)(mnO次；次； 在求出所需的对集之前，初始对集最多能增广在求出所需的对集之前，初始对集最多能增广 m 次；次； 所以，总的计算量为所以，总的计算量为)(2nmO。 第第103页页设二分网络是完全的设二分网络是完全的),(