[理工] 台大電機105 離散圖論

看板Grad-ProbAsk作者 (SonGohan)時間7年前 (2017/01/28 22:30), 編輯推噓8(8推 0噓 45→)
留言53則, 9人參與, 最新討論串1/1
http://i.imgur.com/Im4J04c.jpg
請問這題我是這麼想的： 因為degree數越少則leaf也會越少 所以degree為2的的樹leaf一定是最少的 且degree為2的樹leaf為 l <= n/2 + 1/2 那麼degree數不為2的leaf一定不會比degree數為2的leaf來得少 所以是l >= n/2 +1 不知道觀念是不是有錯 覺得怪怪的 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.135.102 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485613859.A.527.html
→
01/28 22:56, , 1F
degree為2的樹是指binary tree嗎？
01/28 22:56, 1F
→
01/28 23:01, , 2F
是說這題的degree不知道要用tree的還是graph的？
01/28 23:01, 2F
→
01/28 23:05, , 3F
小黃在講tree的分支度的時候好像都用m-ary
01/28 23:05, 3F
→
01/28 23:14, , 4F
yu大：對，是binary的那種degree（我覺得）
01/28 23:14, 4F
→
01/28 23:19, , 5F
那有degree為1的樹嗎？還是說那就是path不是tree了？
01/28 23:19, 5F
→
01/28 23:19, , 6F
1 ??
01/28 23:19, 6F
→
01/28 23:21, , 7F
degree為1的樹leaf永遠只有1個，感覺不是在考這個@@
01/28 23:21, 7F
→
01/28 23:22, , 8F
阿如果只有一個vertex也算樹，阿這樣就只有一個leaf...
01/28 23:22, 8F
→
01/28 23:23, , 9F
感覺我一直瘋狂誤會題目的意思...
01/28 23:23, 9F
→
01/28 23:23, , 10F
等高手解題XDD 不管是直觀還是以圖論公式推導我只想
01/28 23:23, 10F
→
01/28 23:24, , 11F
到這個數字是 最小leaf數
01/28 23:24, 11F
→
01/28 23:25, , 12F
不過題目說沒有degree為2的vertex，如果這邊的degree是
01/28 23:25, 12F
→
01/28 23:26, , 13F
指tree的分支度的話那應該原po的推論不太對？
01/28 23:26, 13F
→
01/28 23:27, , 14F
我剛剛也寫了一個很怪的答案，degree是用graph的定義
01/28 23:27, 14F
→
01/28 23:27, , 15F
然後leaf我當作是degree為1的點
01/28 23:27, 15F
→
01/28 23:28, , 16F
因為tree是connected，我先排除一下只有一個點的情況
01/28 23:28, 16F
→
01/28 23:28, , 17F
那麼就不會有degree為0的點
01/28 23:28, 17F
→
01/28 23:29, , 18F
令n(k)表示degree為k的node數
01/28 23:29, 18F
→
01/28 23:30, , 19F
n(1)+n(3)+n(4)+...+n(m)=n
01/28 23:30, 19F
→
01/28 23:30, , 20F
n(1)+3n(3)+4n(4)+...+mn(m)=2E=2n-2
01/28 23:30, 20F
→
01/28 23:31, , 21F
1式代入2式整理一下可以得到：
01/28 23:31, 21F
→
01/28 23:32, , 22F
n(1)=n(3)+2n(4)+...+(m-2)*n(m)+2
01/28 23:32, 22F
→
01/28 23:32, , 23F
如果n(3)=n(4)=...=n(m)=0的話，n1=2，也就是只有兩個
01/28 23:32, 23F
→
01/28 23:33, , 24F
點連在一起，此時有最少的leaf數為2，但還是很怪
01/28 23:33, 24F
→
01/28 23:37, , 25F
只有兩個點連在一起可以說這兩個點都是leaf嗎？怪怪的
01/28 23:37, 25F
推
01/28 23:49, , 26F
01/28 23:49, 26F
推
01/28 23:54, , 27F
感謝G大，我知道我問題在哪了
01/28 23:54, 27F
→
01/28 23:55, , 28F
大年初一就崩潰了...
01/28 23:55, 28F
推
01/29 00:03, , 29F
http://m.imgur.com/MKt9Cec 林立宇的做法但我覺得他
01/29 00:03, 29F
→
01/29 00:04, , 30F
算最上面那個點，不知道是不是我抄錯
01/29 00:04, 30F
→
01/29 00:05, , 31F
少算，剛沒打好
01/29 00:05, 31F
→
01/29 00:08, , 32F
也許最上面那個點他當root？
01/29 00:08, 32F
→
01/29 00:08, , 33F
不過我覺得林立宇的作法我比較難想的到，G大的作法跟我
01/29 00:08, 33F
→
01/29 00:09, , 34F
一開始的思路一樣，都是用degree跟邊的關係，不過我後
01/29 00:09, 34F
→
01/29 00:09, , 35F
來走錯方向了所以證不出來
01/29 00:09, 35F
→
01/29 00:18, , 36F
抱歉，請問一下，所以題目的degree並非m-ary tree的degre
01/29 00:18, 36F
→
01/29 00:18, , 37F
e而是圖論中定義的degree嗎？
01/29 00:18, 37F
→
01/29 00:21, , 38F
就這些作法看起來都是假設用graph的定義
01/29 00:21, 38F
→
01/29 00:21, , 39F
不過答案跟S大的一樣耶！
01/29 00:21, 39F
→
01/29 00:24, , 40F
可是想請問一下，該如何判斷題目的意思，因為題目提到是t
01/29 00:24, 40F
→
01/29 00:24, , 41F
ree了，會讓我以為不是用graph的degree定義去做，會讓我
01/29 00:24, 41F
→
01/29 00:24, , 42F
直接聯想到用tree的定義
01/29 00:24, 42F
→
01/29 00:26, , 43F
我其實是因為用tree的想不到要怎麼做才用graph的...
01/29 00:26, 43F
→
01/29 00:27, , 44F
看看其他人有什麼想法，我也想知道怎麼解決這個問題QQ
01/29 00:27, 44F
→
01/29 10:35, , 45F
感謝分享<(_ _)>
01/29 10:35, 45F
推
01/29 11:35, , 46F
他好像直接用i<=mn+1吧
01/29 11:35, 46F
→
01/29 11:35, , 47F
然後直接寫出i跟n的關係，m是最多幾個兒子，這裡是2
01/29 11:35, 47F
→
01/29 11:55, , 48F
喔不對，我看錯題目了
01/29 11:55, 48F
推
01/29 22:05, , 49F
我還以為是1，原來沒那麼簡單0.0.......
01/29 22:05, 49F
推
01/29 22:51, , 50F
想問一下G大的算式，第二行開始左邊也是度數和、右
01/29 22:51, 50F
→
01/29 22:52, , 51F
邊也是度數和，為何變成不等式啊
01/29 22:52, 51F
推
12/16 00:34, , 52F
105台大 樹
12/16 00:34, 52F
推
12/17 22:10, , 53F
107 台大 資工 解答
12/17 22:10, 53F
‣ 更多 SuperBu 的文章
文章代碼(AID): #1OZAiZKd (Grad-ProbAsk)