哈尔滨工程大学碑斛监髁程 离影数 第16章树 软件与理论教硏室
第16章 树 离 散 数 学 哈尔滨工程大学本科生课程 软件与理论教研室
本章说明 口树是图论中重要内容之一。 口本章所谈回路均指初级回路(圈)或简单回路, 不含复杂回路(有重复边出现的回路)
本章说明 ❑树是图论中重要内容之一。 ❑本章所谈回路均指初级回路（圈）或简单回路， 不含复杂回路（有重复边出现的回路）
本章说明 16.1无向树及其性质 16.2生成树 16.3根树及其应用 本章小结 习作 题
16.1 无向树及其性质 16.2 生成树 16.3 根树及其应用 本章小结 习 题 作 业 本章说明
16.1无向树及基性质 定义16.1 无向树——连通无回路的无向图,简称树,用T表示。 平凡树—平凡图。 森林—若无向图G至少有两个连通分支(每个都是树 树叶无向图中悬挂顶点。 分支点—度数大于或等于2的顶点 举例如图为九个顶点的树
16.1 无向树及其性质 定义16.1 无向树——连通无回路的无向图，简称树，用T表示。 平凡树——平凡图。 森林——若无向图G至少有两个连通分支（每个都是树）。 树叶——无向图中悬挂顶点。 分支点——度数大于或等于2的顶点。 举例 如图为九个顶点的树
无向树的等价定义 定理16.1设G=<VE>是m阶m条边的无向图,则下面各命题是等 价的: (1)G是树。 (2)G中任意两个顶点之间存在唯一的路径。 (3)G中无回路且m=n-1。 (4)G是连通的且m=n-1。 (5)G是连通的且a中任何边均为桥。 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边, 在所得图中得到唯一的一个含新边的圈
定理16.1 设G＝<V,E>是n阶m条边的无向图，则下面各命题是等 价的： （1）G是树。 （2）G中任意两个顶点之间存在唯一的路径。 （3）G中无回路且m＝n−1。 （4）G是连通的且m＝n−1。 （5）G是连通的且G中任何边均为桥。 （6）G中没有回路，但在任何两个不同的顶点之间加一条新边， 在所得图中得到唯一的一个含新边的圈。 无向树的等价定义