第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 6章章

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

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

5、如:(a):(a)是是 一简单图一简单图, ,但但(b)(b)就不是简单图就不是简单图. .(a)(b)续1第第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的补图的补图 : :与

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

7、两顶点之间都：在有向图中，如果任意两顶点之间都有存在方向互为相反的两条弧。有存在方向互为相反的两条弧。 含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？ 0123012n(n-1)/2n(n-1)续5第第12页页关联矩阵关联矩阵续6第第13页页右图的关联矩阵是右图的关联矩阵是 右图的关联矩阵是右图的关联矩阵是 135241 111000002 100110003 010101104 001001015 00001011143211110000210111103010101140000101图6.1.7图

8、6.1.8续7第第14页页邻接矩阵邻接矩阵续8第第15页页图（图（6.1.76.1.7）的邻接矩阵是）的邻接矩阵是 图（图（6.1.86.1.8）的邻接矩阵是）的邻接矩阵是 01110101011101110101011105432154321 010000001100011043214321143213524图6.1.7图6.1.8续9第第16页页几个基本结论几个基本结论握手定理握手定理续10第第17页页子子 图图续11第第18页页6.2 图的连通性图的连通性图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

9、）一条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中存在一条中存在一条ii，jj路路G G是是连通的连通的：G G中任意两点都是连通的中任意两点都是连通的 连通分支连通分支：G G的极大连通子图的极大连通子图 图图6.2.16.2.1中（中（a a）是连通图；（）是连通图；（b b）是一个具有）是一个具有三个连通分支的非连通图。三个连通分支的非连通图。 图6.2.2（a）（b）6.2 图的连通

10、性图的连通性第第20页页6.2 图的连通性图的连通性第第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) )有向路有向路 简单有向路简单有向路：弧不重的有向路：弧不重的有向路 初级有向路初级有向路：点不重的有向路：点不重的有向路 有向回路有向回路：至少包含一条弧且：至少包含一条弧且n ni i= =n nj j的的( (n ni i, ,n nj j) )有向路有向路 简单有向回路简单

11、有向回路：弧不重的有向回路：弧不重的有向回路 初级有向回路初级有向回路：点不重的有向回路：点不重的有向回路6.2 图的连通性图的连通性第第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,5,3,1)是一条有向回路；(1,2,3,4,5,3,1)是一条简单有向回路；(1,2,4,5,3,1)是一条初级有向回路。1654326.2 有向图的连通性有向图的连通性第第23页页点点i i和点和点j j是强连通的是强连通的：G G中存在一条中存在一

12、条( (i,j)i,j)有向路有向路, ,也也存在一条存在一条( (j,i)j,i)有向路有向路G是强连通的是强连通的：G G中任意两点都是强连通的中任意两点都是强连通的 G的强连通分支的强连通分支：G G的极大连通子图的极大连通子图图图6.2.4中，（中，（a）是一个强连通分支，（）是一个强连通分支，（b）是一个）是一个具有三个强连通分支的非强连通图。具有三个强连通分支的非强连通图。(a)(b)图6.2.46.2 有向图的连通性有向图的连通性第第24页页6.2 有向图的连通性有向图的连通性如何编写判断一个图（有向图）是否（强如何编写判断一个图（有向图）是否（强）连通的算法呢？）连通的算法呢？

13、第第25页页2. 割集割集6.2 图的连通性图的连通性第第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.66.2 图的连通性图的连通性第第27页页割割集集的的性性质质6.2 图的连通性图的连通性第第28页页6.3 树与支撑树树与支撑树1 1、树及其性质、树及其性质第第29页页6.3 树与支撑树树与支撑树-树的性质第第30页页6.3 树与支撑树树与支撑树-支撑树及其性质第第31页页6.4 最小树问题最小树问题|最小树及其性质最小树及其性质|求最小树的求最小树的Krus

14、kalKruskal算法算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性 |求最小树的求最小树的DijkstraDijkstra算法（又称算法（又称PrimPrim算法）算法） 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第32页页-最小树及其性质最小树及其性质6.4 最小树问题最小树问题第第33页页-求最小树的求最小树的Kruskal算法算法6.4 最小树问题最小树问题第第34页页DCBEAF251234192646382517例：例：6.4 最小树问题最小树问题-求最小树的求最小树的Kruskal算法的实例算法的实例第第35页页用用Kruskal算法求解下图所示网络的最小树，其

15、中每条算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。边上的数表示该边的权值。 1543212224443图6.4.16.4 最小树问题最小树问题-求最小树的求最小树的Kruskal算法的练习算法的练习第第36页页计算的迭代过程计算的迭代过程 154321154321215432122154321223第第37页页-Kruskal算法的算法复杂性分析算法的算法复杂性分析6.4 最小树问题最小树问题本算法遗留问题：本算法复杂性是如何算出来的？如何判断加入一条边后是否构成回路？“点的重新标号”是什么意思？a) 按什么数据结构存储和如何编程才能使得此算法节省时间？第第38页页6.4 最

16、小树问题最小树问题-求最小树的求最小树的Dijkstra算法算法注：在许多教科书上此算法叫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 6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实例算法的实例第第40页页例：例：DCBEAF251234192646381725(A, )(A, 34)(A, )(A, 46)(A, 19)(A, )6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第41页

17、页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(F,25)(C,17)6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第42页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第43页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)

18、(C,17)6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第44页页例：例：DCBEAF251234192646381725(A, )(A, 34)(F, 26)(F, 25)(A, 19)(C,17)6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第45页页例：例：DCBEAF251234192646381725(A, )(E, 12)(F, 26)(F, 25)(A, 19)(C,17)6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的实现算法的实现第第46页页1543212224443

19、图6.4.1用用算法求解下图所示网络的最小树，其中每条边上的算法求解下图所示网络的最小树，其中每条边上的数表示该边的权值。数表示该边的权值。6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法的练习算法的练习第第47页页15432122244431543212224443154321222444315432122244436.4 最小树问题最小树问题- Dijkstra算法的迭代过程算法的迭代过程 第第48页页6.4 最小树问题最小树问题-求最小树的求最小树的Dijkstra算法复杂性分析算法复杂性分析第第49页页6.5 最短有向路问题最短有向路问题|最短有向路方程最短有向路

20、方程|求最短有向路的求最短有向路的Dijkstra算法算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第50页页1. 最短有向路方程最短有向路方程6.5 最短有向路问题最短有向路问题第第51页页6.5 最短有向路问题最短有向路问题1. 最短有向路方程最短有向路方程第第52页页2. Dijkstra算法步骤：算法步骤： 6.5 最短有向路问题最短有向路问题注：本算法仅适用于弧的权值为正数的有向网络！第第53页页- 算例算例 用用Dijkstra算法求解下图所示有向网络中自点算法求解下图所示有向网络中自点1到到其他各点的最短有向路。其中每条弧上的数表示其他各点的最短有向路。其中每条弧上的数

21、表示其权值。其权值。16534251225343647图图6.5.16.5 最短有向路问题最短有向路问题第第54页页- 算法的实现过程算法的实现过程 1653425122534364716534251225343647053403546.5 最短有向路问题最短有向路问题（1 1） （2 2）第第55页页16534251225343647165342512253436470503431045886.5 最短有向路问题最短有向路问题- 算法的实现过程算法的实现过程 （3 3） （4 4）第第56页页16534251225343647165342512253436470034345888586.5

22、最短有向路问题最短有向路问题- 算法的实现过程算法的实现过程 （5 5） （6 6）第第57页页DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）6.5 最短有向路问题最短有向路问题当前状态下当前状态下v到此点的到此点的距离距离dist(i)当前状态下，当前状态下，v到此点的到此点的最短路上的最后的顶点最短路上的最后的顶点加加入入边边信信息息的的存存储储后后的的算算法法第第58页页加加入入边边信信息息的的存存储储后后的的算算法法DEBCA501030101002060(A, )(A, 10)(A, 30)(A, 100)(0, 0）(B,

23、 60)6.5 最短有向路问题最短有向路问题第第59页页DEBCA501030101002060(A, 10)(A, 30)(A, 100)(0, 0）(B, 60)(D, 50)(D, 90)加加入入边边信信息息的的存存储储后后的的算算法法6.5 最短有向路问题最短有向路问题第第60页页DEBCA501030101002060(A, 10)(A, 30)(D, 90)(0, 0）(D, 50)(C, 60)加加入入边边信信息息的的存存储储后后的的算算法法6.5 最短有向路问题最短有向路问题第第61页页DEBCA501030101002060(A, 10)(A, 30)(0, 0）(D, 50

24、)(C, 60)加加入入边边信信息息的的存存储储后后的的算算法法6.5 最短有向路问题最短有向路问题第第62页页- 算法复杂性算法复杂性6.5 最短有向路问题最短有向路问题如果大家想知道怎样求所有点对之间的最短路算法请大家看相关的参考资料第第63页页6.6 最大流问题最大流问题|最大流最小割定理最大流最小割定理 基本概念基本概念 主要结论主要结论|最大流算法最大流算法 算法步骤算法步骤 算例算例 算法复杂性算法复杂性第第64页页- 基本概念基本概念 -6.6 最大流问题最大流问题第第65页页-主要定理主要定理 -定定理理6.6.1（增增广广路路定定理理）一一个个可可行行流流是是最最大大流流当当

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

26、条弧上的数表示其容量。1653428695625378图图6.6.46.6 最大流问题最大流问题第第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.56.6 最

27、大流问题最大流问题第第69页页- 算法复杂性算法复杂性 -6.6 最大流问题最大流问题第第70页页6.7 最小费用流问题最小费用流问题|最小费用流算法最小费用流算法 规划形式规划形式 算法步骤算法步骤 算例算例 算法复杂性算法复杂性|最特殊的最小费用流运输问题最特殊的最小费用流运输问题 规划形式规划形式 算法步骤算法步骤 算例算例 第第71页页问问 题题第第72页页线性规划形式线性规划形式 ),( ,0 , , , 0)( )( )( . t . s min),(AjicxtsiNixxvxxvxxxwijijjjiijjjttjjjssjAjiijij 第第73页页对偶规划对偶规划 ,)(

28、),( , 0),( ,)()( . t . s )()( max),(NiipAjirAjiwripjprcvspvtpijijijAjiijij无无限限制制 第第74页页算法步骤算法步骤 第第75页页算例算例 求解下图所示网络中自点求解下图所示网络中自点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

29、,01,2,03,4,03,1,00111stba( ,) (,2)s计算的迭代过程（计算的迭代过程（1）第第77页页计算的迭代过程（计算的迭代过程（2）stba1,2,01,2,01,2,03,4,03,1,00220stba( ,) stba1,2,01,2,01,2,03,4,03,1,00231stba( ,) (,2)a(,2)s(,2)b(,2)a第第78页页计算的迭代过程（计算的迭代过程（3）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页页

30、计算的迭代过程（计算的迭代过程（4）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)值值修修正正的的次次数数最最多多进进行行 mw 次次， 因因此此第第 2 步步的的计计算算量量为为)(2wmO。 如如果果最最大大流流值值为为 v，则则留留增增广广最最多多进进行行 v 次次， 所所以以第第 3

31、步步的的计计算算量量为为)(mvO。 第第 4 步步的的计计算算量量为为)(nmvO 所所以以，总总的的计计算算量量为为)(2mvwmO 。 第第81页页运输问题运输问题ia表示发点表示发点 i 可供应的产品数量可供应的产品数量),.,2 , 1(mi ； jb表示收点表示收点 j 所需的产品数量所需的产品数量),.,2 , 1(nj ； ijw表示从发点表示从发点 i 到收点到收点 j 的单位产品运输费用；的单位产品运输费用； ijx表示从发点表示从发点 i 分配给收点分配给收点 j 的产品数量。的产品数量。 0),.,2 , 1( , ),.,2 , 1( , . t . s min,ij

32、ijijjiijjiijijxnjbxmiaxxw 第第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 初始原可行解初始原可行解 第第86页页续（续（1）213123486121014对偶解对偶解第第87页页w w8 -6 -10

33、-29 809 -12 513 -7 5114 29 -116 -5 -486121 u V第第88页页续（续（2） 15- 20 30+ 20- 10 302131234调整原始可行解调整原始可行解第第89页页续（续（3）213123403666101对偶解对偶解第第90页页8 26 -10 -9 909 -12 313 -7 5314 29 -316 -5 -66610-1 第第91页页续（续（4） 20- 45 15+ 5 10- 302131234调整原始可行解调整原始可行解第第92页页续（续（5）102131234033662对偶解对偶解第第93页页w w8 26 -10 -9 70

34、9 -12 313 -7 2314 59 -16 35 -366102 u V第第94页页6.8 最大对集问题最大对集问题v二分图的对集二分图的对集 基本概念基本概念 主要定理主要定理v二分图的最大基数对集二分图的最大基数对集 基本思想基本思想 算法步骤算法步骤 算例算例 算法复杂性算法复杂性v二分网络的最大权对集分派问题二分网络的最大权对集分派问题 规划形式规划形式 算法步骤算法步骤 算例算例第第95页页基本概念基本概念第第96页页主要定理主要定理第第97页页基本思想基本思想第第98页页算法步骤算法步骤第第99页页算例算例求下图求下图a a所示的二分图所示的二分图G G的最大基数对集，若初始解如下图的最大基数对集，若初始解如下图b b所示所示1234567A98a1234567A98b第第100页页迭代过程（迭代过程（1）1234567A9831333标号标号1234567A98333517810标号标号1234567A98增广路增广路1234567A98增广路增广路第第101页页迭代过程（迭代过程（2）1234567A9812