树-牡丹江师范学院.PPT

第10章 本章说明 树是图论中重要内容之一。 本章所谈回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。 本章说明 10.1 无向树及其性质 10.2 生成树 10.3 根树及其应用 本章小结 作 业 10.1 无向树及其性质 定义10.1 无向树——连通无回路的无向图，简称树，用T表示。 平凡树——平凡图。 森林——若无向图G至少有两个连通分支（每个都是树）。 树叶——无向树中悬挂顶点。 分支点——度数大于或等于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中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 (1)?(2) (2)?(3) (2)?(3) (3)?(4) 如果G中无回路且m＝n-1，则G是连通的且m＝n -1。 (4)?(5) 如果G是连通的且m＝n?1，则G是连通的且G中任何边均为桥。 (5)?(6) 如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 (6)?(1) 如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。 无向树的性质 定理10.2 设T是n阶非平凡的无向树，则T中至少有两片树叶。 例10.1 例10.1 画出6阶所有非同构的无向树。 解答 设Ti是6阶无向树。 由定理10.1可知，Ti的边数mi＝5， 由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。 于是Ti的度数列必为以下情况之一。 例10.1 例10.1 人们常称只有一个分支点，且分支点的度数为n-1的n(n≥3)阶无向树为星形图，称唯一的分支点为星心。 例10.2 例10.2 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。 解答 设Ti为满足要求的无向树，则边数mi＝6，于是 ∑d(vj)＝12＝3+3+d(v4)+d(v5)+d(v6)。 由于d(vj)≠1∧d(vj)≠3，而且d(vj)≥1且d(vj)≤6，j＝4,5,6，可知d(vj)＝2，j＝4,5,6。于是Ti 的度数列为 1，1，1，2，2，2，3 由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个顶点，这3个顶点的度数列只能为以下三种情况之一：1,1,2 1,2,2 2,2,2 设它们对应的树分别为T1，T2，T3。 例10.2 例题 例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。 解：设有x片树叶，于是结点总数为 n＝1+2+x＝3+x 由握手定理和树的性质m＝n?1可知， 2m＝2(n?1)＝2×(2+x) ＝1×3+2×2+x 解出x＝3，故T有3片树叶。 故T的度数应为1、1、1、2、2、3。 10.2 生成树 定义10.2 设G为无向图， （1）T为G的树—T是G的子图并且是树。 （2）T为G的生成树—T是G的生成子图并且是树。 （3）e为T的树枝—设T是G的生成树，?e∈E(G)， 若e∈E(T)。 （4）e为T的弦—设T是G的生成树，?e∈E(G)， 若e?E(T)。 （5）生成树T的余树—导出子图G[E(G)-E(T)] 。 生成树的存在条件 推论 推论1 G为n阶m条边的无向连通图，则m≥n?1。 证明 由定理10.3可知，G有生成树，设T为G的一棵生成树，则m＝|E(G)|≥|E(T)|＝n-1。 推论2 设G是n阶m条边的无向连通图，T为G的生成树，则T的余树中含有m-n+1条边（即T有m-n+1条弦）。 推论3 设T是连通图G的一棵生成树，T为T的余树， C为G中任意一个圈，则E(T)∩E(C)≠?。 证明 若E(T)∩E(C)＝?，则E(C)?E(T)， 这说明C为T中圈，与T为树矛盾。 所以推论正确。 定理10.4 基本回路与基本回路系统的定义 定义10.3 设T是n阶m条边的无向连通图G的一棵生成树，设e?1, e?2, …, e?m?n+1为T的弦。设Cr为T添加弦e?r产生的G中只含弦e?r，其余边均为树枝的圈，称Cr为G的对应T的弦e?r的基本回路或基本圈，r＝1, 2, …, m?n+1。称{C1, C2, …, Cm