有N个点,度数分别为d1,d2,d3.dN,并且其和为2N-2,证明存在度数分别为d1,d2...dN的树.

分类: 作业答案 • 2022-04-16 23:34:36

问题描述：

答

由握手定理，度数和等于边数的2倍，所以边数是N-1。
N个顶点，N－1条边刚好可以组成一棵树

答

接着ls的证明: 既然有度为N的数，那么子树的度就显然有2到N-1，所以d1到dN就在其中了。

答

证明构造任意一个具有n个结点v1,v2,…,vn的树,如果此时对任意i=1,2,…,n,有deg(vi)=di,本题结论成立,否则必存在deg(vi)dj,由于树是连通的,故结点vi,vj之间必有一条路vi,…,vk,vj,其中vj,是紧接着vk的结点,由于deg(vj...