首页 > 试题广场 >

设无向树 T 有 3 个 3 度和 2 个 2 度顶点,其余

[单选题]

设无向树 T 3 3 度和 2 2 度顶点,其余顶点都是树叶,则 T 片树叶。

  • 3
  • 4
  • 5
  • 6
用到两个知识点:(m—边数;n—点数)
①握手定理:总度数=2*m
②在树中:m=n-1
发表于 2017-07-02 14:48:47 回复(2)
相关公式:
1、 树的总度数 = 2*总边数;
2、总边数 = 总结点数-1;(减一是因为根结点没有边连接)
则,树的总度数 = 2*(总结点数-1

设叶子结点数为x,
总结点数=3+2+x;
总度数数= 3*3+2*2+x;(叶子结点有一个入度)
则,
2*(3+2+x -1)= 3*3+2*2+ x;
x=5

发表于 2019-02-22 21:41:39 回复(0)
3 * 3 + 2 * 2 + x = (3 + 2 + x - 1) * 2
得 x = 5.
发表于 2017-05-22 19:32:11 回复(0)
看了以上解答,还是不明白。我自己直接画个图,去数结点个数,数出来就是9。
发表于 2019-10-27 15:06:00 回复(0)
问个问题~ 假设叶子节点的数目是n0
那么这题里面:
总结点数 n = 3 + 2 + n0
总边数 S = 3*3 + 2*2 = 14
总度数 m = 3*3 + 2*2 + n0
那为什么不可以用 S = n -1 推出n0=9呢?
发表于 2019-08-03 09:49:44 回复(0)
所有点的总度数是点的总数的两倍,但点的总数知否考虑减一(即去掉顶点)
发表于 2019-01-22 11:52:20 回复(0)