例1要在这六个居民点之间设置通信线路网以保证居民点的ppt课件.ppt

图与网络优化
实验十二
通信联络网的建立
例1 要在这六个居民点之间设置通信线路网,以保证居民点的联络。每条边代表两居民点的道路,数字代表路长。问如何建立该通信网,使联网代价最小。
5
1
3
4
2
v6
v5
v4
v3
v2
v1
·
·
·
·
·
·
v6
v4
v5
v3
v2
v1
2
4
3
1
5
5
6
5
6
6
·
·
·
·
·
·
基本概念和名词
图:由若干个不同的点(顶点或节点)与其中某些顶点的连线所组成的图形
权:图中的每条边都有一个具体的数与之对应,这些数为权,带权的图为赋权图或网络。
边与弧:两点之间不带箭头的连线称为边,带箭头的连线称为弧。
无向图:一个图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的生成树。
2)按1)排列的次序检查G中的每一条边,如果这条边与已得到的边不产生圈,则取这一条边为解的一部分。
3)若已取到n-1条边,算法终止。此时以V为顶点集,以取到的n-1条边为边集的图即为最小生成树。
●
●
v5
v2
●
●
●
●
v3
v1
v4
v6
1
2
4
5
6
5
5
6
6
3
1
2
4
5
3
最短路径与Dijkstra算法
最短路径问题:在赋权有向图G中,求一条总权最小的vi至vj的路径的问题。
算法思想:若v1,v2,...,vi,...,vj,...,vn是图G从v1到vn的最短路径,则它的子路vi,...,vj一定是从vi到vj的最短路径。
算法步骤:
1)假设网络G有n个顶点,用带权的邻接矩阵W来表示,W(i,j)表示从顶点vi到vj的弧或边上的权值,不存在弧或边的权值用∞表示。