数学建模 图论模型 图论
21页1、图论算法1 最小生成树 11 生成树的概念 设图G(V,E)是一个连通图,当从图中任一顶点出发遍历图G时,将边集E(G)分成两个集合A(G)和B(G)。其中A(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合。显然,G1(V,A)是图G的子图,则称子图G1是连通图G的生成树。图的生成树不是惟一的。如对图1(a),当按深度和广度优先搜索法进行遍历就可以得到图1中(b)和(c)的两棵不同的生成树,并分别称之为深度优先生成树和广度优先生成树。 对于有n个顶点的连通图,至少有n-1条边,而生成树中恰好有n-1条边,所以连通图的生成树是该图的极小连通子图。若图G的生成树中任意加一条边属于边集B(G)中的边,则必然形成回路。 求解生成树在许多领域有实际意义。例如,对于供电线路或煤气管道的铺设问题,即假设要把n个城市联成一个供电或煤气管道网络,则需要铺设n1条线路。任意两城市间可铺设一条线路,n个城市间最多可能铺设n(n1)/2条线路,各条线路的造价一般是不同的。一个很实际的问题就是如何在这些可能的线路中选择n-1条使该网络的建造费用最少,这就是下面要讨论的最小生成树问题。 1.2
2、 网的最小生成树 在前面我们已经给出图的生成树的概念。这里来讨论生成树的应用。 假设,要在n个居民点之间敷设煤气管道。由于,在每一个居民点与其余n1个居民点之间都可能敷设煤气管道。因此,在n个居民点之间,最多可能敷设n(n-1)/2条煤气管道。然而,连通n个居民点之间的管道网络,最少需要n-1条管道。也就是说,只需要n-1条管道线路就可以把n个居民点间的煤气管道连通。另外,还需进一步考虑敷设每一条管道要付出的经济代价。这就提出了一个优选问题。即如何在n(n-1)/2条可能的线路中优选n-1条线路,构成一个煤气管道网络,从而既能连通n个居民点,又能使总的花费代价最小。 解决上述问题的数学模型就是求图中网的最小生成树问题。把居民点看作图的顶点,把居民点之间的煤气管道看作边,而把敷设各条线路的代价当作权赋给相应的边。这样,便构成一个带权的图,即网。对于一个有n个顶点的网可以生成许多互不相同的生成树,每一棵生成树都是一个可行的敷设方案。现在的问题是应寻求一棵所有边的权总和为最小的生成树。 如何构造这种网的最小生成树呢?下面给出这样一种解法: (1)已知一个网,将网中的边按其权值由小到大的次序顺
3、序选取。 (2)若选某边后不形成回路,则将其保留作为树的一条边;若选某边后形成回路,则将其舍弃,以后也不再考虑。 (3)如此依次进行,直到选够(n-1)条边即得到最小生成树。 现以图2为例说明此算法。设此图是用边集数组EV表示的,且数组中各边是按权值由小到大的次序排列,如下表所示。 k12345678910EVk.p12242651115EVk.p23436475626COSTEVk.p1,EVk.p2561011141819212733 按权值由小到大选取各边就是在数组中按下标k由1到en(图中边数)的次序选取。选前2条边(2,3),(2,4)时均无问题,保留作为树的边;到第3条边(4,3)时将与已保留的边形成回路,将其舍去;同样继续做:保留(2, 6);舍去(6,4);保留(5,7),(1,5),(1,6),此时,保留的边数已够(n-1)=6条边,此时必定将7个顶点全部互相连通了,后面剩下的边(1,2),(5,6)就不必再考虑了。最后得到的最小生成树如图2a中深色边所示,其各边权值总和等于80。由离散数学中的图论可以证明,这就是最小生成树了,其权值最小。当图中有权值相等的边时,其最
《数学建模 图论模型 图论》由会员suns****4568分享,可在线阅读,更多相关《数学建模 图论模型 图论》请在金锄头文库上搜索。
土地管理与地籍测量---第八章界址点测量
人机工程学案例分析(2)
工程安全培训_201303
第9章房地产投资决策分析
第2章房地产经纪制度
ACM程序设计-东北林业大学acm05
《亲爱的汉修先生》读书交流会
中原_深圳新世界尖岗山项目市场汇报_40P_2012年_别墅_项目分析_量价走势
五年级数学质量分析演示文稿
人工智能小镇-智慧小镇建设20180525
景观基本知识及发展历程
建设工程信息管理(2)
机电驱动技术第二章步进驱动技术
工程力学-第9章圆轴扭转时的应力变形分析与强度刚度设计
第一章第二节幼儿园文化环境建设的原则
第一章检测技术的基础知识
第一章__现代表面工程技术
第六章钢结构工程
第9节项目试运行管理
班主任工作经验交流课件(4)
2023-06-29 14页
2023-03-21 13页
2023-07-29 16页
2023-05-15 18页
2023-03-01 5页
2023-03-07 13页
2023-02-18 6页
2023-08-28 4页
2024-02-04 14页
2023-07-28 14页