用数学归纳法证明n阶无向树T有n-1边
证明:
当n=1时,因为树T没有回路,所以T的边数m=0,m=n-1成立。
设n=k时成立。当n=k+1时,则T至少有两片树叶,设v是一片树叶,删除v以及与之相邻的边。这时的树有n-1个顶点,m-1条边,有归纳假设知(m−1)=(n−1)−1.(m-1)=(n-1)-1.(m−1)=(n−1)−1.即m=n−1m=n-1m=n−1.
得证.
更多推荐
归纳法,数学
证明:
当n=1时,因为树T没有回路,所以T的边数m=0,m=n-1成立。
设n=k时成立。当n=k+1时,则T至少有两片树叶,设v是一片树叶,删除v以及与之相邻的边。这时的树有n-1个顶点,m-1条边,有归纳假设知(m−1)=(n−1)−1.(m-1)=(n-1)-1.(m−1)=(n−1)−1.即m=n−1m=n-1m=n−1.
得证.
更多推荐
归纳法,数学
发布评论