[理工]清大103計科

看板Grad-ProbAsk作者 (馬吉叫我辦的)時間9年前 (2016/12/30 14:20), 9年前編輯推噓12(12推 0噓 17→)
留言29則, 9人參與, 最新討論串1/1
請問第二題要如何證明? http://i.imgur.com/V8Y01aU.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.218.65.53 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483078836.A.3E5.html ※ 編輯: h9638512 (49.218.65.53), 12/30/2016 14:29:25 ※ 編輯: h9638512 (49.218.65.53), 12/30/2016 14:29:57
推
12/30 15:10, , 1F
以該點為root，則至少有k個child tree，每個tree至
12/30 15:10, 1F
→
12/30 15:10, , 2F
少一個leaf，所以以該點為root就會至少k leaves
12/30 15:10, 2F
推
12/30 15:16, , 3F
可是如果該點不在Root, 這樣只會有k-1個child tree, 只
12/30 15:16, 3F
→
12/30 15:16, , 4F
能說有k-1個leaf, 還有一個躲在哪裡
12/30 15:16, 4F
推
12/30 15:25, , 5F
我想會不會是把parent當作是其中一個leave
12/30 15:25, 5F
推
12/30 15:30, , 6F
換個角度看其實Root也是個leaf.. 不過這樣就不太是個tre
12/30 15:30, 6F
→
12/30 15:30, , 7F
e, 頂多叫個graph
12/30 15:30, 7F
推
12/30 15:32, , 8F
tree的degree跟graph的degree定義不同哦～
12/30 15:32, 8F
推
12/30 15:32, , 9F
是啊 好像有點怪怪的
12/30 15:32, 9F
→
12/30 15:33, , 10F
tree中node之degree=k 就是指那個node有k個子node
12/30 15:33, 10F
推
12/30 15:37, , 11F
我怎麼記得我寫過一題說leaf的degree算是1, 我找看看
12/30 15:37, 11F
→
12/30 15:40, , 12F
12/30 15:40, 12F
→
12/30 15:42, , 13F
T2 第一行 k+1個葉子
12/30 15:42, 13F
→
12/30 15:44, , 14F
其實應該再寫一條當T1不是k的情況 只是跟k+1 寫法差
12/30 15:44, 14F
→
12/30 15:44, , 15F
不多
12/30 15:44, 15F
→
12/30 15:57, , 16F
題目這樣說就是把degree當作child數了吧，不然三個n
12/30 15:57, 16F
→
12/30 15:57, , 17F
ode的skew tree就變成反例
12/30 15:57, 17F
→
12/30 15:58, , 18F
有acyclic 就可以稱為tree了，不用太在意root被設為
12/30 15:58, 18F
→
12/30 15:58, , 19F
哪個點
12/30 15:58, 19F
推
12/30 20:21, , 20F
12/30 20:21, 20F
→
12/30 20:21, , 21F
樹的Degree 就是節點的子樹個數
12/30 20:21, 21F
推
12/30 22:35, , 22F
12/30 22:35, 22F
→
12/30 22:36, , 23F
我是這樣想的只是不知道夠不夠嚴謹就是了
12/30 22:36, 23F
推
12/30 22:38, , 24F
更正 第一行應為 =i之node"數"
12/30 22:38, 24F
推
12/30 22:52, , 25F
感覺也是可以，也許加上n(k+1)+...+n(m)更好？
12/30 22:52, 25F
→
12/30 22:53, , 26F
因為題目沒有說k就是最大的degree，當然最後結果也是對
12/30 22:53, 26F
→
12/30 22:55, , 27F
我覺得這個想法蠻嚴謹的就是了XD
12/30 22:55, 27F
推
12/30 22:57, , 28F
感謝yu大提醒 漏了更大degree的點了哈哈
12/30 22:57, 28F
→
12/31 17:09, , 29F
感謝a大 解法很好懂><
12/31 17:09, 29F
‣ 更多 h9638512 的文章
文章代碼(AID): #1OPVoqFb (Grad-ProbAsk)