第二节树

5.2.1树图

在各式各样的图中，有一类及其简单的然而非常有用的图，这就是树。一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都能表达成一个树图。

|V|=n表示点的个数，|E|=m表示边的条数，可以证明以下树的概念是等价的：

⑴无回路的连通图；

⑵无回路且m=n－1；

⑶连通且m=n－1；

⑷无回路，但增加一条新边，得到一个且仅一个回路；

⑸连通但删去任一边后，就不连通了；

⑹每一对结点有一条且仅一条通路。

在一个连通图中，取部分边连接的所有点组成的树称为的部分树或支撑树(Spanning Tree)。图5-5是图5-4的部分树。

图有支撑树的充分必要条件是图是连通的。

5.2.2最小部分树

将网络图边上的权看作两点间的长度(距离、费用、时间)，定义的部分树的长度等于中每条边的长度之和，记为C()。的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。

最小部分树可以直接用作图的方法求解，常用的有破圈法和避圈法。

破圈法：任取一圈，去掉圈中最长边，直到无圈。

【例5.2】用破圈法求图5-6的最小树。

解：首先选定任一圈，比如，，，其中边[，]=5最长，去掉这条边，再选圈，，，有两条边的权相等，去掉其中任意一条，如此下去，得到支撑树为图5-7，总长为15。

避圈法：取图的个孤立点｛，，…，}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通(有条边)，对图5-5我们可以使用避圈法，得到与破圈法相同的支撑树。注意图的支撑树不是唯一的，但最小总长是唯一的。