第11章 网络模型.ppt

《第11章 网络模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、系统工程第十一章网络模型8/6/2021本章学习目标1.了解图论的基础理论和计算方法2.掌握最短路、最小树和最大流算法3.了解无标度复杂网络的基本概念8/6/20212章节框架11.1图论的基本概念11.2最短路与最小生成树11.3网络流及其应用11.4复杂网络简介本章小结思考与练习题8/6/2021311.1图论的基本概念哥尼斯堡（Konigsberg）７桥问题8/6/2021411.1图论的基本概念哥尼斯堡7桥问题抽象图8/6/2021511.1图论的基本概念概念简介由点集合V和点与点之间的连线的集合E所组成

2、的集合对（V，E）称为图，用G(V，E）来表示。V中的元素称为节（结）点，E中的元素称为边。节点集V与边集合E均为有限的图称为有限图。连接同一节点的边称为自环如果图中的边是有方向的，则称为有向图。在有向图中首尾相接的一串边的集合称为路，顺向的首尾相接的一串边的集合称为有向路。8/6/2021611.1图论的基本概念如果一个图中，任意两个节点间都存在一条路与之相连，称这种图为联通图。若一个连通图中不存在任何回路，则称为树。树中任意两节点之间至多只有一条边；树中边数比节点数少１；树中任意去掉一条边，就变为不连通图；树

3、中任意添一条边，就会构成一个回路。8/6/2021711.2最短路与最小生成树11.2.1最短路及其狄克斯特拉（Dijkstra）算法11.2.2狄克斯特拉算法的一般步骤和流程图11.2.3最小生成树及其算法8/6/2021811.2.1最短路及其狄克斯特拉（Dijkstra）算法一个典型的最短路问题8/6/2021911.2.1最短路及其狄克斯特拉（Dijkstra）算法算法描述设为节点集的一个结点子集，，设为的节点余集。容易看出，若为从到的最短路，则必有，使为从到的最短路。设为从到的最短路，令为从到的最短路的

4、权数，为中任意子集，则为从到的最短路的权数，则式（11-1）为狄克斯特拉算法的理论基础。（11-1）8/6/20211011.2.2狄克斯特拉算法的一般步骤和流程图狄克斯特拉（Dijkstra）算法步骤（1）设（2）对任意（3）计算（4）在（5）（6）若设一个无向的连通图有个节点，，出发点为，令，当时中取出，使并转入（2）；若打印停机。8/6/20211111.2.2狄克斯特拉算法的一般步骤和流程图狄克斯特拉（Dijkstra）算法流程图8/6/20211211.2.3最小生成树及其算法一个连通的赋权图G，可能有

5、很多生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。G的所有生成G树中，权数最小的生成树称为G的最小生成树。树为图的最小生成树的充分必要条件是对以外的任意边，有其中为生成树的连接和的路，故图的最小生成树必然由那些权数较小的边组成，而且不会形成任何回路。8/6/20211311.2.3最小生成树及其算法克罗斯克尔(Kruskal)算法步骤设为由个节点组成的连通赋权图。中所有边按权数大小由小至大重新排列，并把权数最小的一条边取为中的边。中的边形成某个回路，则舍去该边；否则把该边也

6、取进中。条边取进其中为止，则在这条边就组成图的最小生成树。（1）先把（2）从剩下的边中按（1）中排列取下一条边，若该边与前已取进重复步骤（2），直至有8/6/20211411.2.3最小生成树及其算法普莱姆(Prime)算法步骤普莱姆算法的基本思想为：中任取一个节点，并取入中；，其中分别为图与树的节点集；的节点与的节点的边中，选出权数最小的边，即（4）将边取入中。（1）先在（2）令（3）在所有连接8/6/20211511.3网络流及其应用11.3.1网络流与最大流最小割定理11.3.2最大流的算法11.3.3网络

7、流的应用8/6/20211611.3.1网络流与最大流最小割定理流性质实际流动量是一个有向的流动；每个管道中单位时间内通过的流量不可能超过该管道的容量（权数）；每个内部节点处流向节点与流出节点的流量应相等；流入进水口的流量应等于流出出水口的流量，即为实际流动的流量。8/6/20211711.3.1网络流与最大流最小割定理流的定义条件（1）表示从到的正流等于从到设在有向赋权图的上定义一个整数值函数（其中为中的有向边），使其满足条件（2）（3），当时，其中为与节点连接的（4）则称为上的一个流。（1）节点集合；8/6/

8、20211811.3.2最大流的算法设给定一个有向赋权图，从任一可行流出发，例如从零流出发。令为由发点和对于若收点则为最大流；若收点则因故存在从到的非饱和路，在上的每边，均有，的非饱和点组成的节点子集。不是最大流，从而可由下列方法加以改进。令并令容易验证，也为可行流，且它的流值为，在以为基础，重复上面的步骤，必可经过有限步后得到一个最大流。这个算法称为非饱和算法。8/6/