Complete Graph

「完全圖」。任兩點都有一條邊。

連滿了邊，看起來相當堅固。

大家傾向討論無向圖，不討論有向圖。有向圖太複雜。

Complete Subgraph（Clique）

「完全子圖」、「團」。子圖，而且任兩點都有一條邊。

極大團Maximal Clique：無法再添加點的團。可能有許多個。

最大團Maximum Clique：點最多的團。可能有許多個。

所有團當中，最大者，就是最大團。所有極大團當中，最大者，就是最大團。

Minimal、Maximal是區域極值，Minimum、Maximum是全域極值。遣詞用字請小心！

尋找最大團，NP-complete問題，沒有快速的演算法。

窮舉極大團，從中找出最大團，不失為一個務實的方法。

Maximal Clique Enumeration

http://en.wikipedia.org/wiki/Bron–Kerbosch_algorithm

R: 目前的clique。
P: 可以增大目前clique的點集合。接下來要列舉的點。
　（與目前clique上所有點皆相鄰的點，構成的集合）
X: 可以增大目前clique的點集合，但是先前已經列舉過。用來避免重複列舉。

此演算法採用Backtracking。時間複雜度O(n⋅3ⁿᐟ³)。

選擇適當的pivot，讓各階段列舉的點都是最少，時間複雜度加速為O(3ⁿᐟ³)。

點的列舉順序採用degeneracy order，時間複雜度加速為O(d⋅n⋅3ᵈᐟ³)，d是原圖的degeneracy。

下面提供的實作是隨意選擇pivot，稍微減少列舉的點。

const int V = 30; bool adj[V][V]; // adjacency matrix struct Set {bool s[30]; int size;}; int maximal_clique = 0; Set intersect(Set S, int p) { for (int i=0; i<V; ++i) if (S.s[i] && !adj[p][i]) { S.s[i] = false; S.size--; } return S; } void backtrack(Set R, Set P , Set X) { if (P.size == 0) { if (X.size == 0) { maximal_clique++; for (int i=0; i<V; ++i) if (R[i]) cout << i; } return; } int pivot; for (pivot=0; pivot<V; ++pivot) if (P.s[pivot] || X.s[pivot]) break; // if (p == V) return; for (int i=0; i<V; ++i) if (P.s[i] && !adj[pivot][i]) { R.s[i] = true; R.size++; backtrack(R, intersect(P,i), intersect(X,i)); R.s[i] = false; R.size--; P.s[i] = false; P.size--; if (!X.s[i]) {X.s[i] = true; X.size++;} } } void Bron_Kerbosch() { // 刪除自環 for (int i=0; i<V; ++i) adj[i][i] = false; Set R, P, X; for (int i=0; i<V; ++i) R.s[i] = false; for (int i=0; i<V; ++i) P.s[i] = true; for (int i=0; i<V; ++i) X.s[i] = false; R.size = 0; P.size = V; X.size = 0; backtrack(R, P, X); } int adj[30]; // adjacency matrix int c = 0; // count maximal clique void backtrack(int P, int X) { if (P == 0 && X == 0) {c++; return;} int p = __builtin_ctz(P | X); int Q = P & ~adj[p]; while (Q) { int i = __builtin_ctz(Q); backtrack(P & adj[i], X & adj[i]); Q &= ~(1<<i); P &= ~(1<<i); X |= (1<<i); } } void Bron_Kerbosch() { // remove loop for (int i=0; i<N; ++i) adj[i] &= ~(1<<i); c = 0; backtrack((1<<N)-1, 0); cout << "極大團總共" << c << "個"; }

Transitive Graph

「遞移圖」。凡有路、必有邊。

連通關係的完全圖。

大家傾向討論有向圖，不討論無向圖。無向圖太簡單。

Transitive Subgraph

「遞移子圖」。子圖，而且凡有路、必有邊。

尋找最大遞移子圖，NP-complete問題，沒有快速的演算法。

列舉遞移子圖的演算法，我沒有研究。

Transitive Closure

「遞移閉包」其實是一種變換的概念，可以看做是一個函數。

一張圖的「遞移閉包」也是一張圖。記錄由一點能不能走到另一點。如果能走到，則兩點之間以邊相連。

「遞移閉包」。添加邊，連通關係保持相同，並且形成遞移圖。

每個點分別作為起點，實施遍歷。總共遍歷V次。時間複雜度O((V+E) ⋅ V) = O(V² + VE)，通常簡單寫成O(VE)。

Transitively Equivalent Graph

「遞移相等圖」。子圖，而且擁有相同的遞移閉包。

「遞移相等圖」。刪除邊，連通關係保持相同。

最小相等圖Minimum Equivalent Graph：保留盡量少的邊、刪除盡量多的邊。

尋找最小相等圖，NP-complete問題，沒有快速的演算法。

Transitive Reduction

「遞移縮減」。另外一張圖，恰好擁有相同的遞移閉包。

遞移縮減、遞移相等圖，名不符實、意義顛倒。古人腦殘。

最小遞移縮減Minimum Transitive Reduction：邊盡量少。

無向圖：生成森林。可能有許多種。總共遍歷1次。

有向圖：NP-hard。

有向無環圖：所有點對的最長路徑，保留長度是1的最長路徑（只有一條邊）。只有唯一一種。總共遍歷V次。

有向無環圖的情況下，遞移相等圖、遞移縮減，兩者恰好相等。這可能是古人將兩者搞混的原因。

演算法

強連通分量的遞移閉包是團，不必特地計算。收縮所有的強連通分量SCC，變成有向無環圖DAG。

觀察有向無環圖的拓樸順序，所有路徑都是從順序小的點走往順序大的點。一邊建立拓樸順序，一邊檢查是否連通，一邊添加邊以形成遞移閉包。

最多添加1+2+...+(K-1) = K(K-1)/2 = O(K²)條邊。K是新圖的點數量、原圖的SCC數量。時間複雜度O(V+E+K²)。

演算法

雖然時間複雜度較高，但是很有特色的演算法。

Dynamic Programming。取出第k點，分成兩種情況，遞迴分割問題。

tc(i, j, k) = tc(i, k, k-1) && tc(k, j, k-1) || tc(i, j, k-1)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^
              經過第k點                         沒有經過第k點

tc(i, j, k)：由i點能不能走到j點。中繼點只能是第0點到第k點。

時間複雜度O(V³)，空間複雜度O(V²)。

bool adj[9][9]; // adjacency matrix bool tc[9][9]; // transitive closure // 最短路徑演算法Floyd–Warshall Algorithm由此而來。 void warshall() { // DP表格初始化：拷貝原圖 for (int i=0; i<9; i++) for (int j=0; j<9; j++) tc[i][j] = adj[i][j]; // 依序計算各個子問題tc(i, j, k) for (int k=0; k<9; k++) for (int i=0; i<9; i++) for (int j=0; j<9; j++) if (tc[i][k] && tc[k][j]) tc[i][j] = true; }

UVa 280 12017

Regular Graph / Factor

無向圖當中，「Regular Graph」是每一點都連著一樣多的邊的圖；「Factor」是每一點都連著一樣多的邊的子圖。

簡而言之：每個點的邊數都一樣的圖、子圖。

我們可以在名稱開頭冠上數字、橫槓，明確呈現邊數。例如1-Regular Graph是每個點都連著一條邊的圖，2-Factor是每個點都連著兩條邊的子圖。

Complete Graph / Clique

無向圖當中，「完全圖Complete Graph」是所有兩點之間都有一條邊的圖；「團Clique」是所有兩點之間都有一條邊的子圖。

簡而言之：每個點的邊數都是V-1的圖、子圖。

Moore Graph

https://en.wikipedia.org/wiki/Moore_graph

Regular Graph，指定了度數degree、直徑diameter。

度數degree：一個點的邊數。

直徑diameter：兩個點的最遠距離。