[理工] 104 台大電機丙 選擇第16題

看板Grad-ProbAsk作者 (joywilliamjoy)時間5年前 (2020/12/13 18:17), 編輯推噓0(0推 0噓 10→)
留言10則, 1人參與, 最新討論串1/1
https://i.imgur.com/k5164Bu.jpg
16題 目前確定的是A選項是錯的，蝴蝶結 B選項直接上網查是對的，八面體是8個三角型組成的那個 證明方式：假設largest clique=4，隨便選四個點中其中一個點V1，會有一個對角不是ad jacent C錯，跟A一樣的圖形加方向 D不確定到底該不該選 題目描述的很籠統 沒有給指數限制，那有邊有點就一定能夠滿足題目敘述，但感覺不是要考這個... E的話不太會證，尤其是不確定若是1個點的clique的情況怎麼討論 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.127.136 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607854653.A.91E.html
→
12/16 13:32, , 1F
(D) DAG任兩點間至多一條path,所以#path應當正比於#
12/16 13:32, 1F
→
12/16 13:32, , 2F
node，非指數增長
12/16 13:32, 2F
→
12/16 13:32, , 3F
(E) 設G之minimum clique partition 為
12/16 13:32, 3F
→
12/16 13:32, , 4F
P = {C_1,...,C_k},其中 |C_i|<=|C_ j|, for all
12/16 13:32, 4F
→
12/16 13:32, , 5F
1 <= i < j <= k,因為G上的每個node至多連出e條邊，
12/16 13:32, 5F
→
12/16 13:32, , 6F
所以該node與其連接的e個node，
12/16 13:32, 6F
→
12/16 13:32, , 7F
共e+1個點，最大只會形成K_(e+1)。
12/16 13:32, 7F
→
12/16 13:32, , 8F
n=|V|=|C_1 U ... U C_k|<=|C_1|+...+|C_k|
12/16 13:32, 8F
→
12/16 13:32, , 9F
<=k|C_k|=k(e+1)
12/16 13:32, 9F
→
12/16 13:32, , 10F
=> k >= n/(e+1)
12/16 13:32, 10F
‣ 更多 joywilliamjo 的文章
文章代碼(AID): #1VrUezaU (Grad-ProbAsk)