[理工] 102 台大電機 離散 （tree）(更)

看板Grad-ProbAsk作者 (chen)時間7年前 (2017/01/19 21:06), 7年前編輯推噓6(6推 0噓 15→)
留言21則, 5人參與, 最新討論串1/1
http://i.imgur.com/CmHEk0n.jpg
不好意思 從鉛筆畫線以下的部分不懂 尤其（dk+1 -1）那邊 不知道為什麼要-1 還請大神了～ （我知道這題板上有人問過 但看不懂ＱＱ ------------ 更 附上我的做法 請大神們幫我看看這樣可不可以 http://i.imgur.com/BTgeOVI.jpg
http://i.imgur.com/bPF22qU.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.173.172.121 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484831174.A.FE8.html
推
01/19 21:31, , 1F
他講得好麻煩啊，反正也是數學歸納法,在n=k的時候會成立
01/19 21:31, 1F
→
01/19 21:32, , 2F
我們要證n=k+1也成立，根據題意n=k+1的deg合會比n=k還多
01/19 21:32, 2F
→
01/19 21:32, , 3F
2,所以我們就把一個點連到某個leaf,這樣degree就會剛好
01/19 21:32, 3F
→
01/19 21:32, , 4F
多2,且一棵樹的leaf一定存在，所以我們一定可以造得出這
01/19 21:32, 4F
→
01/19 21:33, , 5F
種sequence,所以n=k+1一定也成立，根據數學歸納法，就OK
01/19 21:33, 5F
→
01/19 21:34, , 6F
其實他講的跟我意思一樣啦，只是寫的比較文謅謅
01/19 21:34, 6F
假設拉一孤立點 連到leaf 這邊“邊數”的部分沒問題 但是序列的部分呢？ 拉過去連之前 leaf=d1=1, 序列(d1,d2....dn) 連之後 則孤立點的d=1 d1會變成2 ,序列（d,d1,d2....dn） 這樣後半部的序列...跟之前不一樣 因為d1變成2了 怎能保證新樹跟序列的關係符合？
推
01/19 21:41, , 7F
推T大講的淺顯易懂
01/19 21:41, 7F
推
01/19 21:42, , 8F
我是用另一種證法，不知道行不行。那n個正整數和是2
01/19 21:42, 8F
→
01/19 21:42, , 9F
n-2，令他們為n個點的degree，則邊就會有n-1個，n
01/19 21:42, 9F
→
01/19 21:42, , 10F
個點沒有孤立點，且有n-1個邊，一定存在連通且無迴
01/19 21:42, 10F
→
01/19 21:42, , 11F
圈的圖（tree)
01/19 21:42, 11F
推
01/19 22:50, , 12F
只看得懂G大的證法QQ
01/19 22:50, 12F
ＱＱ 我完全看不懂g大 求g大詳細版 ※ 編輯: cschenptt (218.173.172.121), 01/19/2017 23:43:56
→
01/19 23:54, , 13F
樹的定義是一個連通無迴圈的圖，而且E=V-1，如果那
01/19 23:54, 13F
→
01/19 23:54, , 14F
些正整數是degree的話，表示有n-1個邊（degree和為
01/19 23:54, 14F
→
01/19 23:54, , 15F
變數的兩倍），而且每個點的degree至少都有1，所以
01/19 23:54, 15F
→
01/19 23:54, , 16F
一定可以創造一個連通無迴圈的圖
01/19 23:54, 16F
→
01/20 02:01, , 17F
這天可以用數學歸納法證明
01/20 02:01, 17F
→
01/20 02:02, , 18F
不過我的證明囉唆了點
01/20 02:02, 18F
推
01/20 02:08, , 19F
01/20 02:08, 19F
感謝j大 此法大概就是t大的意思 但我有一樣的疑問sequence的部分不用管他嗎？ 我以為題意關於序列的部分是說 任意的序列d1,d2... 必存在一個數的度數序列 跟該序列相同 目前對於2n+2的部分沒問題了 是對於序列的部分有疑問 ※ 編輯: cschenptt (223.139.201.42), 01/20/2017 03:52:21 再更 我好像想通了，附上我的做法在文章末端 再麻煩大神們幫我看看對不對 ※ 編輯: cschenptt (223.139.201.42), 01/20/2017 04:40:13
推
01/20 09:29, , 20F
排列的部分基本上就沒關係了，反正你只要他是存在的就好
01/20 09:29, 20F
→
01/20 09:29, , 21F
了
01/20 09:29, 21F
‣ 更多 cschenptt 的文章
文章代碼(AID): #1OWBd6_e (Grad-ProbAsk)