[理工] 離散 有關(maximal)clique與independent set

看板Grad-ProbAsk作者 (silver2024)時間10年前 (2014/02/10 11:43), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串1/1
http://i.imgur.com/AFBbYcg.jpg
如圖所示， 有關clique的定義不是很了解... 第二列我圈起來的一個點 是maximal clique還是只是clique? 另外independent set的定義也是不太確定... 第四列我圈起來的一個點 是maximal independent set還是independent set? 麻煩各位大大幫我釐清觀念QQ 感謝!!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.218.198.165 ※ 編輯: silver2024 來自: 180.218.198.165 (02/10 11:47)
推
02/10 11:54, , 1F
1.clique 2. independent set
02/10 11:54, 1F
→
02/10 11:54, , 2F
maximal 的觀念是一樣的，必須是clique，且不能是某個
02/10 11:54, 2F
→
02/10 11:54, , 3F
clique 的子集
02/10 11:54, 3F
→
02/10 11:56, , 4F
我後來自己想了一下，一個點的應該算只是clique
02/10 11:56, 4F
→
02/10 11:57, , 5F
原來如此，感謝A大講解!
02/10 11:57, 5F
推
02/10 19:33, , 6F
independent set 就 紅點們之間的連邊 沒有同一點共連
02/10 19:33, 6F
‣ 更多 silver2024 的文章
文章代碼(AID): #1I-4hFND (Grad-ProbAsk)