第11章网络模型精.ppt

第第11章网络模型章网络模型19 February 2023PPT 1第1页，本讲稿共30页19 February 2023PPT 2本章学习目标本章学习目标1.了解图论的基础理论和计算方法 2.掌握最短路、最小树和最大流算法 3.了解无标度复杂网络的基本概念第2页，本讲稿共30页19 February 2023PPT 3章节框架章节框架a 11.1 图论的基本概念a 11.2 最短路与最小生成树a 11.3 网络流及其应用a 11.4 复杂网络简介a 本章小结 a 思考与练习题第3页，本讲稿共30页19 February 2023PPT 411.1图论的基本概念图论的基本概念a哥尼斯堡（Konigsberg）桥问题第4页，本讲稿共30页19 February 2023PPT 511.1图论的基本概念图论的基本概念a哥尼斯堡7桥问题抽象图 第5页，本讲稿共30页19 February 2023PPT 611.1图论的基本概念图论的基本概念a概念简介 由点集合V和点与点之间的连线的集合E所组成的集合对（V，E）称为图，用G(V，E）来表示。V中的元素称为节（结）点，E中的元素称为边。节点集V与边集合E均为有限的图称为有限图。连接同一节点的边称为自环 如果图中的边是有方向的，则称为有向图。在有向图中首尾相接的一串边的集合称为路，顺向的首尾相接的一串边的集合称为有向路。第6页，本讲稿共30页19 February 2023PPT 711.1图论的基本概念图论的基本概念 如果一个图中，任意两个节点间都存在一条路与之相连，称这种图为联通图。若一个连通图中不存在任何回路，则称为树。树中任意两节点之间至多只有一条边；树中边数比节点数少；树中任意去掉一条边，就变为不连通图；树中任意添一条边，就会构成一个回路。第7页，本讲稿共30页19 February 2023PPT 811.2最短路与最小生成树最短路与最小生成树a 11.2.1 最短路及其狄克斯特拉（Dijkstra）算法a 11.2.2 狄克斯特拉算法的一般步骤和流程图a 11.2.3 最小生成树及其算法第8页，本讲稿共30页19 February 2023PPT 911.2.1 最短路及其狄克斯特拉（最短路及其狄克斯特拉（Dijkstra）算法）算法a一个典型的最短路问题第9页，本讲稿共30页19 February 2023PPT 1011.2.1 最短路及其狄克斯特拉（最短路及其狄克斯特拉（Dijkstra）算法）算法a算法描述设为节点集的一个结点子集，设为的节点余集。容易看出，若为从到的最短路，则必有，使为从到的最短路。设为从到的最短路，令为从到的最短路的权数，为中任意子集，则为从到的最短路的权数，则式（11-1）为狄克斯特拉算法的理论基础。（11-1）第10页，本讲稿共30页19 February 2023PPT 1111.2.2 狄克斯特拉算法的一般步骤和流程图狄克斯特拉算法的一般步骤和流程图a狄克斯特拉（Dijkstra）算法步骤（1）设（2）对任意（3）计算（4）在（5）（6）若设一个无向的连通图有个节点，出发点为，令 ，当时中取出，使并转入（2）；若打印停机。第11页，本讲稿共30页19 February 2023PPT 1211.2.2 狄克斯特拉算法的一般步骤和流程图狄克斯特拉算法的一般步骤和流程图a狄克斯特拉（Dijkstra）算法流程图第12页，本讲稿共30页19 February 2023PPT 1311.2.3最小生成树及其算法 一个连通的赋权图G，可能有很多生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。G的所有生成G树中，权数最小的生成树称为G的最小生成树。树 为图 的最小生成树的充分必要条件是 对以外的任意边 ，有 其中 为生成树 的连接 和 的路，故图 的最小生成树 必然由那些权数较小的边组成，而且不会形成任何回路。第13页，本讲稿共30页19 February 2023PPT 1411.2.3最小生成树及其算法a克罗斯克尔(Kruskal)算法步骤设为由个节点组成的连通赋权图。中所有边按权数大小由小至大重新排列，并把权数最小的一条边取为中的边。中的边形成某个回路，则舍去该边；否则把该边也取进 中。条边取进其中为止，则在这条边就组成图的最小生成树。（1）先把（2）从剩下的边中按（1）中排列取下一条边，若该边与前已取进重复步骤（2），直至有第14页，本讲稿共30页19 February 2023PPT 1511.2.3最小生成树及其算法a普莱姆(Prime)算法步骤普莱姆算法的基本思想为：中任取一个节点，并取入中；，其中分别为图与树的节点集；的节点与的节点的边中，选出权数最小的边，即 （4）将边取入中。（1）先在（2）令（3）在所有连接第15页，本讲稿共30页19 February 2023PPT 1611.3网络流及其应用网络流及其应用a11.3.1网络流与最大流最小割定理a11.3.2最大流的算法a11.3.3网络流的应用第16页，本讲稿共30页19 February 2023PPT 1711.3.1网络流与最大流最小割定理网络流与最大流最小割定理a流性质 实际流动量是一个有向的流动；每个管道中单位时间内通过的流量不可能超过该管道的容量（权数）；每个内部节点处流向节点与流出节点的流量应相等；流入进水口的流量应等于流出出水口的流量，即为实际流动的流量。第17页，本讲稿共30页19 February 2023PPT 1811.3.1网络流与最大流最小割定理网络流与最大流最小割定理a流的定义条件（1）表示从到的正流等于从到设在有向赋权图的上定义一个整数值函数（其中为中的有向边），使其满足条件（2）（3），当时，其中为与节点连接的（4）则称为上的一个流。（1）节点集合；第18页，本讲稿共30页19 February 2023PPT 1911.3.2 最大流的算法最大流的算法设给定一个有向赋权图，从任一可行流出发，例如从零流出发。令为由发点和对于若收点则为最大流；若收点则因故存在从到的非饱和路，在上的每边，均有，的非饱和点组成的节点子集。不是最大流，从而可由下列方法加以改进。令并令容易验证，也为可行流，且它的流值为，在以 为基础，重复上面的步骤，必可经过有限步后得到一个最大流。这个算法称为非饱和算法。第19页，本讲稿共30页19 February 2023PPT 2011.3.3网络流的应用网络流的应用 .最小费用最大流问题 在实际问题中，人们不仅考虑流量的大小，还要考虑输送这些流量所需的费用、代价等。例如某工厂要把产品运往销售点，在选择运输路线时，不仅要考虑运输量，而且还要考虑运输最大运输量的最小费用问题，这是典型的最小费用最大流问题之一。.运输问题第20页，本讲稿共30页19 February 2023PPT 2111.4 复杂网络简介复杂网络简介a11.4.1实际网络的拓扑结构a11.4.2 规则图与经典随机网络a11.4.3 复杂现象的共同特性a11.4.4 无标度网络模型a11.4.5 无标度网络的稳健性和脆弱性a11.4.6 无标度模型扩展研究第21页，本讲稿共30页19 February 2023PPT 2211.4.1 实际网络的拓扑结构实际网络的拓扑结构a信息交换网万维网、国际互联网、电话网、电力网a社会网络电影演员合作网、科研合作图、引文网、人类性接触网、语言学网a生物网络细胞网络、生态网络、蛋白质折叠第22页，本讲稿共30页19 February 2023PPT 2311.4.2 规则图与经典随机网络规则图与经典随机网络a经典随机网络ER模型 1960年匈牙利数学家Paul Erds和Alfred Rnyi提出了随机网络模型（ER模型）。这个有影响的模型由n个节点构成，每个节点以概率p通过一条边连接到另一节点上。该随机网络节点具有k条边（或度为k）的概率服从泊松分布，网络中大多数节点具有大约相同的连接边数，节点平均度为。第23页，本讲稿共30页19 February 2023PPT 2411.4.3 复杂现象的共同特性复杂现象的共同特性 系统结构出现幂律分布已成为许多复杂系统的共性，在许多复杂系统背后，都存在着一个构成网络基础的非均匀拓扑结构，目前的研究只是个开端，还有大量的现实系统值得我们去进行实证性研究。产生这种幂律分布的机理是什么？需要根据对实际网络的观察分析，建立模型进行理论研究。第24页，本讲稿共30页19 February 2023PPT 2511.4.4 无标度网络模型无标度网络模型aBA模型的算法如下（1）增长。开始于较少的节点数量，在每个时间间隔增添一个具有（）条边的新节点，连接这个新节点到个已经存在于系统中的节点上。（2）择优连接。在选择新节点的连接点时，假设新节点连接到节点的概率取决于节点 的度数。即 第25页，本讲稿共30页19 February 2023PPT 2611.4.5 无标度网络的稳健性和脆弱性无标度网络的稳健性和脆弱性a无标度网络特性a增长性a择优性a稳健性a脆弱性a小世界特性a较大的群聚系数a较小的平均路径长度第26页，本讲稿共30页19 February 2023PPT 2711.4.6 无标度模型扩展研究无标度模型扩展研究a增长机制的改变研究a择优连接的更迭机理研究a层次网络研究第27页，本讲稿共30页19 February 2023PPT 28本章小结本章小结 本章阐述了网络图的基本概念，介绍了网络系统中的最短路问题、最生成小树问题和最大流问题。针对最短路问题介绍了狄克斯特拉算法。针对最小生成树问题介绍了克罗斯克尔(Kruskal)求解算法和普莱姆(Prime)算法。对于最大流问题介绍了最大流最小割定理，并用算例进行了演示求解。另外还对对近年来快速发展的有关复杂网络的研究进展作了简要回顾。通过本章学习，要求了解图论的基础理论和计算方法，掌握最短路、最小树和最大流算法，学会应用这些算法解决实际系统中的相关问题。同时，对无标度复杂网络的一些基本概念有所了解。第28页，本讲稿共30页19 February 2023PPT 29思考与练习题思考与练习题1.现实世界中哪些问题可以用图来描述？试举几个例子说明。2.狄克斯特拉最短路算法思想是什么？3.试用学过的计算机知识编制算法程序，求解最短路问题。4.你所了解的最小生成树算法有几种？试编制计算机程序求解最小生成树问题。5.最大流算法的中心思想是什么？6.流增值的限制条件是什么？7.那些问题可转换为求最小费用最大流问题？8.你能举例说明现实世界中的哪些系统可构成随机网络？9.小世界网络的特征是什么？无标度网络的特征是什么？10.那些指标可用来描述随机网络的性质？第29页，本讲稿共30页19 February 2023PPT 30Thank youThank you！第30页，本讲稿共30页