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所示．来.自/751论|文-网www.751com.cn/

解决问题步骤如下， 

   （1）与 点相邻的顶点有 ， 两点， 最接近于 点，连接  ，令 ．

   （2）与S={ ， }相邻的点有 ， ， ，且 

        连接   ．                 

   （3）与S={ ， ， }相邻的点有 ， ， ，且

       连接  、  ．

   （4）与S={ ， ， ， ， }相邻的点有 ， ， ， 

        连接  、  、   ．

   （5）按照上述方式依次算下去，直到所有的点都连接起来为止．

最终结果如图6所示，

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