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