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

例要在这六个居民点之间设置通信线路网以保证居民点的-资料
例1 要在这六个居民点之间设置通信线路网，以保证居民点的联络。每条边代表两居民点的道路，数字代表路长。问如何建立该通信网，使联网代价最小。
5
1
3
4
2
例要在这六个居民点之间设置通信线路网以保证居民点的-资料
例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的生成树。
邻接矩阵：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条边为边集的图即为最小生成树。
●
●
v5
v2
●
●
●
●
v3
v1
v4
v6
1
2
4
5
6
5
5
6
6
3
1
2
4
5
3
不同使用年限设备的维修费(单位:万元)
第一年到第五年的购买价格(单位:万元)
年号
1
2
3
4
5
价格
20
20
22
22
23
使用年限
0-1
1-2
2-3
3-4
4-5
维修费
5
7
12
18
25
问：公司应在哪一年购买一台新设备，使维修费和新设备的购置费的总和最小。
解 考虑六个点v1、v2、v3、v4、v5、v6,其中vi表示在第i年初要购买新设备。v6是虚设点,表示在第5年底购买新设备。
从点vi引出指向点vi+1，vi+2，…，v6的弧,
弧(vi,vj)表示第i年年初购进的新设备要使用到第j年的年初。
弧(vi,vj)上所赋的权为第i年的购置费加上从第i年初到第j年初的维修总费用。比如W(1, 4) = 20 + (5 + 7 + 12) = 44（万元），如此计算可得到所有权值，见下图。
本问题变为在赋权图中求一条从v1到v6总权最小的路径。
例3 8个城市间有公路网,每条公路为下图中的边,边上的权数表示通过该公路所需时间。设你处在城市v1,那么从v1到其它各城市,应选择什么路径使所需的时间最少？
感谢您的关注