第11章 网络模型.ppt

February5 2020 PPT1 系统工程第十一章网络模型 February5 2020 PPT2 本章学习目标 1 了解图论的基础理论和计算方法2 掌握最短路 最小树和最大流算法3 了解无标度复杂网络的基本概念 February5 2020 PPT3 章节框架 11 1图论的基本概念11 2最短路与最小生成树11 3网络流及其应用11 4复杂网络简介本章小结思考与练习题 February5 2020 PPT4 11 1图论的基本概念 哥尼斯堡 Konigsberg 桥问题 February5 2020 PPT5 11 1图论的基本概念 哥尼斯堡7桥问题抽象图 February5 2020 PPT6 11 1图论的基本概念 概念简介由点集合V和点与点之间的连线的集合E所组成的集合对 V E 称为图 用G V E 来表示 V中的元素称为节 结 点 E中的元素称为边 节点集V与边集合E均为有限的图称为有限图 连接同一节点的边称为自环如果图中的边是有方向的 则称为有向图 在有向图中首尾相接的一串边的集合称为路 顺向的首尾相接的一串边的集合称为有向路 February5 2020 PPT7 11 1图论的基本概念 如果一个图中 任意两个节点间都存在一条路与之相连 称这种图为联通图 若一个连通图中不存在任何回路 则称为树 树中任意两节点之间至多只有一条边 树中边数比节点数少 树中任意去掉一条边 就变为不连通图 树中任意添一条边 就会构成一个回路 February5 2020 PPT8 11 2最短路与最小生成树 11 2 1最短路及其狄克斯特拉 Dijkstra 算法11 2 2狄克斯特拉算法的一般步骤和流程图11 2 3最小生成树及其算法 February5 2020 PPT9 11 2 1最短路及其狄克斯特拉 Dijkstra 算法 一个典型的最短路问题 February5 2020 PPT10 11 2 1最短路及其狄克斯特拉 Dijkstra 算法 算法描述 February5 2020 PPT11 11 2 2狄克斯特拉算法的一般步骤和流程图 狄克斯特拉 Dijkstra 算法步骤 1 设 2 对任意 3 计算 4 在 5 6 若 February5 2020 PPT12 11 2 2狄克斯特拉算法的一般步骤和流程图 狄克斯特拉 Dijkstra 算法流程图 February5 2020 PPT13 11 2 3最小生成树及其算法 一个连通的赋权图G 可能有很多生成树 设T为图G的一个生成树 若把T中各边的权数相加 则这个和数称为生成树T的权数 G的所有生成G树中 权数最小的生成树称为G的最小生成树 树为图的最小生成树的充分必要条件是对以外的任意边 有其中为生成树的连接和的路 故图的最小生成树必然由那些权数较小的边组成 而且不会形成任何回路 February5 2020 PPT14 11 2 3最小生成树及其算法 克罗斯克尔 Kruskal 算法步骤 February5 2020 PPT15 11 2 3最小生成树及其算法 普莱姆 Prime 算法步骤 February5 2020 PPT16 11 3网络流及其应用 11 3 1网络流与最大流最小割定理11 3 2最大流的算法11 3 3网络流的应用 February5 2020 PPT17 11 3 1网络流与最大流最小割定理 流性质实际流动量是一个有向的流动 每个管道中单位时间内通过的流量不可能超过该管道的容量 权数 每个内部节点处流向节点与流出节点的流量应相等 流入进水口的流量应等于流出出水口的流量 即为实际流动的流量 February5 2020 PPT18 11 3 1网络流与最大流最小割定理 流的定义 条件 1 表示从 到 的正流等于从 到 February5 2020 PPT19 11 3 2最大流的算法 February5 2020 PPT20 11 3 3网络流的应用 最小费用最大流问题在实际问题中 人们不仅考虑流量的大小 还要考虑输送这些流量所需的费用 代价等 例如某工厂要把产品运往销售点 在选择运输路线时 不仅要考虑运输量 而且还要考虑运输最大运输量的最小费用问题 这是典型的最小费用最大流问题之一 运输问题 February5 2020 PPT21 11 4复杂网络简介 11 4 1实际网络的拓扑结构11 4 2规则图与经典随机网络11 4 3复杂现象的共同特性11 4 4无标度网络模型11 4 5无标度网络的稳健性和脆弱性11 4 6无标度模型扩展研究 February5 2020 PPT22 11 4 1实际网络的拓扑结构 信息交换网万维网 国际互联网 电话网 电力网社会网络电影演员合作网 科研合作图 引文网 人类性接触网 语言学网生物网络细胞网络 生态网络 蛋白质折叠 February5 2020 PPT23 11 4 2规则图与经典随机网络 经典随机网络 ER模型1960年匈牙利数学家PaulErd s和AlfredR nyi提出了随机网络模型 ER模型 这个有影响的模型由n个节点构成 每个节点以概率p通过一条边连接到另一节点上 该随机网络节点具有k条边 或度为k 的概率服从泊松分布 网络中大多数节点具有大约相同的连接边数 节点平均度为 February5 2020 PPT24 11 4 3复杂现象的共同特性 系统结构出现幂律分布已成为许多复杂系统的共性 在许多复杂系统背后 都存在着一个构成网络基础的非均匀拓扑结构 目前的研究只是个开端 还有大量的现实系统值得我们去进行实证性研究 产生这种幂律分布的机理是什么 需要根据对实际网络的观察分析 建立模型进行理论研究 February5 2020 PPT25 11 4 4无标度网络模型 BA模型的算法如下 February5 2020 PPT26 11 4 5无标度网络的稳健性和脆弱性 无标度网络特性增长性择优性稳健性脆弱性小世界特性较大的群聚系数较小的平均路径长度 February5 2020 PPT27 11 4 6无标度模型扩展研究 增长机制的改变研究择优连接的更迭机理研究层次网络研究 February5 2020 PPT28 本章小结 本章阐述了网络图的基本概念 介绍了网络系统中的最短路问题 最生成小树问题和最大流问题 针对最短路问题介绍了狄克斯特拉算法 针对最小生成树问题介绍了克罗斯克尔 Kruskal 求解算法和普莱姆 Prime 算法 对于最大流问题介绍了最大流最小割定理 并用算例进行了演示求解 另外还对对近年来快速发展的有关复杂网络的研究进展作了简要回顾 通过本章学习 要求了解图论的基础理论和计算方法 掌握最短路 最小树和最大流算法 学会应用这些算法解决实际系统中的相关问题 同时 对无标度复杂网络的一些基本概念有所了解 February5 2020 PPT29 思考与练习题 现实世界中哪些问题可以用图来描述 试举几个例子说明 狄克斯特拉最短路算法思想是什么 试用学过的计算机知识编制算法程序 求解最短路问题 你所了解的最小生成树算法有几种 试编