[理工] 104台大電機 資演

[joeboy (揪立)]

http://i.imgur.com/MwWDra5.jpg
第六題爬文一下
有人說可以用DFS解決
為什麼呢QQ

http://i.imgur.com/pmEy7C7.jpg
這個A選項是在說明什麼呢，看不太懂想問蝦米QQ

http://i.imgur.com/ZZNtwCZ.jpg
藍筆的三個選項
其中16D為什麼是exponential呀？應該不可能那麼多吧？
剩下兩個有勞大大幫忙解答，謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.91.184
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484848230.A.C31.html
推 A4P8T6X9: 1，拓樸排序
推 Transfat: 我也有疑問QQ
推 yorunohoshi: 16. (D) 應該是錯的 用DFS就可解
→ yorunohoshi: goo.gl/jbEave
→ yorunohoshi: 16.(E) 可以參考這個 goo.gl/LnvEPY
推 FRAXIS: 15 一個 tree 第 k 層有 k + 2 個子節點
→ FRAXIS: 這很明顯的比二元樹要多很多節點 所以節點數不是O(2^n)
推 FRAXIS: 15 如果有 n = 2^h - 1 個節點 那麼 minimum tree height
→ FRAXIS: 的樹只有一種可能（完全平衡） 但是 n 節點的二元樹有指數
→ FRAXIS: 種  所以機率應該非常小
→ FRAXIS: 16 D 如果 DAG 是一串菱形 起點到終點就有指數種路徑
→ FRAXIS: 16 E 最大 degree d -> 最大 clique size d + 1
→ FRAXIS: 因為最大 clique size 是 d+1 要 cover n 點就要 n/(d+1)
→ FRAXIS: 個 clique