Complete Graph

Complete Graph

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

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

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

Complete Subgraph(Clique)

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

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

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

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

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

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

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

Maximal Clique Enumeration: Bron-Kerbosch Algorithm

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,稍微減少列舉的點。

Transitive Graph

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次。

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

Transitive Closure: Purdom's Algorithm

演算法

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

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

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

Transitive Closure: Warshall Algorithm

演算法

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

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²)。

UVa 280 12017

Regular Graph

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:兩個點的最遠距離。