中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第三部分 图论 第十二章 树

离散数学 第十二章树 主要内容 ●无向树及其性质 ●生成树 ●根树及其应用 1

1 第十二章 树 主要内容 ⚫ 无向树及其性质 ⚫ 生成树 ⚫ 根树及其应用

离散数学 12.1无向树及其性质 定义12.1连通无回路的无向图称为无向树，简称树.每个连 通分支都是树的无向图称为森林.平凡图称为平凡树.在无 向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为 分支点 例 星形树

12.1 无向树及其性质 定义12.1 连通无回路的无向图称为无向树,简称树.每个连 通分支都是树的无向图称为森林.平凡图称为平凡树.在无 向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为 分支点． 例 f 星形树

离散数学 无向树的性质 定理12.1设G=是阶条边的无向图，则下面各命题 是等价的： (1)G是树 (2)G中任意两个顶点之间存在惟一的路径. (3)G中无回路且n-1. (4)G是连通的且mn-1. (⑤)G是连通的且G中任何边均为桥. (⑥)G中没有回路，但在任何两个不同的顶点之间加一条新 边后所得图中有惟一的一个含新边的圈. 3

3 无向树的性质 定理12.1 设G=是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且m=n−1. (4) G 是连通的且m=n−1. (5) G 是连通的且G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新 边后所得图中有惟一的一个含新边的圈

离散数学 证明 证(1)→(2).若路径不惟一，必有回路. (2)→3).若G中有回路，则回路上任意两点之间的路径不 惟一.对n用归纳法证明n-1. 当=1时成立.设≤k时成立，证=k+1时也成立：任取 一条边e,G-e有且仅有两个连通分支G,G2.n≤k,由归 纳假设得m,=n-1,=1,2.于是， tFm1+m2+1=n1+n2-2+1=n-1. (3)=→(4).只需证明G连通.用反证法.否则G有s(s≥2)个连通 分支，它们都是树.于是，有m,=-1, m=∑m,=∑4-s=n-ss≥2) i=1 i= 这与n-1矛盾. 4

4 (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni−1, 这与m=n−1矛盾. 证明 (2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n−1. 当n=1时成立. 设nk时成立，证n=k+1时也成立：任取 一条边e，G−e有且仅有两个连通分支G1 ,G2 . nik，由归 纳假设得mi=ni−1, i=1,2. 于是， m=m1+m2+1=n1+n2−2+1=n−1. ( 2) 1 1 =  =  − = −  = = m m n s n s s s i i s i i 证 (1)(2). 若路径不惟一, 必有回路

离散数学 证明 (4)→（⑤）.只需证明G中每条边都是桥.下述命题显然成立：G 是n阶m条边的无向连通图，则m心n-1. Ve∈E,G-e只有n-2条边，由命题可知G-e不连通，故e为桥 (⑤)=→>（⑥.由（⑤）易知G为树.由(1)→(2)知，u,veV(u≠v), u到v有惟一路径，加新边(w,)得惟一的一个圈. (6)→(1).只需证明G连通，这是显然的. 5

5 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn−1. eE, G−e只有n−2条边，由命题可知G−e不连通，故e为桥. 证明 (5)(6). 由(5)易知G为树. 由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的

离散数学 无向树的性质 定理12.2设T是阶非平凡的无向树，则T中至少有两片树叶. 证设T有x片树叶，由握手定理及定理10.1可知， 2(n-1)=∑d(y)≥x+2(n-x) 解得x≥2. 例1已知无向树T中有1个3度顶点，2个2度顶点，其余顶点 全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 解设有x片树叶，n=3+x 2m=2(-1)=2x(2+x)=1×3+2×2+x 解出x=3,故T有3片树叶

2(n 1) d(v ) x 2(n x) − = i  + − 解得 x  2. 定理12.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 无向树的性质 证 设 T 有 x 片树叶，由握手定理及定理10.1可知， 例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点 全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 解 设有x片树叶，n = 3+x. 2m = 2(n−1) = 2(2+x) = 13+22+x 解出x = 3，故T有3片树叶

离散数学 例题 例2已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数，并画出满足要求的所有非同 构的无向树 解设T的阶数为n,则边数为n-1,4度顶点的个数为n-7. 由握手定理，2m=2(n-1)=5×1+2×1+3×1+4(n-7), 解出n=8,4度顶点为1个 7

7 例2 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n，并画出满足要求的所有非同 构的无向树. 例题 解 设T的阶数为n, 则边数为n−1，4度顶点的个数为n−7. 由握手定理, 2m = 2(n−1) = 51+21+31+4(n−7), 解出n = 8，4度顶点为1个

离散数学 12.2生成树 定义12.2如果无向图G的生成子图T是树，则称T是G的生 成树.设T是G的生成树，G的在T中的边称为T的树枝，不 在T中的边为T的弦.称T的所有弦的导出子图为T的余树， 记作页. 例 8

8 12.2 生成树 定义12.2 如果无向图G的生成子图T是树，则称T是G的生 成树. 设T是G的生成树，G的在T中的边称为T的树枝，不 在T中的边为T的弦. 称T的所有弦的导出子图为T的余树， 记作 . 例 T

离散数学 生成树存在条件 定理12.3无向图G有生成树当且仅当G连通. 证必要性显然.证充分性.若G中无回路，则G为自己的生 成树.若G中含圈，任取一圈，随意地删除圈上的一条边； 若仍有圈，再任取一个圈并删去这个圈上的一条边，重复进 行，直到最后无圈为止.最后得到的图无圈（当然无回路）、 连通且是G的生成子图，因而是G的生成树， 这个产生生成树的方法称为破圈法。 推论G为n阶m条边的无向连通图，则m心n-1. 9

9 定理12.3 无向图G有生成树当且仅当G连通. 生成树存在条件 推论 G为n阶m条边的无向连通图，则mn−1. 证 必要性显然. 证充分性．若G中无回路，则G为自己的生 成树．若G中含圈，任取一圈，随意地删除圈上的一条边; 若仍有圈, 再任取一个圈并删去这个圈上的一条边，重复进 行, 直到最后无圈为止. 最后得到的图无圈（当然无回路）、 连通且是G的生成子图，因而是G的生成树． 这个产生生成树的方法称为破圈法．

离散数学 最小生成树 定义12.3设无向连通带权图G= 输出：G的最小生成树T l.将G中非环边按权从小到大排列：W(e1)≤We2)..≤Wem) 2.令Tk-{e1},ik-2. 3.若e,与T中的边不构成回路，则令T←几U{e 4.若T<n-1,则令ik-i计1，转3. 10

10 最小生成树 定义12.3 设无向连通带权图G=，T是G的一棵生成 树，T的各边权之和称为T的权，记作W(T)．G的所有生成树 中权最小的生成树称为G的最小生成树. 避圈法（Kruskal） 输入: 连通图G= 输出: G的最小生成树T 1. 将G中非环边按权从小到大排列: W(e1 )W(e2 ) …W(em). 2. 令T{e1 }, i2. 3. 若ei与T中的边不构成回路, 则令TT{ei }. 4. 若|T|<n-1, 则令ii+1, 转3