→ yupog2003: degree為2的樹是指binary tree嗎？ 01/28 22:56
→ yupog2003: 是說這題的degree不知道要用tree的還是graph的？ 01/28 23:01
→ gouya: 小黃在講tree的分支度的時候好像都用m-ary 01/28 23:05
→ SuperBu: yu大：對，是binary的那種degree（我覺得） 01/28 23:14
→ yupog2003: 那有degree為1的樹嗎？還是說那就是path不是tree了？ 01/28 23:19
→ ken52011219: 1 ?? 01/28 23:19
→ yupog2003: degree為1的樹leaf永遠只有1個，感覺不是在考這個@@ 01/28 23:21
→ yupog2003: 阿如果只有一個vertex也算樹，阿這樣就只有一個leaf... 01/28 23:22
→ yupog2003: 感覺我一直瘋狂誤會題目的意思... 01/28 23:23
→ ken52011219: 等高手解題XDD 不管是直觀還是以圖論公式推導我只想 01/28 23:23
→ ken52011219: 到這個數字是 最小leaf數 01/28 23:24
→ yupog2003: 不過題目說沒有degree為2的vertex，如果這邊的degree是 01/28 23:25
→ yupog2003: 指tree的分支度的話那應該原po的推論不太對？ 01/28 23:26
→ yupog2003: 我剛剛也寫了一個很怪的答案，degree是用graph的定義 01/28 23:27
→ yupog2003: 然後leaf我當作是degree為1的點 01/28 23:27
→ yupog2003: 因為tree是connected，我先排除一下只有一個點的情況 01/28 23:28
→ yupog2003: 那麼就不會有degree為0的點 01/28 23:28
→ yupog2003: 令n(k)表示degree為k的node數 01/28 23:29
→ yupog2003: n(1)+n(3)+n(4)+...+n(m)=n 01/28 23:30
→ yupog2003: n(1)+3n(3)+4n(4)+...+mn(m)=2E=2n-2 01/28 23:30
→ yupog2003: 1式代入2式整理一下可以得到： 01/28 23:31
→ yupog2003: n(1)=n(3)+2n(4)+...+(m-2)*n(m)+2 01/28 23:32
→ yupog2003: 如果n(3)=n(4)=...=n(m)=0的話，n1=2，也就是只有兩個 01/28 23:32
→ yupog2003: 點連在一起，此時有最少的leaf數為2，但還是很怪 01/28 23:33
→ yupog2003: 只有兩個點連在一起可以說這兩個點都是leaf嗎？怪怪的 01/28 23:37
推 yupog2003: 感謝G大，我知道我問題在哪了 01/28 23:54
→ yupog2003: 大年初一就崩潰了... 01/28 23:55
→ Gene0515: 算最上面那個點，不知道是不是我抄錯 01/29 00:04
→ Gene0515: 少算，剛沒打好 01/29 00:05
→ yupog2003: 也許最上面那個點他當root？ 01/29 00:08
→ yupog2003: 不過我覺得林立宇的作法我比較難想的到，G大的作法跟我 01/29 00:08
→ yupog2003: 一開始的思路一樣，都是用degree跟邊的關係，不過我後 01/29 00:09
→ yupog2003: 來走錯方向了所以證不出來 01/29 00:09
→ SuperBu: 抱歉，請問一下，所以題目的degree並非m-ary tree的degre 01/29 00:18
→ SuperBu: e而是圖論中定義的degree嗎？ 01/29 00:18
→ yupog2003: 就這些作法看起來都是假設用graph的定義 01/29 00:21
→ yupog2003: 不過答案跟S大的一樣耶！ 01/29 00:21
→ SuperBu: 可是想請問一下，該如何判斷題目的意思，因為題目提到是t 01/29 00:24
→ SuperBu: ree了，會讓我以為不是用graph的degree定義去做，會讓我 01/29 00:24
→ SuperBu: 直接聯想到用tree的定義 01/29 00:24
→ yupog2003: 我其實是因為用tree的想不到要怎麼做才用graph的... 01/29 00:26
→ yupog2003: 看看其他人有什麼想法，我也想知道怎麼解決這個問題QQ 01/29 00:27
→ ken52011219: 感謝分享<(_ _)> 01/29 10:35
推 joeboy: 他好像直接用i<=mn+1吧 01/29 11:35
→ joeboy: 然後直接寫出i跟n的關係，m是最多幾個兒子，這裡是2 01/29 11:35
→ joeboy: 喔不對，我看錯題目了 01/29 11:55
推 angel861047: 我還以為是1，原來沒那麼簡單0.0....... 01/29 22:05
推 angel861047: 想問一下G大的算式，第二行開始左邊也是度數和、右 01/29 22:51
→ angel861047: 邊也是度數和，為何變成不等式啊 01/29 22:52
推 clonsey1314: 105台大 樹 12/16 00:34
推 sarsman: 107 台大 資工 解答 12/17 22:10