第11章网络模型.pptVIP

第11章网络模型*PPT*第1页，共30页，星期日，2025年，2月5日*PPT*本章学习目标1.了解图论的基础理论和计算方法2.掌握最短路、最小树和最大流算法3.了解无标度复杂网络的基本概念第2页，共30页，星期日，2025年，2月5日*PPT*章节框架11.1图论的基本概念11.2最短路与最小生成树11.3网络流及其应用11.4复杂网络简介本章小结思考与练习题第3页，共30页，星期日，2025年，2月5日*PPT*11.1图论的基本概念哥尼斯堡（Konigsberg）７桥问题第4页，共30页，星期日，2025年，2月5日*PPT*11.1图论的基本概念哥尼斯堡7桥问题抽象图第5页，共30页，星期日，2025年，2月5日*PPT*11.1图论的基本概念概念简介由点集合V和点与点之间的连线的集合E所组成的集合对（V，E）称为图，用G(V，E）来表示。V中的元素称为节（结）点，E中的元素称为边。节点集V与边集合E均为有限的图称为有限图。连接同一节点的边称为自环如果图中的边是有方向的，则称为有向图。在有向图中首尾相接的一串边的集合称为路，顺向的首尾相接的一串边的集合称为有向路。第6页，共30页，星期日，2025年，2月5日*PPT*11.1图论的基本概念如果一个图中，任意两个节点间都存在一条路与之相连，称这种图为联通图。若一个连通图中不存在任何回路，则称为树。树中任意两节点之间至多只有一条边；树中边数比节点数少１；树中任意去掉一条边，就变为不连通图；树中任意添一条边，就会构成一个回路。第7页，共30页，星期日，2025年，2月5日*PPT*11.2最短路与最小生成树11.2.1最短路及其狄克斯特拉（Dijkstra）算法11.2.2狄克斯特拉算法的一般步骤和流程图11.2.3最小生成树及其算法第8页，共30页，星期日，2025年，2月5日*PPT*11.2.1最短路及其狄克斯特拉（Dijkstra）算法一个典型的最短路问题第9页，共30页，星期日，2025年，2月5日*PPT*11.2.1最短路及其狄克斯特拉（Dijkstra）算法算法描述设为节点集的一个结点子集，，设为的节点余集。容易看出，若为从到的最短路，则必有，使为从到的最短路。设为从到的最短路，令为从到的最短路的权数，为中任意子集，则为从到的最短路的权数，则式（11-1）为狄克斯特拉算法的理论基础。（11-1）第10页，共30页，星期日，2025年，2月5日*PPT*11.2.2狄克斯特拉算法的一般步骤和流程图狄克斯特拉（Dijkstra）算法步骤（1）设（2）对任意（3）计算（4）在（5）（6）若设一个无向的连通图有个节点，，出发点为，令，当时中取出，使并转入（2）；若打印停机。第11页，共30页，星期日，2025年，2月5日*PPT*11.2.2狄克斯特拉算法的一般步骤和流程图狄克斯特拉（Dijkstra）算法流程图第12页，共30页，星期日，2025年，2月5日*PPT*11.2.3最小生成树及其算法一个连通的赋权图G，可能有很多生成树。设T为图G的一个生成树，若把T中各边的权数相加，则这个和数称为生成树T的权数。G的所有生成G树中，权数最小的生成树称为G的最小生成树。树为图的最小生成树的充分必要条件是对以外的任意边，有其中为生成树的连接和的路，故图的最小生成树必然由那些权数较小的边组成，而且不会形成任何回路。第13页，共30页，星期日，2025年，2月5日*PPT*11.2.3最小生成树及其算法克罗斯克尔(Kruskal)算法步骤设为由个节点组成的连通赋权图。中所有边按权数大小由小至大重新排列，并把权数最小的一条边取为中