第三章图与网络技术优秀PPT.ppt
《第三章图与网络技术优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第三章图与网络技术优秀PPT.ppt(50页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第三章 图与网络技术2023/2/25现在学习的是第1页,共50页图的概念图的概念所谓图,就是顶点和边的集合,点的集合记为所谓图,就是顶点和边的集合,点的集合记为V,边,边的集合记为的集合记为E,则图可以表示为:,则图可以表示为:G(V,E),),点代表被研究的事物,边代表事物之间的联系,点代表被研究的事物,边代表事物之间的联系,因此,边不能离开点而独立存在,每条边都有两因此,边不能离开点而独立存在,每条边都有两个端点。个端点。在画图时,顶点的位置、边和长短形状都是无关紧在画图时,顶点的位置、边和长短形状都是无关紧要的,只要两个图的顶点及边是对应相同的,则两要的,只要两个图的顶点及边是对应相同
2、的,则两个图相同。个图相同。第一节 图的基本概念2023/2/25现在学习的是第2页,共50页1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1:如 G:简单图:无环、无多重边的图。2023/2/25现在学习的是第3页,共50页2.关联与相邻3.链与圈2023/2/25现在学习的是第4页,共50页4.有向图与无向图,圈,回路比较:2023/2/25现在学习的是第5页,共50页一个没有圈的图称为一个无圈图或称为林。一个没有圈的图称为一个无圈图或称为林。一一个个连连通通的的无无圈圈图图则则称称为为树树,一一个个林林的的每每个个连连通通子子图图都都是是一
3、个树。一个树。定理定理以下关于树的六种不同描述是等价的:以下关于树的六种不同描述是等价的:无圈连通图。无圈连通图。无圈,无圈,q=p-1。连通,连通,q=p-1。无圈,但若任意增加一条边,则可得到一个且仅一个圈。无圈,但若任意增加一条边,则可得到一个且仅一个圈。连通,但若任意舍弃一条边,图便不连通。连通,但若任意舍弃一条边,图便不连通。每一对顶点之间有一条且仅有一条链。每一对顶点之间有一条且仅有一条链。5.树2023/2/25现在学习的是第6页,共50页6.图的部分(支撑)树 若图G=(V,E)的子图T=(V,E)是树,则称T为G的部分树或支撑树。特点边少、点不少。性质:G连通,则G必有部分树
4、。证:破圈、保连通。2023/2/25现在学习的是第7页,共50页第二节 网络分析网络赋权图,记D=(V,E,C),其中C=c1,cn,ci为边ei上的权(设ci )。网络分析主要内容最小部分树、最短路、最大流。图只能用来研究事物之间有没有某种关系,而图只能用来研究事物之间有没有某种关系,而不能研究这种关系的强弱程度。不能研究这种关系的强弱程度。2023/2/25现在学习的是第8页,共50页一.最小部分(支撑)树问题问题:求网络D的部分树,使其权和最小。方法:避圈法(Kruskal,1956)、破圈法(管梅谷,1975)。例 2 求如图网络的最小部分树。v5v1v3v6v4v2v7255233
5、5757112023/2/25现在学习的是第9页,共50页避圈法是一种选边的过程,其步骤如下:1.从网络D中任选一点vi,找出与vi相关联的 权最小的边vi,vj,得第二个顶点vj;2.把顶点集V分为互补的两部分V1,1,其中2023/2/25现在学习的是第10页,共50页用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分树如图上红线所示;最小权和为14。思考:破圈法是怎样做的呢?见圈就破,去掉其中权最大的。2023/2/25现在学习的是第11页,共50页二.最短路问题1.问题:求网络D中一定点v1到其它点的最短路。例3 求如图网络中v1至v7的最短路,图中数字为两点间
6、距离。v5v1v3v6v4v2v72552335757112.方法:标号法(Dijkstra,1959)给每点vj标号dj,vi,其中dj为v1至vj的最短距,vi为最短路上的前一点。2023/2/25现在学习的是第12页,共50页标号法步骤:2023/2/25现在学习的是第13页,共50页用标号法解例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。2023/2/25现在学习的是第14页,共50
7、页最短路问题的应用例子 某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元):年号 1 2 3 4 5 价格22.12.32.42.6 汽车使用年龄0112233445维修费用0.71.11.522.5试用网络分析中求最短路的方法确定公司可采用的最优策略。方法:以年号作顶点绘图,连线表示连续使用期间,以 费用作路长。2023/2/25现在学习的是第15页,共50页所所谓谓最最大大流流问问题题就就是是在在一一定定的的条条件件下下,要要求求流流过过网网络络的的物物流流、能能量量流流或或信信息息流流等等流流量量为为最最大大的的问问题题,在在最最大大流流问
8、题中一般有如下规定:问题中一般有如下规定:网络有一个起点网络有一个起点s和一个终点和一个终点t网络是有向网络,即流有方向性。网络是有向网络,即流有方向性。在在网网络络各各条条弧弧上上都都有有一一个个权权,表表示示允允许许流流过过的的最最大大流流量量。若若以以cij表表示示由由i到到j的的弧弧上上允允许许流流过过的的最最大大流流量量,以以xij表表示示实实际流过该弧的流量,则际流过该弧的流量,则0 xijcij网网络络中中,除除起起点点s和和终终点点t之之外外的的任任何何顶顶点点,流流入入量量总总和和应应该该等于流出量的总和。等于流出量的总和。三.最大流问题2023/2/25现在学习的是第16页
9、,共50页最大流问题的数学模型最大流问题的数学模型最大流最大流问题的问题的数学模型:数学模型:vs101165473915vtv5v3v4v22023/2/25现在学习的是第17页,共50页最大流最小割集定理最大流最小割集定理1网网络络中中的的最最大大流流量量fmax值值大大小小是是由由网网络络中中最最狭狭窄窄处瓶颈的容量所决定的。处瓶颈的容量所决定的。最最大大流流最最小小割割集集定定理理揭揭示示了了最最小小割割集集(网网络络中中的的瓶瓶颈颈)容容量量与最大流量的关系,也提供了一个求最大流的方法。与最大流量的关系,也提供了一个求最大流的方法。割集割集网络割集容量网络割集容量最小割集最小割集所有
10、割集中容量最小的一个割集。所有割集中容量最小的一个割集。2023/2/25现在学习的是第18页,共50页最大流最小割集定理最大流最小割集定理2网网络络中中的的最最大大流流量量fmax值值大大小小是是由由网网络络中中最最狭窄处瓶颈的容量所决定的。狭窄处瓶颈的容量所决定的。网络割集容量网络割集容量最小割集最小割集所有割集中容量最小的一个割集。所有割集中容量最小的一个割集。最大流最小割集定理最大流最小割集定理流过网络的最大流量等于最小割集的容量。流过网络的最大流量等于最小割集的容量。2023/2/25现在学习的是第19页,共50页最大流最小割集定理最大流最小割集定理3vs101165473915vt
11、v5v3v4v2SS割集割集容量容量vsv2v3v4v5vt(vsv2)(vsv3)24vsv2v3v4v5vt(vsv3)(v2v4)(v2v5)20vsv3v2v4v5vt(vsv2)(v3v2)(v3v4)(v3v5)29.2023/2/25现在学习的是第20页,共50页福德富克逊方法原理福德富克逊方法原理算法的原理算法的原理首首先先,依依据据最最大大流流问问题题的的要要求求,为为网网络络分分配配一一个个可可行行流流。所所谓谓可可行行流流,是是指指所所有有弧弧上上流流量量满满足足容容量限制,所有中间点满足平衡条件的流;量限制,所有中间点满足平衡条件的流;若若这这一一可可行行流流的的流流量
12、量就就是是最最大大流流量量,则则问问题题已已经经解决;解决;若若不不是是最最大大流流量量,则则增增加加流流量量获获得得流流量量更更大大的的可行流。可行流。2023/2/25现在学习的是第21页,共50页福德富克逊方法流图福德富克逊方法流图求一个初始可行流求一个初始可行流是是判断初始可行流是否最优判断初始可行流是否最优结结束束不是不是求使目标得到改善的可行流求使目标得到改善的可行流2023/2/25现在学习的是第22页,共50页福德富克逊方法图示福德富克逊方法图示算法原理图示算法原理图示初始流初始流初始流初始流2023/2/25现在学习的是第23页,共50页福德富克逊方法讨论福德富克逊方法讨论若
13、若弧弧(vi,vj)上上的的流流量量满满足足xij=cij,则则称称该该弧弧为为饱饱和和弧弧,否否则则称称为非饱和弧。为非饱和弧。若若弧弧(vi,vj)上上的的流流量量xij=0。则则称称该该弧弧为为零零流流弧弧,否否则则称称为为非零流弧。非零流弧。一一条条从从s到到t的的初初等等链链是是由由s开开始始的的点点、边边序序列列,其其中中没没有相同的点,也不考虑弧的方向。有相同的点,也不考虑弧的方向。把这条链中的把这条链中的s到到t方向相同的弧称为正向弧。方向相同的弧称为正向弧。把这条链中的把这条链中的s到到t方向相反的弧称为逆向弧。方向相反的弧称为逆向弧。在上述的可行流中,从在上述的可行流中,从
14、s到到t的某个初等链满足:的某个初等链满足:其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。则称该链为一条则称该链为一条流量增广链流量增广链。2023/2/25现在学习的是第24页,共50页福德富克逊方法讨论福德富克逊方法讨论流量增广链流量增广链:从从s到到t的某个初等链满足的某个初等链满足其上的正向弧均为非饱和弧。其上的正向弧均为非饱和弧。其上的逆向弧均为非零流弧。其上的逆向弧均为非零流弧。结结论论:若若在在可可行行流流中中,存存在在从从s到到t的的增增广广链链,则则该该可可行行流流不不是是最最大大流流,其其流流量量可可以以增增加加;否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第三章 图与网络技术优秀PPT 第三 网络技术 优秀 PPT
限制150内