离散数学 树.ppt

第十二章树主讲:熊焕亮
第十二章树
树是图论中重要内容之一,在计算机科学技术中有着广泛的应用。树的概念由数学家约当(Jordan)给出了统一的定义。
在讨论本章内容之前,首先作个说明,就是本章所谈回路均指初级回路(圈)或简单回路,而不含复杂回路(有重复边出现的回路)。
2
第十二章树
树的概念及性质
最小生成树
根树
树的应用*
3

树的定义
树的一些性质
4
树的定义
若简单连通无回路的无向图称为无向树,或简称树,常用表示树,平凡图称为平凡树。无向树中度数为1的顶点称为树叶,度数大于等于2的顶点称为分支点,只有一个顶点(无边)的简单图称为平凡树;若无向图G 至少有两个连通分支,则称G 为森林。
也就是说,(无向)树是连通无回路的简单图,后面提到树时,如果没有特别说明都是指无向树,在证明树的性质前,先回忆一下桥(或说割边)的定义,将看到树的每一条边都是桥。
5
树的定义
给定图,说边是G 的桥(割边),如果,即G 中删除之后会增加连通分支数。
显然,如果e是G 的桥,则有,即删除一条边,最多增加一个连通分支,另一方面,若e是G 的桥,则e不属于G 的任意回路。
6
树的一些性质
无向树有许多性质,这些性质中有些既是树的必要条件又是充分条件,因而都可以看作树的等价定义,见下面定理
7
树的一些性质
设是n阶m条边的无向图,则下面各命题是等价的:
(1)G 是树。
(2)G 中任意两个顶点之间存在惟一的路径。
(3)G 中无回路且。
(4)G 是连通的且。
(5)G 是连通的且G 中任何边均为桥。
(6)G 中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到惟一的一个含新边的圈。
8
树的一些性质
证(1) (2)
对n作归纳,n=1时,m =0,显然有m =n-1。假设n=k时命题成立,现证n=k+1也成立。
由于G 连通而无回路,所以G 中至少有一个度数为1的结点,在G 中删去及其关联的边,便得到k个结点的连通而无回路的图,由归纳假设知它有k-1条边。再将结点及其关联的边加回到原图G ,所以G 中含有k+1个结点和k条边,符合公式m=n-1。
所以,G中无回路,且m=n-1。
9
树的一些性质
(2)(3):首先证明G 中无回路。若G 中存在关联某顶点v的环,则v到v存在长为0和1的两条路径(注意初级回路是路径的特殊情况),这与已知矛盾。若G 中存在长度大于或等于2的圈,则圈上任何两个顶点之间都存在两条不同的路径,这也引出矛盾,下面用归纳法证明m=n-1。
n=1时,G 为平凡图,结论显然成立。设n 时结论成立,当n=k+1时,设为G 中的一条边,由于G 中无回路,所以G-e为两个连通分支。设分别为中的顶点数和边数,则,由归纳假设可知,于是, 。
10