第六題
題目大致如下
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時你找到一個符合題目要求的樹

我知道問題出在哪了@@ 感恩