Graph資料結構(Under Construction!)

Incidence Matrix

先前介紹了三種平易近人的資料結構:edge list、adjacency matrix、adjacency lists。接著再介紹兩個罕見的資料結構,適合已經熟悉圖論、想要深入鑽研的人。

點有編號,邊有編號。矩陣的第一個維度代表點,第二個維度代表邊,元素(0,1)記錄著第0點與第1邊是否碰觸。

無向圖當中,點碰觸邊就標上1,否則標上0。有向圖當中,點碰觸出邊就標上+1,點碰觸入邊就標上-1,否則標上0。

Incidence Matrix的缺點是無法記錄自己連向自己的邊。

Incidence Matrix可以看成是Bipartite Graph。

Laplacian Matrix

L = D - A。L D A分別代表Laplacian Matrix、Degree Matrix、Adjacency Matrix。

https://www.quora.com/Graph-Theory-Whats-the-intuition-behind-a-Laplacian-matrix
https://en.wikipedia.org/wiki/Kirchhoff's_theorem
laplacian = 流入 - 流出
圖上每一條邊看成擴散箭頭 <---> 流到兩邊
以邊當做主角
Lij = -1     流入0、往左右各流出1/2(但是只取j方向)
Lii = d(i)   流入d/2、流出0
然後乘以2變整數,比較好算

Algebraic Graph Theory(Under Construction!)

Neighbor

Aᵀx。x向量的元素,起點是1,其餘點是0。

矩陣相乘需時O(N³)。亦得採用更快的矩陣相乘演算法,例如Strassen's Algorithm。

http://www.lab2.kuis.kyoto-u.ac.jp/keisan-genkai/reports/2006/nhc/Uri_Zwick.pdf
http://www.cs.tau.ac.il/~zwick/Adv-Alg-2015/Matrix-Graph-Algorithms.pdf

Transitive Closure

圖上每一個點,可以走到圖上哪些點。

根據路徑長度分類。簡化成圖上每一個點,走零條、走一條、走兩條、……、走無限多條邊,到達圖上哪些點。

一張圖只有V個點。從一點走到另一點,最多走過V-1條邊。簡化成圖上每一個點,走一條、走兩條、……、走V-1條邊,到達圖上哪些點。

矩陣元素是Boolean,元素加法是OR運算,元素乘法是AND運算!

T = I + A + A² + ...。矩陣0次方、1次方、2次方、……、V-1次方通通OR起來。

A₀ = I、A₁ = A₀ + (A₀ ⋅ A)、A₂ = A₁ + (A₁ ⋅ A)、……。由於OR的性質,可以改成一邊相加、一邊相乘,結果仍正確。

Strassen's Algorithm的過程包含了實數減法,在此對應到OR反元素,然而OR並沒有反元素,所以不能直接套用Strassen's Algorithm。

不過我們還是可以運用矩陣乘法解題。方法很簡單:直接用實數下去算,計算完畢之後,把零當做false,非零的數字當做是true就可以了。

一般的圖,仿效Strassen's Algorithm的手法,稍微加速。

1. G均分成四份:左上為A,右上為B,左下為C,右下為D。
2. 遞迴求出D*。
3. 令E = A + BD*C,並且遞迴求出E*。
4. G*均分成四份,左上會是E*,右上會是E*BD*,左下會是D*CE*,右下會是D* + D*CE*BD*。

Transitive Closure of Level Graph

分層圖,只有層與層之間才有邊,導致矩陣許多區域是零,可再稍微加速。例如恰好是前中後三層:

1. G均分成九份:上為A,右為B,其餘皆為0。
2. G*均分成九份:上仍為A,右仍為B,右上為AB,
   左上、中、右下為單位矩陣I,其餘皆為0。

Transitive Closure of DAG

http://www.student.cs.uwaterloo.ca/~cs466/Old_courses/F08/transitiveClosure.pdf

環上的點相互連通,沒必要認真找Transitive Closure。因此可以預先找到強連通分量SCC,收縮圖上所有環,變成有向無環圖DAG,再來找Transitive Closure。

有向無環圖,求出拓樸順序。矩陣呈現可愛的上三角矩陣。

拓樸順序從中切開,成為前後兩段。所有點分成前後兩群。後群到前群,顯然沒有邊。矩陣四等分,左下角為零。

1. G均分成四份:左上為A,右上為T,左下為0,右下為B。
2. 遞迴求出A*。遞迴求出B*。
3. G*均分成四份:左上是A*,右上是A*TB*,左下是0,右下是B*。

Strongly Connected Component

矩陣元素是Boolean,元素加法是OR運算,元素乘法是AND運算。

C = I ⋁ A ⋁ A² + ...。從C ⋀ Cᵀ當中找到true。

因為很難算,所以矩陣元素改成實數。

D = I + A + A² + ... = (I - A)⁻¹。從D + Dᵀ當中找到大於0的元素。

為了收斂,添加一個倍率α,讓α < 1。

D = I + (αA) + (αA)² + ... = (I - αA)⁻¹。

Shortest Path

矩陣元素是實數,元素加法是min運算,元素乘法是加法運算!

不過min運算沒有反元素,所以必須用特殊的方式避開反元素的計算,例如Seidel's Algorithm。

http://www.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf
http://theory.stanford.edu/~virgi/cs367/

Matching

Tutte Matrix

Tij = { xij    if i < j and e(i,j) exist
      { -xji   if i > j and e(i,j) exist
      { 0      otherwise

rank(T):最大匹配的邊數的兩倍。

det(T):完美匹配是否存在。

Spectral Graph Theory(Under Construction!)

Graph Spectrum

http://www.cs.yale.edu/homes/spielman/

Neighbor

L = D - A
x*Ax = x* (Ax)
Ax --> vertex label 複製到隔壁並累計
x* Ax --> 所有點對相乘總和
Lx    --> vertex label 分散到隔壁並累計
x* Lx --> 所有點對差平方總和

Spanning Tree

Matrix Tree Theorem

incidence = 一個方向的一次微分
laplacian = sum 一個方向的二次微分
於是可以寫成二次型????  剛好是gradient norm平方???
(每一處的gradient length總和的最小值 => 每一處laplace = 0)
特徵值的零的數量是連通成分數量
特徵值的前n-1大的乘積是生成樹數量,簡單的算法是minor的det

Clique

http://web.stanford.edu/class/ee378b/lect-7.pdf
matrix multiplication of adjacency matrix ---> transitive
當clique足夠大,此時矩陣的無限大次方,很容易在clique裡面跑來跑去
(degree總和特別多?  不巧遇到degree很多的點怎辦? 像是星星圖那種的)
找出eigenvalue絕對值最大的那一個eigenvector
當中絕對值比較大的那幾個元素,差不多是個clique

Random Walk

UVa 12695

Graph Property(Under Construction!)

Reachability

把一張圖想像成道路地圖,把圖上的點想像成地點,把圖上的邊想像成道路。現在我們在意的是:由某一點開始,走過N條道路後,可以到達哪些點?

走過零條道路,原地不動。走過一條道路,跑到隔壁鄰居了。

走過N條道路,各位應該馬上想試試看Graph Traversal──可是遇到重複地點就沒轍了。Graph Traversal只能拜訪一個點一次。

如果i點可以走到某一個j點、這個j點又可以走到k點,那麼就可以由i點走到k點,剛好兩條道路。

窮舉所有可能的j點,就可以判斷i點走到k點,是否剛好兩條道路!

寫成數學式子:

r₂(i, k) = ( r₁(i, 0) AND r₁(0, k) ) OR
           ( r₁(i, 1) AND r₁(1, k) ) OR
           ( r₁(i, 2) AND r₁(2, k) ) OR
                       :
           ( r₁(i, V-1) AND r₁(V-1, k) )

r₂(i, k):i點走到k點,是否剛好2條道路。

i點到j點,j點到k點,窮舉j點──宛如矩陣乘法。

元素加法改成OR運算,元素乘法改成AND運算,adjacency matrix自己乘上自己,矩陣相乘的結果,就是走兩條道路的情況了!

兩條加一條就是三條,三條加一條就是四條。逐次加一條道路,慢慢累積,最後就得到走N條道路的情況。

同理,走兩條道路的矩陣,再乘上一次原圖的adjacency matrix,就是走三條道路的矩陣。走N條道路的矩陣,就是原圖的adjacency matrix的N次方。

矩陣的N次方,採用分治法,只需O(logN)次矩陣乘法。

另外這個方法也可以用來計算從一點走到另外一點,走了N步之後總共有幾種走法。各位可以想想看。

UVa 10681

Similarity(Graph Kernel)

相似程度。兩張圖的距離、差異。

https://www.zhihu.com/question/57269332
http://www.raetschlab.org/lectures/amsa/5-borgwardt-graph.pdf
http://www.stat.purdue.edu/~vishy/talks/Graphs.pdf

Centrality

寬闊程度。

http://en.wikipedia.org/wiki/Centrality
http://en.wikipedia.org/wiki/Betweenness_centrality

Connectivity

連結強度。

http://en.wikipedia.org/wiki/Algebraic_connectivity
http://www.lix.polytechnique.fr/~schwander/resources/mig/slides/pati.pdf

Graph Isomorphism(Under Construction!)

Graph Isomorphism

http://en.wikipedia.org/wiki/Graph_canonization
http://en.wikipedia.org/wiki/Graph_isomorphism
http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem
http://en.wikipedia.org/wiki/Maximum_common_subgraph_isomorphism_problem
http://en.wikipedia.org/wiki/Graph_sandwich_problem

Graph Enumeration

http://en.wikipedia.org/wiki/Graph_enumeration

Tree Isomorphism

http://www.cs.upc.edu/~valiente/graph-00-01-c.pdf
use radix sort O(nd) = O(#son + #grandson) = O(n + n) = O(n)

http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Solved_special_cases

subtree isomorphism問題可以用DP+matching來解決
https://code.google.com/codejam/contest/dashboard?c=32005#s=a&a=3
http://www.lsi.upc.edu/~valiente/riga-tre.pdf
為什麼對?
https://github.com/juanplopes/icpc/blob/master/uva/12489.cpp

UVa 10729 10904 12489 ICPC 2935

Tree Enumeration

http://mathworld.wolfram.com/LabeledTree.html
http://en.wikipedia.org/wiki/Prüfer_sequence
http://www.matrix67.com/blog/archives/682

Prüfer Code:把一棵樹轉換成獨特的編號。

UVa 10843

Tree Distance(Tree Similarity)

兩棵樹的距離:

Edit Distance
Rotation Distance
Chain Rotation Distance

Graph Partitioning(Under Construction!)

Graph Partitioning

https://people.eecs.berkeley.edu/~luca/expanders2016/

Separator

規定兩邊的點數呈特定比例,就是NP-complete問題。

http://www.cs.cmu.edu/~guyb/realworld/slidesF07/separators1.pdf

Expander

Definition 3.1
A graph G = (V,E) is called an (n, d, c)-expander
if it has n vertices, the maximum degree is d,
and for all S 屬於 V with |S| <= |V|/2,
we have |N(S)| >= c|S| and c is called the expansion of G.
http://en.wikipedia.org/wiki/Expander_graph
https://en.wikipedia.org/wiki/Zig-zag_product

Graph Sampling(Under Construction!)

Graph Sampling

Graph Sparsification

Spanner

http://tmtacm.blogspot.tw/2016/01/2.html

Graph Stream(Under Construction!)

Graph Stream

《Graph Stream Algorithms: A Survey》

Graph Sketch

《Graph Sketches: Sparsification, Spanners, and Subgraphs》

Geometric Graph Theory(Under Construction!)

Graph Drawing

http://press.princeton.edu/titles/10314.html

Graph Theory

Graph Theory

本站僅介紹最基礎的圖論知識。讀者如果覺得不過癮,可以自行研究下述這些進階的圖論領域。

Graph Theory與Linear Programming

組合最佳化的經典問題,路樹流割配,通通可以套用線性規劃。針對流割配這類複雜度較高的問題,線性規劃的速度遠比經典演算法還快!針對問題本身的性質,有著各種加速技巧,內容多到可以寫成一本書。有興趣的讀者可以自行查詢資料。

Minimum Ratio Spanning Tree: Dinkelbach's Algorithm

Geometric Graph Theory

http://en.wikipedia.org/wiki/Geometric_graph_theory

http://www.math.harvard.edu/~knill/graphgeometry/

引入距離的概念。

Topological Graph Theory

http://en.wikipedia.org/wiki/Topological_graph_theory

著重於點與邊。發掘特殊的圖,建立從屬關係。

minor containment problem 問一張圖是不是有某個minor。至少是NP-complete。
http://en.wikipedia.org/wiki/Graph_minor
http://en.wikipedia.org/wiki/Robertson–Seymour_theorem
http://en.wikipedia.org/wiki/Graph_structure_theorem

Extremal Graph Theory

http://en.wikipedia.org/wiki/Extremal_graph_theory

著重屬性計量。

Structural Graph Theory

研究圖的各種架構方式、描述方式。

本站僅提到兩種方式:用點和邊架構出圖、用交集架構出圖。

Algebraic Graph Theory與Spectral Graph Theory

http://en.wikipedia.org/wiki/Algebraic_graph_theory

http://en.wikipedia.org/wiki/Spectral_graph_theory

http://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/

以代數描述一張圖、分析一張圖。