例:无向树G有2个2度结点,1个3度结点,3个 4度结点,则其1度结点数为多少? 解:由握手定理2m∑d(v 及n=m+1 设G有个1顶点则有下列关系式 2x2+3+4x3+t=2m 2x(n-1) =2x(2+1+3+t-1) 解得:t=9
解：由握手定理 2m=∑d(vi ) 及n = m+1, 设G有t个1顶点, 则有下列关系式 2 x 2+3+4 x 3+t =2 m =2 x(n-1) =2 x(2+1+3+t-1) 解得：t = 9 。 例：无向树G有2个2度结点，1个3度结点，3个 4度结点，则其1度结点数为多少？
例:无向树G有8片树叶,2个3度分支点,其 余分支点均为4度,问G有多少个4度分支点? 画出其非同构的情况。 解:设G有个4度分支点,则有下列关系式 8x1+2x3+tx4=2x(8+2+t-1) 解得:t=2 则G中共有12个顶点,1条边,度数序列之 和为22,△(T)=4,δ(T=1,度序列为 1,1,1,1,1,1,1,3,3,4,4 其非构的图形为
解：设G有t个4度分支点，则有下列关系式 8 x 1+2 x 3+ t x 4 =2 x(8+2+t-1) 解得：t = 2 则G中共有12个顶点，11条边，度数序列之 和为22， △ (Ti )=4, (Ti )=1, 度序列为： 1,1,1,1,1,1,1,1,3,3,4, 4 其非同构的图形为： 例 ：无向树G有8片树叶，2个3度分支点，其 余分支点均为4度，问G有多少个4度分支点？ 画出其非同构的情况
其非同构的图形为:
。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 其非同构的图形为：
例:画出6阶所有非同构的无向树 解:有如下6种情况: (1,1,2,2,2,2) 1,1,1,3,2,2)(1,1,3,3,1,1) (1,1,4,2,1,1)
解： 有如下6种情况: (1,1,1,1,1,5) (1,1,2,2,2,2) (1,1,1,3,2,2) (1,1,3,3,1,1) (1,1,4,2,1,1) 例：画出6阶所有非同构的无向树
生成树 设G为无向图,着G的生成子图是一棵 树,则该树称为G的生成树。设G的生成树 为T,则T中的边称为树枝。G的不在生成树 T中的边称为弦。T的所有弦的集合的导出 子图称为T的余树。 注意:余树不一定是树。 一个无向连通图,如果它本身不是树, 它的生成树是不唯一的。但所有的连通图都 具有生成树
生成树 设G为无向图，若G的生成子图是一棵 树，则该树称为G的生成树。设G的生成树 为T，则T中的边称为树枝。G的不在生成树 T中的边称为弦。T的所有弦的集合的导出 子图称为T的余树。 注意：余树不一定是树。 一个无向连通图，如果它本身不是树， 它的生成树是不唯一的。但所有的连通图都 具有生成树