《离散数学》课程教学课件（PPT讲稿）10 树

树

析取范式与合取范式 树

树的概念是亚瑟凯莱1提出的饱和碳氢化合物与树英国数学家亚瑟·凯莱在1857年发明了树，当时他试图列举饱和碳氢化合物CnH2n+2的同分异构体左图为什么是树？H结点数：1H-C-HHHH=n+(2n+2)=3n+2H-C-H1H-CCC-HH-C-H1结点度数之和：HHH-C-HH-C-H14×n+1x(2n+2)=6n+2HH(a）丁烷(b）异丁烷则边数e=3n+1.因是连通图，且e=u-1,所以是树1ArthurCayley（1821-1895）17岁进入剑桥三一学院学习，1849年获律师资格，在其律师生涯中写下了超过300篇的数学论文.1863年返回剑桥任教职黄正华（武汉大学）离散数学第7章树December 2.2012856

析取范式与合取范式

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

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

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

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

证明(1) G 是树(2)G中任意两个顶点之间存在惟一的路径.(3)G 中无回路且 m=n-1.证(1)二(2).若路径不惟一,必有回路(2)二(3). 若G中有回路，则回路上任意两点之间的路径不惟一.对n用归纳法证明m=n-1.当n=1时成立.设n≤k时成立，证n=k+1时也成立：任取一条边e，G-e有且仅有两个连通分支G1,G2·n;<k，由归纳假设得m;=n;-1,i=1,2. 于是,m=mi+m2+1=n1+n2-2+1=n-15

5 证明 (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. 证 (1)(2). 若路径不惟一, 必有回路. (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且 m=n−1

证明(3)G中无回路且m=n-1.(4) G 是连通的且 m=n-1.(3)二(4).只需证明G连通.用反证法.否则G有s(s≥2)个连通分支，它们都是树.于是，有m=n一1,m=mi=ni- s= n- s (s ≥ 2)i=1i=1这与m=n-1矛盾.6

6 (3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通 分支, 它们都是树. 于是, 有mi=ni−1, 这与m=n−1矛盾. 证明 𝑚 = ෍ 𝑖=1 𝑠 𝑚𝑖 = ෍ 𝑖=1 𝑠 𝑛𝑖 − 𝑠 = 𝑛 − 𝑠 (𝑠 ≥ 2) (3) G 中无回路且 m=n−1. (4) G 是连通的且 m=n−1

证明(4)G是连通的且m=n-1.(5)G是连通的且G中任何边均为桥(4)二(5).只需证明G中每条边都是桥.下述命题显然成立：G是n阶m条边的无向连通图，则mzn-1VeEE,G-e只有n-2条边，由命题可知G-e不连通，故e为桥7

7 (4)(5). 只需证明G 中每条边都是桥. 下述命题显然成立: G 是 n 阶 m 条边的无向连通图，则 mn−1. eE, G−e只有n−2条边，由命题可知G−e不连通，故e为桥. 证明 (4) G 是连通的且 m=n−1. (5) G 是连通的且 G 中任何边均为桥

证明(1) G 是树(2) G中任意两个顶点之问存在惟一的路径.(5)G是连通的且G中任何边均为桥(6)G中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的图。(5)=(6). 由(5)易知G为树. 由(1)=>(2)知， Vu,VEV (uV) u到v有惟一路径，加新边(u,v)得惟一的一个图.(6)二(1). 只需证明G连通， 这是显然的8

8 证明 (5)(6). 由(5)易知G为树. 由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的. (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间 加一条新边后所得图中有惟一的一个含新边的圈

无向树的性质定理10.2设T是n阶非平凡的无向树，则T中至少有两片树叶证设T有X片树叶，由握手定理及定理10.1可知，2(n - 1) = d(vi) ≥ x + 2(n - x)解得x≥2

𝟐(𝒏 − 𝟏) = ෍𝒅(𝒗𝒊) ≥ 𝒙 + 𝟐(𝒏 − 𝒙) 解得 x  2. 定理10.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 无向树的性质 证 设 T 有 x 片树叶，由握手定理及定理10.1可知

无向树的性质例1已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树解设有x片树叶，n=3+x.2m = 2(n-1) = 2x(2+x) = 1x3+2×2+x解出×=3，故T有3片树叶

无向树的性质 例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片树叶