7图论－树10 19.ppt

第十六章 树 一、 无向树 1）定义： 连通无回路（初级回路或简单回路）的无向图称为无向树，或简称树 常用T表示树，平凡图称为平凡树． 若无向图G至少有两个连通分支，则称G为森林． 在无向树中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分支结点． 2）树的等价定义 设G＝V，E是n阶m条边的无向图， 则下面各命题是等价的： (1)G是连通无回路（树）． 可通过循环证明 (2) G中任意两个顶点之间存在惟一的路径． （连通则存在路径，若不唯一 （不同路径则构成回路） (3) G中无回路且 m = n - 1． 有长大于等于2的回路都与唯一路径矛盾 对结点进行归纳：n=1平凡图m= 0=n-1， 设n=k成立 n=k+1时 两个结点有唯一的路，去掉则为两个连通分支（各自满足假设） m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1 (4) G是连通的且 m = n - 1． 若不连通，对各个(s=2)连通分支是树且有mi=ni-1 m=n-s s=2 矛盾 (5)G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的初级回路． G无回路：n=1时成立， 归纳看n: 至少有一个结点度数为1（不然，结点的度=2则边=n) 去掉此结点所得到的G’无回路，再加上结点及边也无回路 任何二个结点有通路，增加一条新边构成简单回路（若不是初级的则删去此边，则G中必有简单回路） (6)G是连通的，但删去任何一条边后，所得图不连通． G连通：存在二个结点无通路，则在二个结点添加边后不会出现回路 由于无回路则删去任一条边，图不连通 只要证G无回路：若有回路-则删去一条边后仍连通-与条件矛盾 3）树的性质 对于给定的无向图—树是边数最小的连通图（mn-1则不连通） 树是边数最多的无回路图（mn-1则有回路） 结点的度： Σd(vi) = 2 m =2(n-1) 定理： 设T是n阶非平凡的无向树，则T中至少有两片树叶 设：所有结点度=2 则 Σd(vi) =2n 有一个结点度为1其余的=2 则 Σd(vi)=2(n-1)+1=2n-1 （也可以设k个度为1的结点，其余结点的度大于等于2 ） 例：无向树T中度为4、3、2的结点各一个，其余为树叶，树叶＝？ 4) 阶数n比较小的所有非同构的无向树． 例：画出6阶所有非同构的无向树． m=n-1=5 从树的节点之和来分析：结点之和为10分配给6个结点 1 1 1 1 1 5 1 1 1 1 2 4 1 1 1 1 3 3 1 1 1 2 2 3 1 1 2 2 2 2 例：7阶无向树中有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3．试画出满足要求的所有非同构的无向树． 从树的节点之和来分析： Ti为满足要求的无向树，则边数mi = 6， 于是∑d(vi)＝12＝3＋3 + d(v5)+d(v6)+d(v7) 1 1 1 2 2 2 3 2，2，2 加入如何组成结点的度数序列使之不同构 §16.2 生成树 （一些连通图不是树，但它的子图是树-重要的是生成树） 1、定义：设T是无向图G的子图并且为树，则称T为G的树． 若T是G的树且为生成子图，则称T是G的生成树． 设T是G的生成树，?e∈ E(G)，若e ∈ E(T)，则称e为T的树枝， 否则称e为T的弦．并称导出子图G[E(G)—E(T)]为T的余树，记作T ． 注：T不一定连通，也不一定不含回路 2、生成树的性质 1）定理：无向图G具有生成树当且仅当G是连通图 （破圈法-不断去掉回路） 2）设G为n阶m条边的无向连通图，则m =|E(G)|≥|E(T)| = n - 1． 3）设G是n阶m 条边的无向连通图，T为G的生成树， 则T的余树T中含m - n十1条边(即T有m—n+