第16章 树 离 散 数 学本章说明 q树是图论中重要内容之一。 q本章所谈回路均指初级回路（圈）或简单回路， 不含复杂回路（有重复边出现的回路）。16.1 无向树及其性质 定义16.1 无向树连通无回路的无向图，简称树，用T表示。 平凡树平凡图。 森林若无向图G至少有两个连通分支（每个都是树）。 树叶无向图中悬挂顶点。 分支点度数大于或等于2的顶点。 举例 如图为九个顶点的树。定理16.1 设G是n阶m条边的无向图，则下面各命题是等 价的： （1）G是树。 （2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且mn 1。 （4）G是连通的且mn 1。 （5）G是连通的且G中任何边均为桥。 （6）G中没有回路，但在任何两个不同的顶点之间加一条新边， 在所得图中得到唯一的一个含新边的圈。 无向树的等价定义(1)(2) 如果G是树，则G中任意两个顶点之间存在唯一的路径。 存在性。 由G的连通性及定理14.5的推论（在n阶图G中，若从顶点v i 到 v j (v i v j )存在通路，则v i 到v j 一定存在长度小于等于n-1的初 级通路(路径)）可知， u ,vV，u与v之间
