第六题
题目大致如下
n个点,其degree分别为d1,d2,...,dn; 其中n>2, di>0
证明在sigma(di)=2n-2下,存在一树T其degree分布为d0...dn
目前看到的算法是用数学归纳法
但是我想问问看我这种证法是否可行 想知道逻辑上有没有错误@@
证法如下:
假设不具T使其degree分布如要求
则原题相当于:存在d1,...,dn 使得 if sigma(di)=2n-2=>不存在T使其符合要求
逆否命题:for all T符合要求=> sigma(di)!=2n-2
又T的边数必为n-1
则degree总和必为2n-2
与上述命题产生矛盾
则必定存在T满足此种degree分布
不知道以上证法有没有逻辑错误或是不完备的地方呢?
感恩各位大大解惑了QQ

感觉妳这样只有证明一个图形的子图一定有一个tree？

不懂@@ 我是直接假设这个图是Tree了

这样没有证明到所有n>2的情形吧

嗯…可以再讲详细一点吗？ 因为n的点的tree不管n等于多少应该都符合边数为n-1才对 照理说算是包括n>2的情形 还是说只要再多补个证明树的边数=n-1就好呢？

这样的证明只能証n=k>2时你找到一个符合题目要求的树

我知道问题出在哪了@@ 感恩