第五讲 树及其应用

　　一、小结
　　本讲主要介绍树与根树的概念与性质、最小生成树与最优树的解法。
　　1．树的概念
　　连通而无简单回路的无向图称为无向树，简称树．树中次数为1的顶点称为树叶．次数大于1的顶点称为分枝点或内部顶点。
一个无向图称为森林，如果它的每个连通分图是树。
　　2．树的6个等价定义及证明
　　给定图 T ，则以下关于图 T 为树的定义等价。
　　（1）无回路的连通图。
　　（2）无回路且e=v-1，其中 e 是边数，v 是顶点数。
　　（3）连通且e=v-1。