以保证居民点的联络每条边代表两居民点的道路数字代精品课件学案.pptx

,以保证居民点的联络。每条边代表两居民点的道路,数字代表路长。问如何建立该通信网,使联网代价最小。基本概念和名词图:由若干个不同的点(顶点或节点)与其中某些顶点的连线所组成的图形权:图中的每条边都有一个具体的数与之对应,这些数为权,带权的图为赋权图或网络。边与弧:两点之间不带箭头的连线称为边,带箭头的连线称为弧。无向图:一个图G是由顶点和边构成的。有向图:一个图G是由顶点和弧构成的。V和E分别是图的顶点的集合和边的集合,V={v1,v2,…,vn},E={e1,e2,…,em}链:在无向图中,点与边的交错序列(vi1,ei1,vi2,…,vik-1,eik-1,vik)称为连结vi1和vik的链。(eit为连结vit和vit+1的边)路径:(vi1,ai1,vi2,…,vik-1,aik-1,vik)是有向图中一条链(ait为从vit指向vit+1的弧),称之为从vi1到vik的路径。弧的集合,A={a1,a2,…,am}回路:闭合的路径称为回路。圈:闭合的链称为圈。连通图:图G中任何两个点之间至少有一条链,称G为连通图。树:一个无圈的连通图称为树生成树:若G1=(V1,E1)是连通图G2=(V2,E2)的生成子图(即V1=V2,E1E2),且G1本身是树,则称G1为G2的生成树。邻接矩阵:bij表示图G中从顶点vi到vj的弧(无向图只考虑vi与vj间的边)的数目,则矩阵B=(bij)称为图G的邻接矩阵。带权邻接矩阵:以wij表示网络G中从顶点vi到vj的弧的权(无向网只考虑vi与vj间的边的权),当vi到vj无弧或边时,wij=∞,则矩阵W=(wij)称为图G的带权邻接矩阵。算法步骤如下:1)把赋权图G中的边按权的非减次序排列。最小生成树:在赋权图G中,求一棵生成树使其总权最小,称此为图G的最小生成树。Kruskal算法思想及步骤:每次添加权尽量小的边,使新的图无圈,直到生成一棵树为止,便得最小生成树。最小生成树与Kruskal算法思想2)按1)排列的次序检查G中的每一条边,如果这条边与已得到的边不产生圈,则取这一条边为解的一部分。3)若已取到n-1条边,算法终止。此时以V为顶点集,以取到的n-1条边为边集的图即为最小生成树。Matlab程序::在赋权有向图G中,求一条总权最小的vi至vj的路径的问题。算法思想:若v1,v2,...,vi,...,vj,...,vn是图G从v1到vn的最短路径,则它的子路vi,...,vj一定是从vi到vj的最短路径。算法步骤(双标号法):1)假设网络G有n个顶点,用带权的邻接矩阵W来表示,W(i,j)表示从顶点vi到vj的弧或边上的权值,不存在弧或边的权值用∞表示。S为已求出的从始点vi出发的最短路径的终点集合,初始状态为空集。则从vi出发到图上其余各顶点vk可能达到的最短路径长度的初值为:D(k)=min{W(i,k)|vk∈V-{i}};2)选择vj,使得:D(j)=min{D(k)|vk∈V-S},vj就是当前求得的一条从始点vi出发的最短路径的终点。令S=S∪{j};