第十六章树 ■无向树及其性质 ■生成树 ■根树及其应用
第十六章 树 无向树及其性质 生成树 根树及其应用
16.1无向树及其性质 ■无向树、森林 ■无向树的性质
16.1 无向树及其性质 无向树、森林 无向树的性质
无向树 无向树：连通无回路的无向图 平凡树：平凡图 森林：每个连通分支都是树的非连通的无向图 树叶：树中度数为1的顶点 分支点：树中度数≥2的顶点 右图为一棵12阶树. 声明：本章中所讨论的回路均 指简单回路或初级回路
无向树 无向树: 连通无回路的无向图 平凡树: 平凡图 森林: 每个连通分支都是树的非连通的无向图 树叶: 树中度数为1的顶点 分支点: 树中度数2的顶点 右图为一棵12阶树. 声明:本章中所讨论的回路均 指简单回路或初级回路
无向树的性质 定理16.1设G=<V,E>是n阶m条边的无向图，则下面 各命题是等价的： (1)G是树（连通无回路）； (2)G中任意两个顶点之间存在惟一的路径 (3)G中无回路且=n-1; (4)G是连通的且m=n-1; (5)G是连通的且G中任何边均为桥； (6)G中没有回路，但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈
无向树的性质 定理16.1 设G=<V,E>是n阶m条边的无向图，则下面 各命题是等价的： （1）G是树(连通无回路); （2）G中任意两个顶点之间存在惟一的路径; （3）G中无回路且m=n1; （4）G是连通的且m=n1; （5）G是连通的且G中任何边均为桥; （6）G中没有回路, 但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈
无向树的性质（续） 定理16.2设T是n阶非平凡的无向树，则T中至少 有两片树叶. 证设T有x片树叶，由握手定理及定理16.1可知， 2(n-1)=∑d()2x+2(n-x) 由上式解出x之2
无向树的性质(续) 2(n 1) d(v ) x 2(n x) i 定理16.2 设T 是 n 阶非平凡的无向树，则T中至少 有两片树叶. 证 设T有x片树叶，由握手定理及定理16.1可知， 由上式解出x2