[理工] 104電機丙 資結 10 16

[bochengchen (LFII)]

想請問
1.https://imgur.com/4V4IDX2.jpg
top-down的建法建出來的樹會跟bottom-up不一樣嗎？
這題的建樹過程是長怎樣呢？

2.https://imgur.com/vhCgoQx.jpg
想請問Ｂ選項 the cardinality of the largest clique 的意思！
是指最大的clique有幾個node嗎？

想請問Ｄ選項the number of paths in a directed acyclic graph can be exponential
 to the number of nodes in the graph

請問這個選項是否正確呢？我覺得這個選項應該是錯的，因為這個圖最多有n(n-1)條path

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 124.199.106.66 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578557068.A.324.html
推 jeremyyuan: 1. 不一樣 https://i.imgur.com/c0CzANJ.jpg
→ jeremyyuan: 2. 你算的是edge 他是問path
→ bochengchen: 請問J大為什麼path會是exponential等級呢?
推 mi981027: https://i.imgur.com/mlPS0T9.jpg
→ mi981027: https://i.imgur.com/hxYiiNQ.jpg
推 jeremyyuan: 我的方法跟樓上一樣 不過應該是2^(n-2) m大最後初值好
→ jeremyyuan: 像帶錯了
推 mi981027: 抱歉帶錯了>< a_2 = 1, a_n = 2^{n-2}沒錯 感謝j大
感謝Ｍ大Ｊ大的講解！謝謝你們！
※ 編輯: bochengchen (114.39.173.222 臺灣), 01/09/2020 23:49:35
推 twiddlebug:  https://i.imgur.com/JEXumPY.jpg
→ twiddlebug: 我畫這樣但不太確定
推 twiddlebug: 想想問16的E選項是怎麼解的><
→ cossetannie: https://i.imgur.com/mboO9yd.jpg