哈尔滨工程大学碑斛监髁程 离影数 第16章树 软件与理论教硏室
第16章 树 离 散 数 学 哈尔滨工程大学本科生课程 软件与理论教研室
本章说明 口树是图论中重要内容之一。 口本章所谈回路均指初级回路(圈)或简单回路, 不含复杂回路(有重复边出现的回路)
本章说明 ❑树是图论中重要内容之一。 ❑本章所谈回路均指初级回路（圈）或简单回路， 不含复杂回路（有重复边出现的回路）
本章说明 16.1无向树及其性质 16.2生成树 16.3根树及其应用 本章小结 习作 题
16.1 无向树及其性质 16.2 生成树 16.3 根树及其应用 本章小结 习 题 作 业 本章说明
16.1无向树及基性质 定义16.1 无向树——连通无回路的无向图,简称树,用T表示。 平凡树—平凡图。 森林—若无向图G至少有两个连通分支(每个都是树 树叶无向图中悬挂顶点。 分支点—度数大于或等于2的顶点 举例如图为九个顶点的树
16.1 无向树及其性质 定义16.1 无向树——连通无回路的无向图，简称树，用T表示。 平凡树——平凡图。 森林——若无向图G至少有两个连通分支（每个都是树）。 树叶——无向图中悬挂顶点。 分支点——度数大于或等于2的顶点。 举例 如图为九个顶点的树
无向树的等价定义 定理16.1设G=是m阶m条边的无向图,则下面各命题是等 价的: (1)G是树。 (2)G中任意两个顶点之间存在唯一的路径。 (3)G中无回路且m=n-1。 (4)G是连通的且m=n-1。 (5)G是连通的且a中任何边均为桥。 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边, 在所得图中得到唯一的一个含新边的圈
定理16.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) 如果G是树,则G中任意两个顶点之间存在唯一的路径。 存在性。 由G的连通性及定理145的推论(在n阶图G中,若从顶点v到 (v;ν)存在通路,则v到v一定存在长度小于等于n1的初 级通路(路径)可知, u,v∈V,u与ν之间存在路径。 唯一性(反证法)。 若路径不是唯一的,设厂1与/2都是n到v的路径, 易知必存在由厂和2上的边构成的回路, 这与G中无回路矛盾
(1)(2) 如果G是树，则G中任意两个顶点之间存在唯一的路径。 存在性。 由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到 vj(vi vj)存在通路，则vi到vj 一定存在长度小于等于n-1的初 级通路(路径)）可知， u,v∈V，u与v之间存在路径。 唯一性（反证法）。 若路径不是唯一的，设Г1与Г2都是u到v的路径， 易知必存在由Г1和Г2上的边构成的回路， 这与G中无回路矛盾
(2)→(3) 如果G中任意两个顶点之间存在唯一的路径, 则G中无回路且m=n-1。 首先证明G中无回路。 若G中存在关联某顶点v的环, 则吨到w存在长为0和1的两条路经 注意初级回路是路径的特殊情况), 这与已知矛盾。 若G中存在长度大于或等于2的圈, 则圈上任何两个顶点之间都存在两条不同的路径, 这也与已知矛盾
(2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 首先证明 G中无回路。 若G中存在关联某顶点v的环， 则v到v存在长为0和1的两条路经 (注意初级回路是路径的特殊情况)， 这与已知矛盾。 若G中存在长度大于或等于2的圈， 则圈上任何两个顶点之间都存在两条不同的路径， 这也与已知矛盾
(2)→(3) 如果G中任意两个顶点之间存在唯一的路径, 则G中无回路且m=n-1。 其次证明m=m-1。(归纳法) n=1时,G为平凡图,结论显然成立。 设n≤k(k≥1)时结论成立, 当n=k+1时,设e=(u,吵为G中的一条边, 由于G中无回路,所以Ge为两个连通分支G、G20 设n、m分别为G中的顶点数和边数,则n≤k,i=1,2, 由归纳假设可知m=n-1,于是 m=m+m2+1=m1-1+n2-1+1=n1+n2-1=n-1
(2)(3) 如果G中任意两个顶点之间存在唯一的路径， 则G中无回路且m＝n-1。 其次证明 m＝n-1。（归纳法） n＝1时，G为平凡图，结论显然成立。 设n≤k(k≥1)时结论成立， 当n=k+1时，设e＝(u,v)为G中的一条边， 由于G中无回路，所以G-e为两个连通分支G1、G2。 设ni、mi分别为Gi中的顶点数和边数，则ni≤k ，i＝1,2， 由归纳假设可知mi＝ni-1，于是 m＝m1+m2 +1＝n1 -1+n2 -1+1＝n1 +n2 -1＝n-1
(3)→(4) 如果G中无回路且m=m-1,则G是连通的且m=n-1。 只需证明G是连通的。(采用反证法) 假设G是不连通的,由s(s≥2)个连通分支GG2灬G组成,并 且G中均无回路,因而G全为树。 由(1)→(2)→(3)可知,m,=n;-1。于是, m=∑m=∑(m-1)=∑n-S=n-s 由于s≥2,与m=n-1矛盾
只需证明G是连通的。（采用反证法） 假设G是不连通的，由s(s≥2)个连通分支G1 ,G2 ,…,Gs组成，并 且Gi中均无回路，因而Gi全为树。 由(1)(2)(3)可知，mi ＝ni -1。于是， 由于s≥2，与m＝n-1矛盾。 1 1 1 ( 1) s s s i i i i i i m m n n s n s = = = = = − = − = − (3)(4) 如果G中无回路且m＝n-1，则G是连通的且m＝n -1
(4)→(5) 如果G是连通的且m=n1,则G是连通的且G中任何边均为桥 只需证明G中每条边均为桥。 Ve∈E,均有|E(G-e)|=m1-1=m2, 由习题十四题49(若G是n阶m条边的无向连通图,则mn1)可 知,Ge已不是连通图, 所以,e为桥
如果G是连通的且m＝n−1，则G是连通的且G中任何边均为桥。 只需证明G中每条边均为桥。 e∈E，均有|E(G-e)|＝n-1-1＝n-2， 由习题十四题49（若G是n阶m条边的无向连通图，则m≥n-1）可 知，G-e已不是连通图， 所以，e为桥。 (4)(5)