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

[dunkjames (Firefighter)]

補圖我看小黃的書 還是看不懂= =

是說只要A原本有的邊 B就不能出現嗎
http://ppt.cc/PcIC



clique只知道是最大的子圖 但是看到題目還是不知道該怎麼辦


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 42.72.160.41
→ love5566188:補圖就是完全圖的邊扣掉原來圖的邊
→ love5566188:clique是圖裡面的最大完全子圖
→ love5566188:而在演算法裡面即是用補圖找出clique(屬於NPC)
→ dunkjames:3Q...補圖了解了~但另一個還是..
→ dunkjames:例如說這個clique是3 要從哪邊看 http://ppt.cc/xvND
推 mapleleaf052:clique是complete subgraph 題目不一定要maximal的
→ mapleleaf052:圖裡面就兩個K3
→ dunkjames:感謝 原來我原本想太複雜了