证明构造任意一个具有n个结点v1,v2,…,vn的树,如果此时对任意i=1,2,…,n,有deg(vi)=di,本题结论成立,否则必存在deg(vi)dj,由于树是连通的,故结点vi,vj之间必有一条路vi,…,vk,vj,其中vj,是紧接着vk的结点,由于deg(vj)>dj=1,,故必存在vl≠vk,使得(vj,vl)是树的一条边,此时删去边(vj,vl),增添边(vi,vl),所得图仍是树,此时deg(vi)增加1,而deg(vj)减少1,经过若干次这种做法,即得满足条件的树.
有N个点,度数分别为d1,d2,d3.dN,并且其和为2N-2,证明存在度数分别为d1,d2...dN的树.
3个回答
相关问题
-
∵dn= 3+(-1)n/2 ,∴an=d1+d2+d3+…+d2n= 3×2n/2 =3n 这个an怎么求出来的
-
若m不等于n,两个等差数列m,a1,a2,n与m,b1,b2,b3,n,的公差分别为d1,d2,d1/d2的值为
-
Y=X^2-4NX+4N^2+3N-61,证明顶点共线,顶点到X轴距离D1+D2+.+DN,求和
-
设P为可逆矩阵,且PTAP=diag(d1,d2,...,dn),问di(i=1,2,...,n)是否为A的特征值?并说
-
化简{[2*1d+3*2d+4*3d+……+n(n-1)d]+n(n-1)/2*d*a}/[(n-1)n*d/2]
-
（2014•齐齐哈尔三模）若m≠n，两个等差数列m，a1，a2，n与m，b1，b2，b3，n的公差分别为d1和d2，则d
-
若m不等于n,两个等差数列m,a1,a2,n与m,b1,b2,b3,n的公差为d1和d2,则d1/d2的值为
-
1.设n是正整数,d1、d2、d3、d4是n的4个连续最小的正整数约数（d1、d2、d3、d4）,若n＝d1、d2、d3
-
证明:diag[d1,d2,...,dn]与diag[di1,di2,...,din]相似,其中i1,i2,...in是
-
线性代数这个Dn和D(n-1)代表什么?