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⋅3n/3)。
選擇適當的pivot,讓各階段列舉的點都是最少,時間複雜度加速為O(3n/3)。
點的列舉順序採用degeneracy order,時間複雜度加速為O(d⋅n⋅3d/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:兩個點的最遠距離。