[理工] 102 台大電機丙離散

看板Grad-ProbAsk作者goldflower (金色小黃花)時間10年前 (2016/02/09 17:45)推噓1(1推 0噓 7→)

留言8則, 3人參與討論串3/4 (看更多)

第六題題目大致如下 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 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.60.217.209 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455011150.A.100.html ※ 編輯: goldflower (61.60.217.209), 02/09/2016 17:46:44

推

markmushu

02/09 18:38, , 1^F

02/09 18:38, 1^F

※ 編輯: goldflower (61.60.217.209), 02/09/2016 18:52:05

→

goldflower

02/09 18:55, , 2^F

02/09 18:55, 2^F

→

jerry031181

02/09 19:12, , 3^F