用数学归纳法证明n阶无向树T有n

编程入门行业动态更新时间:2024-10-26 15:29:58

用数学归纳法证明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.
得证.

更多推荐

归纳法,数学

本文发布于:2023-05-27 02:43:25，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/285799.html