第三章图与网络技术精选文档.ppt

《第三章图与网络技术精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章图与网络技术精选文档.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第三章 图与网络技术2022/9/25本讲稿第一页，共五十页图的概念图的概念所谓图，就是顶点和边的集合，点的集合记为所谓图，就是顶点和边的集合，点的集合记为V，边的集合记为边的集合记为E，则图可以表示为：，则图可以表示为：G（V，E），），点代表被研究的事物，边代表事物之间的联系，因点代表被研究的事物，边代表事物之间的联系，因此，边不能离开点而独立存在，每条边都有两个端此，边不能离开点而独立存在，每条边都有两个端点。点。在画图时，顶点的位置、边和长短形状都是无关在画图时，顶点的位置、边和长短形状都是无关紧要的，只要两个图的顶点及边是对应相同的，紧要的，只要两个图的顶点及边是对应相同的，则两个图

2、相同。则两个图相同。第一节 图的基本概念2022/9/25本讲稿第二页，共五十页1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：简单图：无环、无多重边的图。2022/9/25本讲稿第三页，共五十页2.关联与相邻3.链与圈2022/9/25本讲稿第四页，共五十页4.有向图与无向图，圈，回路比较：2022/9/25本讲稿第五页，共五十页一个没有圈的图称为一个无圈图或称为林。一个没有圈的图称为一个无圈图或称为林。一一个个连连通通的的无无圈圈图图则则称称为为树树，一一个个林林的的每每个个连连通通子子图图都都是是一个树。一个树。定理定理以下关于树

3、的六种不同描述是等价的：以下关于树的六种不同描述是等价的：无圈连通图。无圈连通图。无圈，无圈，q=p-1。连通，连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。5.树2022/9/25本讲稿第六页，共五十页6.图的部分（支撑）树 若图G=（V，E）的子图T=（V，E）是树，则称T为G的部分树或支撑树。特点边少、点不少。性质：G连通，则G必有部分树。证：破圈、保连通。2022/9/25

4、本讲稿第七页，共五十页第二节 网络分析网络赋权图，记D=（V，E，C），其中C=c1，cn，ci为边ei上的权（设ci ）。网络分析主要内容最小部分树、最短路、最大流。图只能用来研究事物之间有没有某种关系，而不能研图只能用来研究事物之间有没有某种关系，而不能研究这种关系的强弱程度。究这种关系的强弱程度。2022/9/25本讲稿第八页，共五十页一.最小部分（支撑）树问题问题：求网络D的部分树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如图网络的最小部分树。v5v1v3v6v4v2v72552335757112022/9/25本讲稿第九页，共五十

5、页避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中2022/9/25本讲稿第十页，共五十页用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？见圈就破，去掉其中权最大的。2022/9/25本讲稿第十一页，共五十页二.最短路问题1.问题：求网络D中一定点v1到其它点的最短路。例3 求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v72552335757112.方法：标

6、号法（Dijkstra，1959）给每点vj标号dj，vi，其中dj为v1至vj的最短距，vi为最短路上的前一点。2022/9/25本讲稿第十二页，共五十页标号法步骤：2022/9/25本讲稿第十三页，共五十页用标号法解例3v5v1v3v6v4v2v72552335757110，v12，v13，v1其中2=min0+2,0+5,0+3其中3=min0+3，0+5，2+2，2+74，v27，v38，v513，v6最短距为13；最短路为v1-v2-v3-v5-v6-v7。2022/9/25本讲稿第十四页，共五十页最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格

7、以及一辆汽车的使用维修费用(万元)：年号 1 2 3 4 5 价格22.12.32.42.6 汽车使用年龄0112233445维修费用0.71.11.522.5试用网络分析中求最短路的方法确定公司可采用的最优策略。方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。2022/9/25本讲稿第十五页，共五十页所所谓谓最最大大流流问问题题就就是是在在一一定定的的条条件件下下，要要求求流流过过网网络络的的物物流流、能能量量流流或或信信息息流流等等流流量量为为最最大大的的问问题题，在在最最大大流流问问题题中一般有如下规定：中一般有如下规定：网络有一个起点网络有一个起点s和一个终点和一个终点t

8、网络是有向网络，即流有方向性。网络是有向网络，即流有方向性。在在网网络络各各条条弧弧上上都都有有一一个个权权，表表示示允允许许流流过过的的最最大大流流量量。若若以以cij表表示示由由i到到j的的弧弧上上允允许许流流过过的的最最大大流流量量，以以xij表表示示实实际流过该弧的流量，则际流过该弧的流量，则0 xijcij网网络络中中，除除起起点点s和和终终点点t之之外外的的任任何何顶顶点点，流流入入量量总总和和应应该该等于流出量的总和。等于流出量的总和。三.最大流问题2022/9/25本讲稿第十六页，共五十页最大流问题的数学模型最大流问题的数学模型最大流最大流问题的问题的数学模型：数学模型：vs1

9、01165473915vtv5v3v4v22022/9/25本讲稿第十七页，共五十页最大流最小割集定理最大流最小割集定理1网网络络中中的的最最大大流流量量fmax值值大大小小是是由由网网络络中中最最狭窄处瓶颈的容量所决定的。狭窄处瓶颈的容量所决定的。最最大大流流最最小小割割集集定定理理揭揭示示了了最最小小割割集集（网网络络中中的的瓶瓶颈颈）容容量量与与最大流量的关系，也提供了一个求最大流的方法。最大流量的关系，也提供了一个求最大流的方法。割集割集网络割集容量网络割集容量最小割集最小割集所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。2022/9/25本讲稿第十八页，共五十页最大流最

10、小割集定理最大流最小割集定理2网网络络中中的的最最大大流流量量fmax值值大大小小是是由由网网络络中中最最狭狭窄处瓶颈的容量所决定的。窄处瓶颈的容量所决定的。网络割集容量网络割集容量最小割集最小割集所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。最大流最小割集定理最大流最小割集定理流过网络的最大流量等于最小割集的容量。流过网络的最大流量等于最小割集的容量。2022/9/25本讲稿第十九页，共五十页最大流最小割集定理最大流最小割集定理3vs101165473915vtv5v3v4v2SS割集割集容量容量vsv2v3v4v5vt(vsv2)(vsv3)24vsv2v3v4v5vt(vs

11、v3)(v2v4)(v2v5)20vsv3v2v4v5vt(vsv2)(v3v2)(v3v4)(v3v5)29.2022/9/25本讲稿第二十页，共五十页福德富克逊方法原理福德富克逊方法原理算法的原理算法的原理首首先先，依依据据最最大大流流问问题题的的要要求求，为为网网络络分分配配一一个个可可行行流流。所所谓谓可可行行流流，是是指指所所有有弧弧上上流流量量满满足容量限制，所有中间点满足平衡条件的流；足容量限制，所有中间点满足平衡条件的流；若若这这一一可可行行流流的的流流量量就就是是最最大大流流量量，则则问问题题已经解决；已经解决；若若不不是是最最大大流流量量，则则增增加加流流量量获获得得流流量

12、量更更大大的可行流。的可行流。2022/9/25本讲稿第二十一页，共五十页福德富克逊方法流图福德富克逊方法流图求一个初始可行流求一个初始可行流是是判断初始可行流是否最优判断初始可行流是否最优结结束束不是不是求使目标得到改善的可行流求使目标得到改善的可行流2022/9/25本讲稿第二十二页，共五十页福德富克逊方法图示福德富克逊方法图示算法原理图示算法原理图示初始流初始流初始流初始流2022/9/25本讲稿第二十三页，共五十页福德富克逊方法讨论福德富克逊方法讨论若若弧弧(vi,vj)上上的的流流量量满满足足xij=cij，则则称称该该弧弧为为饱饱和和弧弧，否否则则称称为非饱和弧。为非饱和弧。若若弧

13、弧(vi,vj)上上的的流流量量xij=0。则则称称该该弧弧为为零零流流弧弧，否否则则称称为为非零流弧。非零流弧。一一条条从从s到到t的的初初等等链链是是由由s开开始始的的点点、边边序序列列，其其中中没没有相同的点，也不考虑弧的方向。有相同的点，也不考虑弧的方向。把这条链中的把这条链中的s到到t方向相同的弧称为正向弧。方向相同的弧称为正向弧。把这条链中的把这条链中的s到到t方向相反的弧称为逆向弧。方向相反的弧称为逆向弧。在上述的可行流中，从在上述的可行流中，从s到到t的某个初等链满足：的某个初等链满足：其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均

14、为非零流弧。则称该链为一条则称该链为一条流量增广链流量增广链。2022/9/25本讲稿第二十四页，共五十页福德富克逊方法讨论福德富克逊方法讨论流量增广链流量增广链:从从s到到t的某个初等链满足的某个初等链满足其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。结结论论：若若在在可可行行流流中中，存存在在从从s到到t的的增增广广链链，则则该该可可行行流流不不是是最最大大流流，其其流流量量可可以以增增加加；否否则则若若不不存在从存在从s到到t的增广链，则该可行流是最大流。的增广链，则该可行流是最大流。2022/9/25本讲稿第二十五页，共五十页增

15、广链的性质增广链的性质流量增广链流量增广链:从从s到到t的某个初等链满足的某个初等链满足其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。增广链的性质：增广链的性质：1Vs到增广链上任一点也有增广链到增广链上任一点也有增广链;2增广链上任一点到增广链上任一点到Vt也有增广链也有增广链;2022/9/25本讲稿第二十六页，共五十页福德富克逊方法步骤福德富克逊方法步骤算法的步骤算法的步骤：为网络分配初始流为网络分配初始流xij标在图中弧旁的标在图中弧旁的()内内寻求增广链，若不存在，则已最优寻求增广链，若不存在，则已最优,否则否则在增广链上调整

16、流量，产生新的可行流。在增广链上调整流量，产生新的可行流。重复重复、两步，直到最优。两步，直到最优。2022/9/25本讲稿第二十七页，共五十页寻求增广链的方法寻求增广链的方法寻寻求求流流量量增增广广链链的的方方法法，是是依依据据增增广广链链的的性性质质而而产生的，其基本思路类似于最短树问题的生长法。产生的，其基本思路类似于最短树问题的生长法。从从s开开始始，逐逐个个检检查查每每个个点点i，看看是是否否存存在在从从s到到i的增广链。的增广链。如果存在从如果存在从s到到i的增广链，的增广链，而（而（ViVj）非饱和或（）非饱和或（VjVi）非零流，）非零流，则存在从则存在从V1到到Vj的增广链。

17、的增广链。2022/9/25本讲稿第二十八页，共五十页福德富克逊方法示例福德富克逊方法示例标记化算法的步骤标记化算法的步骤：为网络分配初始流为网络分配初始流xij标在图中弧旁的标在图中弧旁的()内内vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)2022/9/25本讲稿第二十九页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链从从s开开始始，赋赋上上标标记记（，），表表示示s是是源源点点，能能够够得得到到任任意意多多的的量量。s称称为为已已标标记记的的点点。也也表表示示增增广链可以从广链可以从V1延伸到延伸到V1vs101156

18、473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)-,2022/9/25本讲稿第三十页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链如果如果vi是已经标记的点是已经标记的点,vj是未标记的点是未标记的点则当则当(vi,vj)是非饱和弧时是非饱和弧时,vj可以标记可以标记:vi+,ejej=minei,bij-xij当当(vj,vi)是非零流弧时是非零流弧时,vj可以标记可以标记:vi-,ejej=minei,xji如果如果vt可以标记可以标记,则找到增广链则找到增广链,否则继续否则继续.如如果果对对于于一一切切未未标标记记的的点点,均均不不能能

19、再再标标记记,则则已已经经是是最最优优.2022/9/25本讲稿第三十一页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链如图如图v1是已经标记的点是已经标记的点,其它点是未标记的点其它点是未标记的点(v1,v2)是非饱和弧是非饱和弧,v2可以标记可以标记:v1+,e2e2=mine1,b12-x12(v1,v3)是是饱饱和和弧弧,目目前前v3和和其其它它点点暂暂时时不不能能标标记记，即暂时没有从即暂时没有从v1到到v3或其它点的增广链。或其它点的增广链。vs101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)-,vs+,112022/

20、9/25本讲稿第三十二页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链如图如图v2是已经标记的点是已经标记的点,v3是未标记的点是未标记的点(v3,v2)是非零流弧是非零流弧,v3可以标记可以标记:v2-,e3e3=mine2,x32=min11,3-,vs+,11v2-,3v2+,4v3+,3v5+,4vs1154315vtv5v3v4v2(4)(9)(1)(5)(7)(5)(8)1079(3)62022/9/25本讲稿第三十三页，共五十页福德富克逊方法示例福德富克逊方法示例在增广链上调整流量。在增广链上调整流量。vt已经标记已经标记,找到流量增广链。找到流量增广链。vs

21、101156473915vtv5v3v4v2(4)(9)(3)(1)(5)(7)(5)(8)-,vs+,11v2-,3v2+,4v3+,3v5+,4正向流流量增加正向流流量增加et，逆向流流量减少，逆向流流量减少et调整后流量调整后流量f=172022/9/25本讲稿第三十四页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链vs101154315vtv5v3v4v2(8)(9)(3)(1)(5)(7)(9)(8)(4)967-,vs+,7v2-,3v3+,1v3+,3v4+,3vt已经标记已经标记,找到流量增广链。找到流量增广链。2022/9/25本讲稿第三十五页，共五十页福

22、德富克逊方法示例福德富克逊方法示例在增广链上调整流量。在增广链上调整流量。正向流流量增加正向流流量增加et=3，逆向流流量减少，逆向流流量减少et调整后流量调整后流量f=20vs101154315vtv5v3v4v2(11)(9)(4)(5)(7)(9)(11)(4)9672022/9/25本讲稿第三十六页，共五十页福德富克逊方法示例福德富克逊方法示例寻求增广链寻求增广链Vsv2已经标记，其余点不能标记，已经最优已经标记，其余点不能标记，已经最优最大流量最大流量fmax=20vs101154315vtv5v3v4v2(11)(9)(4)(5)(7)(9)(11)(4)967-,vs+,4202

23、2/9/25本讲稿第三十七页，共五十页一、工程计划网络问题（关键路径法）1.问题的一般提法 设：有一项工程，分为若干道工序；已知各工序 间的先后关系，以及各工序所需时间t。问：（1）工程完工期T=？（2）工程的关键工序有哪些？2.解法关键路径法（CPM）（1）绘制工程网络图第六章 网络计划2022/9/25本讲稿第三十八页，共五十页1）顺序：按工序先后从左至右；2）图中弧（箭线）：表示工序；顶点（结点）：表示相邻工序的时间分 界点，称事项，用 表示。相邻弧：表示工序前后衔接关系，称紧 前（后）工序；3）要求：图中不得有缺口、回路和多重边。i缺口：多个始点或多个终点的现象。（应当只有一个始点和终

24、点）回路：方向一致的闭合链。2022/9/25本讲稿第三十九页，共五十页例1 为筹建某餐馆，需制定计划。将工程分为14道工序，各工序需时及先后关系如下表。试求该工程完工期T及关键路径。多重边：两点间有多于一条的边。AB处理方法：增加虚工序。AAB2022/9/25本讲稿第四十页，共五十页工序内容紧前工序所需天数A购买炉灶及材料10B购买室内设备3C招集工人1D选择开业地点2E申请许可得到执照D7F修理门窗、粉刷墙壁E3G砌炉灶、水池A、F5H接通上下水道G4I安装室内设备B、H4J做好室内装饰B、H3K购进米面及副食品I、J6L张贴开业广告G3M人员训练C、I4N开业前操作试验K、L72022

25、/9/25本讲稿第四十一页，共五十页工序ABCDEFGHIJKLMN紧前工序_DEAFGBHBHIJGCIKL所需天数1031273544363471CBAD2E3F4G5H6IJ7I8KL9IM10N112022/9/25本讲稿第四十二页，共五十页（2）求完工期（用标号法）1）标出各事项的最早开始时间 ，-给始点 标 ；-给任意点 标 ,Ej=Max以 为箭头的各箭之 “箭尾 +箭长tij”10jEjj2)终点 的 中的T即完工期。nT1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)9I(0)M(4)10N(7)110

26、2912172125253125382022/9/25本讲稿第四十三页，共五十页（3）求关键路（用标号法）2）计算各工序 的时差R(i,j)=的 -tij-的 。ijji1）标出各事项的最晚开始时间 ，-给终点 标 ；-给任意点 标 ,Li=Min以 为箭尾的各箭之“箭头 -箭长tij”niLiiT3）关键路径：由R(i,j)=0的关键工序组成的由 至 的路。n191C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)I(0)M(4)10N(7)11029121721252531253838253425213117129202

27、022/9/25本讲稿第四十四页，共五十页1C(1)B(3)A(10)D(2)2E(7)3F(3)4G(5)5H(4)6I(4)J(3)7I(0)8K(6)L(3)9I(0)M(4)10N(7)1102912172125253125383825342521311712920完工期T=38（天）；关键路：D-E-F-G-H-I-K-N。由本例可见：关键工序 头尾皆有 =，但反之未必。关键工序时间之和=工期T。2022/9/25本讲稿第四十五页，共五十页二、工序时间不确定的工程计划网络问题 （计划评审技术PERT）2022/9/25本讲稿第四十六页，共五十页=关键工序的平均工序时间之和；=关键工序

28、时间方差之和。2022/9/25本讲稿第四十七页，共五十页例2 某工程可分为11项工作，有关资料如下表：工作紧前工作工序时间ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.55632424333171415109794（1）画出施工网络图，确定关键路线及完工期TE；（2）估计工程在20周内完工的概率。2022/9/25本讲稿第四十八页，共五十页工作紧前工作工序时间ambABCDEFGHIJK-ABBCCG、HD、EF、I、J1111232111422210.556324243331714151097942221067434340.330.330.

29、332.672.002.001.331.331.001.3300.110.110.117.134.004.001.771.771.001.7701B(2)A(2)C(2)2D(10)E(6)35F(7)4G(4)67H(3)8I(4)J(3)9K(4)19022212561519151211117620期望工期TE=19；关键路：A-D-J-K。2022/9/25本讲稿第四十九页，共五十页0.31 0.32 0.33 0.34 0.350.6217 0.6255 0.6293 0.6331 0.6338标准正态分布数值表=0.6293工程在20周内完工的概率为0.6293。19 202022/9/25本讲稿第五十页，共五十页