[理工] 102台大電機離散

[goldflower (金色小黃花)]

第六題

題目大致如下

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: 感覺妳這樣只有證明一個圖形的子圖一定有一個tree？
※ 編輯: goldflower (61.60.217.209), 02/09/2016 18:52:05
→ goldflower: 不懂@@  我是直接假設這個圖是Tree了
→ jerry031181: 這樣沒有證明到所有n>2的情形吧
→ goldflower: 嗯…可以再講詳細一點嗎？ 因為n的點的tree不管n等於
→ goldflower: 多少應該都符合邊數為n-1才對 照理說算是包括n>2的情
→ goldflower: 形 還是說只要再多補個證明樹的邊數=n-1就好呢？
→ jerry031181: 這樣的證明只能証n=k>2時你找到一個符合題目要求的樹
→ goldflower: 我知道問題出在哪了@@  感恩