2.3  树的定义及其性质

连通图G的不包含任何回路的最大子图T叫做图G的树,如图4所示.若树T就是G图本身,则G图就是一棵树.属于树T的边叫做“树枝”,不属于树T的边叫做“弦”.树T中线度为1的顶点成为树叶.

树的性质:

 (1)一棵树每两点之间都是有且只有一条路径.一棵有N个点的树就会有N-1条边,即为连接N个点所需要的最少边数.所以若删除树中的任意一条边,树就会不连通.

   (2)在一棵树中加入任意一条边,就会形成有且仅有一个环的图.这是因为这条边连接的两个点中有且仅有一条边,这条边和新加进去的边连接在一起就会成为一个环.如果把一个连通图中的多余边全部删除,那么所构成的树就叫做这个图的生成树.

   (3)若需在树中加入一个点,则就要加入一条将这个点和原有的点相连接的边.这条边不会使这棵树形成一个环或多余的路.所以按上述方法每次加进一个点,就能构成一棵树.

   (4)一棵树既可以是有向的也可以是无向的.

3  典型图论问题的解法

3.1  最短路径问题

最短路径问题是图论研究的一个经典问题,旨在寻找图中两结点之间的最短路径.主要特点是以起始点为中心向外层层展开,直到展开到终点为止.

下面介绍一种求最短路的常见算法,Dijkstra算法[1].设P(u,v)是加权图G中从u到v的路径,该路径上的权值之和称为该路径的权,记为W(P).从u到v的路径中权最小者称为u到v的最短路径.Dijkstra算法就是从点 出发,逐步地向外探寻最短路.算法执行过程中,与每一个点对应,记录一个数,它表示点 到该点的最短路的权(记为P标号),或表示点 到该点的最短路的权的上界(记为T标号),算法的每一步就是去修改T标号,并且把记为T标号的点改成记为P标号的点,从而使图中P标号的顶点数多一个,至多经过p-1步,就可以求出点 到各点的最短路径.

要求 点到其他各点的最短路径,各边的权表示路径长度,如图5所示.来.自/优尔论|文-网www.youerw.com/

解决问题步骤如下, 

   (1)与 点相邻的顶点有 , 两点, 最接近于 点,连接  ,令 .

   (2)与S={ , }相邻的点有 , , ,且 

        连接   .                 

   (3)与S={ , , }相邻的点有 , , ,且

       连接  、  .

   (4)与S={ , , , , }相邻的点有 , , , 

        连接  、  、   .

   (5)按照上述方式依次算下去,直到所有的点都连接起来为止.

最终结果如图6所示,

运用Lingo软件解决问题的方法是先建立模型.设图n个节点,赋权图的邻接矩阵为 ,其中 表示节点i到j的权值为p.为有向图时, ;为无向图时, 和 分别从图中读出.当 时,表示节点i与节点j不连通[6].

上一篇:凸函数的性质及其在不等式证明中的应用
下一篇:江苏省洪涝灾害风险评估

约束最优化问题的算法研...

无约束最优化问题的算法研究MATLAB实现

MATLAB图论问题解法研究

最优纯策略和混合策略水果种植方案的优化

邻接矩阵在图论中的应用

苏果超市基于GIS的物流配送路线优化研究

Arena航班计划的仿真与优化研究

ASP.net+sqlserver企业设备管理系统设计与开发

安康汉江网讯

互联网教育”变革路径研究进展【7972字】

张洁小说《无字》中的女性意识

我国风险投资的发展现状问题及对策分析

网络语言“XX体”研究

新課改下小學语文洧效阅...

LiMn1-xFexPO4正极材料合成及充放电性能研究

麦秸秆还田和沼液灌溉对...

老年2型糖尿病患者运动疗...