离散数学——树.ppt
第16章 树离离 散散 数数 学学本章说明本章说明q树是图论中重要内容之一。树是图论中重要内容之一。q本章所谈本章所谈回路均指初级回路（圈）或简单回路回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。不含复杂回路（有重复边出现的回路）。16.1 无向树及其性质无向树及其性质定义定义16.116.1无向树无向树连通无回路的无向图，简称树，用连通无回路的无向图，简称树，用T表示。表示。平凡树平凡树平凡图。平凡图。森林森林若无向图若无向图G至少有两个连通分支（每个都是树）。至少有两个连通分支（每个都是树）。树叶树叶无向图中悬挂顶点。无向图中悬挂顶点。分支点分支点度数度数大于或等于大于或等于2 2的顶点。的顶点。举例举例如图为九个顶点的树。如图为九个顶点的树。定理定理16.116.1 设设G 是是n阶阶m条边的无向图，则下面各命题是等条边的无向图，则下面各命题是等价的：价的：（1 1）G是树。是树。（2 2）G中任意两个顶点之间存在唯一的路径。中任意两个顶点之间存在唯一的路径。（3 3）G中无回路且中无回路且mn 1 1。（4 4）G是连通的且是连通的且mn 1 1。（5 5）G是连通的且是连通的且G G中任何边均为桥。中任何边均为桥。（6 6）G中没有回路，但在任何两个不同的顶点之间加一条新边，中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。在所得图中得到唯一的一个含新边的圈。无向树的等价定义无向树的等价定义(1)(1)(2)(2)如果如果G是树是树，则，则G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径。存在性。存在性。 由由G的连通性及定理的连通性及定理14.514.5的推论（的推论（在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj( (vi vj) )存在通路，则存在通路，则vi到到vj 一定存在长度小于等于一定存在长度小于等于n-1-1的初级的初级通路通路( (路径路径) )）可知，）可知， u, ,vV，u与与v之间存在路径。之间存在路径。唯一性唯一性（反证法）。（反证法）。 若路径不是唯一的，设若路径不是唯一的，设1 1与与2 2都是都是u到到v的路径，的路径，易知必存在由易知必存在由1 1和和2 2上的边构成的回路，上的边构成的回路，这与这与G中无回路矛盾。中无回路矛盾。(2)(2)(3)(3)如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径，则则G中无回路且中无回路且mn- -1 1。首先证明首先证明 G中无回路。中无回路。若若G中存在关联某顶点中存在关联某顶点v的环，的环，则则v到到v存在长为存在长为0 0和和1 1的两条路经的两条路经( (注意初级回路是路径的特殊情况注意初级回路是路径的特殊情况) )，这与已知矛盾。这与已知矛盾。若若G中存在长度大于或等于中存在长度大于或等于2 2的圈，的圈，则圈上任何两个顶点之间都存在两条不同的路径，则圈上任何两个顶点之间都存在两条不同的路径，这也与已知矛盾。这也与已知矛盾。(2)(2)(3)(3)如果如果G中任意两个顶点之间存在唯一的路径中任意两个顶点之间存在唯一的路径，则则G中无回路且中无回路且mn- -1 1。其次证明其次证明 mn-1-1。（归纳法）（归纳法）n1 1时，时，G为平凡图，结论显然成立。为平凡图，结论显然成立。设设nk( (k1)1)时结论成立，时结论成立，当当n= =k+1+1时，设时，设e( (u, ,v) )为为G中的一条边，中的一条边，由于由于G中无回路，所以中无回路，所以G- -e e为两个连通分支为两个连通分支G1 1、G2 2。设设ni、mi分别为分别为Gi中的顶点数和边数，则中的顶点数和边数，则nik ，i1,21,2，由归纳假设可知由归纳假设可知mini-1-1，于是于是mm1 1+ +m2 2+1+1n1 1-1+-1+n2 2-1+1-1+1n1 1+ +n2 2-1-1n-1-1。只需证明只需证明G是连通的。（采用反证法）是连通的。（采用反证法）假设假设G是不连通的，由是不连通的，由s( (s2) )个连通分支个连通分支G1,G2,Gs组成组成，并且并且Gi中均无回路，因而中均无回路，因而Gi全为树全为树。由由(1)(1)( (2)2)( (3)3)可知可知，mini- -1。于是于是，由于由于s2，与与mn- -1矛盾矛盾。111(1)sssiiiiiimmnnsns(3)(3)(4)(4)如果如果G中无回路且中无回路且mn-1-1，则则G是连通的且是连通的且mn -1-1。如果如果G是连通的且是连通的且mn 1，则则G是连通的且是连通的且G中任何边均为桥中任何边均为桥。只需证明只需证明G中每条边均为桥中每条边均为桥。 eE，均有均有| |E( (G- -e)|)|n- -1- -1n- -2，由习题十四题由习题十四题49（若若G是是n阶阶m条边的无向连通图，则条边的无向连通图，则mn- -1）可可知知，G- -e已不是连通图已不是连通图，所以所以，e为桥为桥。 (4)(4)(5)(5)如果如果G是连通的且是连通的且G中任何边均为桥中任何边均为桥，则，则G中没有回路，但在任中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈一个含新边的圈。因为因为G中每条边均为桥，删掉任何边，将使中每条边均为桥，删掉任何边，将使G变成不连通图，变成不连通图，所以，所以，G中没有回路，也即中没有回路，也即G中无圈。中无圈。又由于又由于G连通，所以连通，所以G为树，由为树，由(1) (2)可知，可知， u,vV，且且uv，则则u与与v之间存在唯一的路径之间存在唯一的路径，则则( (u,v) )（( (u,v) )为加的新边为加的新边）为为G中的圈，中的圈，显然圈是唯一的。显然圈是唯一的。(5)(5)(6)(6)如果如果G中没有回路，但在任何两个不同的顶点之间加一条新边，中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈在所得图中得到唯一的一个含新边的圈，则，则G是树是树。只需证明只需证明G是连通的。是连通的。 u,vV，且且uv，则新边则新边( (u,v) )G产生唯一的圈产生唯一的圈C，显然有显然有C -(-(u,v) )为为G中中u到到v的通路，故的通路，故uv，由由u,v的任意性可知，的任意性可知，G是连通的。是连通的。(6)(6)(1)(1)定理定理16.216.2 设设T是是n阶非平凡的无向树，则阶非平凡的无向树，则T中至少有两片树叶。中至少有两片树叶。设设T有有x片树叶，由握手定理及定理片树叶，由握手定理及定理16.116.1可知，可知，证明证明2(1)( )2()ind vxnx由上式解出由上式解出x2 2。无向树的性质无向树的性质例例16.116.1例例16.116.1 画出画出6 6阶所有非同构的无向树。阶所有非同构的无向树。 解答解答 设设Ti是是6 6阶无向树。阶无向树。由定理由定理16.116.1可知，可知，Ti的边数的边数mi5 5，由握手定理可知，由握手定理可知，dTi( (vj) )1010，且且(Ti)1)1，( (Ti)5)5。于是于是Ti的度数列必为以下情况之一。的度数列必为以下情况之一。(1) 1，1，1，1，1，5(2) 1，1，1，1，2，4(3) 1，1，1，1，3，3(4) 1，1，1，2，2，3(5) 1，1，2，2，2，2(4)(4)对应两棵非同构的树，对应两棵非同构的树，在一棵树中两个在一棵树中两个2 2度顶点相邻，度顶点相邻，在另一棵树中不相邻，在另一棵树中不相邻，其他情况均能画出一棵非同构其他情况均能画出一棵非同构的树。的树。例例16.116.1q 人们常称只有一个分支点，且分支点的度数为人们常称只有一个分支点，且分支点的度数为n-1-1的的n( (n3)3)阶无向树为阶无向树为星形图星形图，称唯一的分支点为，称唯一的分支点为星心星心。 例例16.216.2例例16.216.2 7 7阶无向图有阶无向图有3 3片树叶和片树叶和1 1个个3 3度顶点，其余度顶点，其余3 3个顶点的度数个顶点的度数均无均无1 1和和3 3。试画出满足要求的所有非同构的无向树。试画出满足要求的所有非同构的无向树。解答解答 设设Ti为满足要求的无向树，则边数为满足要求的无向树，则边数mi6 6，于是于是d( (vj) )1212e+3+3+d( (v4 4)+)+d( (v5 5)+)+d( (v6 6) )。由于由于d( (vj)1d()1d(vj)3)3，而且而且d( (vj)1)1且且d( (vj)6)6，j4,5,64,5,6，可知可知d(d(vj) )2 2，j4,5,64,5,6。于是于是Ti 的度数列为的度数列为1 1，1 1，1 1，2 2，2 2，2 2，3 3由度数列可知，由度数列可知，Ti中有一个中有一个3 3度顶点度顶点vi，vi的邻域的邻域N( (vi) )中有中有3 3个顶个顶点，这点，这3 3个顶点的度数列只能为以下三种情况之一：个顶点的度数列只能为以下三种情况之一：1,1,21,1,21,2,21,2,22,2,22,2,2设它们对应的树分别为设它们对应的树分别为T1 1，T2 2，T3 3。此度数列只能产生这三棵。此度数列只能产生这三棵非同构的非同构的7 7阶无向树。阶无向树。例例16.216.2例题例题例题例题 已知无向树已知无向树T中，有中，有1 1个个3 3度顶点，度顶点，2 2个个2 2度顶点，其余度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。的无向树。 解答解答 设有设有x片树叶，于是结点总数为片树叶，于是结点总数为n1+2+1+2+x3+3+x 由握手定理和树的性质由握手定理和树的性质mn 1 1可知，可知，2 2m2(2(n 1)1)2 2(2+(2+x) ) 1 13+23+22+2+x解出解出x3 3，故故T有有3 3片树叶。片树叶。故故T的度数应为的度数应为1 1、1 1、1 1、2 2、2 2、3 3。例题例题 已知无向树已知无向树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个个。故故T的度数列为的度数列为1、1、1、1、1、2、3、4。例题例题小节结束小节结束例题例题16.2 16.2 生成树生成树 定义定义16.216.2 设设G为无向图，为无向图，（1 1）T为为G的的树树T是是G的子图并且是树。的子图并且是树。（2 2）T为为G的的生成树生成树T是是G的生成子图并且是树。的生成子图并且是树。（3 3）e为为T的的树枝树枝设设T是是G的生成树，的生成树， eE( (G) )，若若eE( (T) )。（4 4）e为为T的的弦弦设设T是是G的生成树，的生成树， eE( (G) )，若若e e E( (T) )。（5 5）生成树）生成树T的的余树余树导出子图导出子图G E( (G)-)-E( (T) ) 。记作。记作T注意：注意： 不一定连通，也不一定不含回路。不一定连通，也不一定不含回路。T说明说明 定理定理16.316.3 无向图无向图G具有生成树当且仅当具有生成树当且仅当G连通。连通。证明证明必要性必要性，显然。，显然。充分性充分性（破圈法）。（破圈法）。 若若G中无回路，中无回路，G为自己的生成树。为自己的生成树。 若若G中含圈，任取一圈，随意地删除圈上的一条边，中含
