一个树,结点的度最多为k(k>=2),试证至少有k个树叶
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/21 15:43:53
![一个树,结点的度最多为k(k>=2),试证至少有k个树叶](/uploads/image/z/7064423-71-3.jpg?t=%E4%B8%80%E4%B8%AA%E6%A0%91%2C%E7%BB%93%E7%82%B9%E7%9A%84%E5%BA%A6%E6%9C%80%E5%A4%9A%E4%B8%BAk%28k%3E%3D2%29%2C%E8%AF%95%E8%AF%81%E8%87%B3%E5%B0%91%E6%9C%89k%E4%B8%AA%E6%A0%91%E5%8F%B6)
一个树,结点的度最多为k(k>=2),试证至少有k个树叶
一个树,结点的度最多为k(k>=2),试证至少有k个树叶
一个树,结点的度最多为k(k>=2),试证至少有k个树叶
反证法.假设至多有s片树叶,s<k.则这棵树有s个1度节点,1个k度节点,剩下的节点的度数都至少是2.
设结点个数是n,则边数m=n-1,由握手定理,2m=2n-2=∑d(Vi)≥s×1+k×1+2(n-s-1),由此得s≥k.矛盾.
所以至少有k片树叶.