一道离散数学证明题设T为平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2.抱歉抱歉,原题打错了,是非平凡无向树,
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/12 23:09:19
![一道离散数学证明题设T为平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2.抱歉抱歉,原题打错了,是非平凡无向树,](/uploads/image/z/3005250-42-0.jpg?t=%E4%B8%80%E9%81%93%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%E8%AF%81%E6%98%8E%E9%A2%98%E8%AE%BET%E4%B8%BA%E5%B9%B3%E5%87%A1%E6%97%A0%E5%90%91%E6%A0%91%2CT%E4%B8%AD%E5%BA%A6%E6%95%B0%E6%9C%80%E5%A4%A7%E7%9A%84%E8%8A%82%E7%82%B9%E6%9C%89%E4%B8%A4%E4%B8%AA%2C%E4%B8%94%E5%BA%A6%E6%95%B0K%3E%3D2%2C%E6%B1%82%E8%AF%81T%E5%8F%B6%E5%AD%90%E8%8A%82%E7%82%B9%E7%9A%84%E6%95%B0%E9%87%8F%3E%3D2K-2.%E6%8A%B1%E6%AD%89%E6%8A%B1%E6%AD%89%EF%BC%8C%E5%8E%9F%E9%A2%98%E6%89%93%E9%94%99%E4%BA%86%EF%BC%8C%E6%98%AF%E9%9D%9E%E5%B9%B3%E5%87%A1%E6%97%A0%E5%90%91%E6%A0%91%EF%BC%8C)
一道离散数学证明题设T为平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2.抱歉抱歉,原题打错了,是非平凡无向树,
一道离散数学证明题
设T为平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2.
抱歉抱歉,原题打错了,是非平凡无向树,
一道离散数学证明题设T为平凡无向树,T中度数最大的节点有两个,且度数K>=2,求证T叶子节点的数量>=2K-2.抱歉抱歉,原题打错了,是非平凡无向树,
1.因为每一个非根节点,要么有两个叶子,要么有一个叶子,最少的情况就是,只有一个叶子,且叶子也至多有一个子叶子.度数=n的节点,对应的最终叶子的数量>=n
2. 度数最大的节点必然是根节点的直接后继,否则必然导致矛盾.因为如果不是直接后继的话,那么它的父节点的叶子个数就比它大至少1了.
所以这两个度数"最大"的节点的度数=K-1,所以这两棵树的叶子的数量>2*(K-1)=2K-2
3.当然根节点还可以有其他的子数或者叶子,所以
T总叶子节点的数量>=2K-2
得证
设叶子节点的数量为X个,非叶子非度数最大的节点个数为Y个,最大的节点有两个,故全部节点为X+Y+2,由树的边数是节点数减1,故边数为X+Y+2-1=X+Y+1,所有节点的度数之和为边数的两倍,故所有节点的度数之和为2(X+Y+1),
非叶子非度数最大的节点度数至少为2度,故非叶子非度数最大的节点度数之和>=2Y,故
所有节点的度数之和=叶子节点度数之和+非叶子非度数最大的节点度数之...
全部展开
设叶子节点的数量为X个,非叶子非度数最大的节点个数为Y个,最大的节点有两个,故全部节点为X+Y+2,由树的边数是节点数减1,故边数为X+Y+2-1=X+Y+1,所有节点的度数之和为边数的两倍,故所有节点的度数之和为2(X+Y+1),
非叶子非度数最大的节点度数至少为2度,故非叶子非度数最大的节点度数之和>=2Y,故
所有节点的度数之和=叶子节点度数之和+非叶子非度数最大的节点度数之和+度数最大的两个节点度数之和>=X+2Y+2K,
即2(X+Y+1)>=X+2Y+2K,由此得X>=2K-2。
收起
确实