[理工] 105台大電機丙 離散 tree

看板Grad-ProbAsk作者 (一一)時間8年前 (2018/02/04 17:20), 8年前編輯推噓3(3推 0噓 7→)
留言10則, 4人參與, 6年前最新討論串1/1
https://i.imgur.com/wssAmya.jpg
想請問這題是怎麼推得的 上課的時候老師好像只有給答案 但是我不確定怎麼推出來的 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.13.50.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1517736033.A.29D.html
推
02/04 17:47, 8年前 , 1F
v2+v0=n 2*v2=v2+v0-1 v2=v0-1 2v0-1=n v0=(n+1)/2
02/04 17:47, 1F
推
02/04 17:50, 8年前 , 2F
假設degree1為l 剩下為n-l全部的degree總和至少為l+3(n-l)
02/04 17:50, 2F
→
02/04 17:50, 8年前 , 3F
（因為剩下的node 的degree至少為3）
02/04 17:50, 3F
→
02/04 17:52, 8年前 , 4F
然後上述會小於真正的degree加總 也就是小於2e=2（v-1) 然
02/04 17:52, 4F
→
02/04 17:52, 8年前 , 5F
後就可以推出來了
02/04 17:52, 5F
→
02/04 17:56, 8年前 , 6F
換一種 E=(3*v3+v1)/2=v3+v1-1 v3=v1-2 n=v1+v3=2*v1-2
02/04 17:56, 6F
→
02/04 17:56, 8年前 , 7F
v1=n/2+1
02/04 17:56, 7F
原來如此 太感謝了！ ※ 編輯: qaswed101 (101.13.50.203), 02/04/2018 18:03:57
推
02/06 09:51, 7年前 , 8F
可是這題他沒有說是binary tree欸，這樣解法有瑕疵吧
02/06 09:51, 8F
→
12/13 12:17, 6年前 , 9F
binary tree一定是最少的情況 可以隨意想像一下非二元跟二元
12/13 12:17, 9F
→
12/13 12:18, 6年前 , 10F
的情況 在知道最佳解必是二元後由上述方法推得
12/13 12:18, 10F
‣ 更多 qaswed101 的文章
文章代碼(AID): #1QTj1XAT (Grad-ProbAsk)