树
析取范式与合取范式 树
树的概念是亚瑟凯莱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=<V,E>是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=<V,E>是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时成立. 设nk时成立，证n=k+1时也成立：任取 一条边e，G−e有且仅有两个连通分支G1 ,G2 . nik，由归 纳假设得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