1.請問助教這題是否因為矩陣過大 所以用畫圖或觀察求解是最快？
2.請問幾個觀念 在找maximal clique的時候 一個graph的adjacency matrix是A 則是否可以求A^2, A^2中 non-zero entries和A重複的 則有可能是三個點之clique。同理 若要找四個點的clique 則求A^3中和A重複之entry做分析.... 請問助教這觀念是否正確？
3.請問三個點的完全圖clique個數是不是7個？？ 3個k1 3個k2 一個k3？？
感謝助教補充一下 第三點的疑問是因為下圖題目的定義 順便請問助教 下題的β是 independent set 的通用符號嘛？
8 則留言:
您好：
1.7個點硬做，因為這圖我覺得很小。
2.不，假設A中存在(a,b)、(a,d)，(b,g)、(d,g)，此時A^2中我們將看到(a,g)為2(代表從a走兩步到達g有兩條路，分別經b、d)，卻不存在與A中相同的entry(a不存在走兩步到b、d)，此時A^2和A未必有同樣的entry，如何分析？
3.我認為clique應該至少要兩點一邊。
定義：
A clique in an undirected graph G = (V, E) is a subset of the vertex set C ⊆ V, such that for every 「two vertices」 in C, there exists an edge connecting the two.
以上淺見..
sorry 我打錯 A^2應該是三點clique分析用 A^3是四點分析用... 以此類推 想法是 A中可到的點 則adjacency martrix對應entry不為0。 如果A^2 某(a,b)entry不為0且A對應之entry不為零 則代表a走一步可到b a走兩步也可到b 則這些點有可能是三點的clique。 以上個人淺見
對，但您不知道中間經過了那些點(acb、adb都是兩步到b)，對吧？
其實目前做到這種題目應該都還是硬幹比較快 今天突然想這個是以演算法觀點來想。以這題為例 7by7 clique最多也只有四點 以此題2356為例 則A^3 (2,6)entry不為零 且確認此entry在A也不為零 則只需看第二列和第六列中3~5行有哪些entry也不為零在做小測試即可
以上淺見
我是想說如果是4by4 loop free graph, 則也頂多算adjacency matrix到三次方 好像不一定會比硬幹慢
當然矩陣特大的時候還是硬幹快 只是單純想一下這題如何用點腦解 因為演算法有提到 不過這只是個人淺見 尚待助教及各位回復
1. 列出所有maximal cliques這個問題本身就是一個很難的問題, 且有些圖甚至可能會有指數多個maximal cliques, 因此很難有有效率的方法, 這種題目我也是覺得將圖畫出來用肉眼看比較快, 因為問題很難, 所以題目通常出的也不會很大
2. β那個符號不是很常用, 題目應該會給定義
請問助教graph k3的clique個數是？
K3的maximal clique就只有一個, 就是K3
張貼留言