最少树叶数 定理162设T是n阶非平凡的无向树,则至少存在两片树叶 1、顶点数确定则边数确定 2、叶子顶点度为1; 根据定理16,1,n阶非平凡无向树的边数为n-1,度数为2n-2。 若叶子顶点为k个,则分支点数量为nk个,且其度数均大于等于2。 因此T的度数至少为2(n-k)+k=2n-k。 若k小于2,则T的度数将大于2n2,与定理161的结论矛盾 东南大学计算机科学与工程学院 同的出学 图论定理 16.2 设T是n阶非平凡的无向树,则T至少存在两片树叶。 根据定理16.1，n阶非平凡无向树的边数为n-1，度数为2n-2。 若叶子顶点为k个，则分支点数量为n-k个，且其度数均大于等于2。 因此T的度数至少为2(n-k)+k=2n-k。 若k小于2，则T的度数将大于2n-2，与定理16.1的结论矛盾。 1、顶点数确定则边数确定； 2、叶子顶点度为1；