[理工] [離散] 補圖跟clique

看板Grad-ProbAsk作者 (Firefighter)時間14年前 (2012/02/17 21:40), 編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 最新討論串1/1
補圖我看小黃的書 還是看不懂= = 是說只要A原本有的邊 B就不能出現嗎 http://ppt.cc/PcIC clique只知道是最大的子圖 但是看到題目還是不知道該怎麼辦 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 42.72.160.41
→
02/17 21:44, , 1F
補圖就是完全圖的邊扣掉原來圖的邊
02/17 21:44, 1F
→
02/17 21:48, , 2F
clique是圖裡面的最大完全子圖
02/17 21:48, 2F
→
02/17 21:49, , 3F
而在演算法裡面即是用補圖找出clique(屬於NPC)
02/17 21:49, 3F
→
02/17 22:07, , 4F
3Q...補圖了解了~但另一個還是..
02/17 22:07, 4F
→
02/17 22:45, , 5F
例如說這個clique是3 要從哪邊看 http://ppt.cc/xvND
02/17 22:45, 5F
推
02/17 23:04, , 6F
clique是complete subgraph 題目不一定要maximal的
02/17 23:04, 6F
→
02/17 23:05, , 7F
圖裡面就兩個K3
02/17 23:05, 7F
→
02/17 23:24, , 8F
感謝 原來我原本想太複雜了
02/17 23:24, 8F
‣ 更多 dunkjames 的文章
文章代碼(AID): #1FFbYp-F (Grad-ProbAsk)