Graph Spectrum(Under Construction!)

Graph Spectrum

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

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。

【待補文字】

Graph Property(Under Construction!)

Reachability

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

http://www.lab2.kuis.kyoto-u.ac.jp/keisan-genkai/reports/2006/nhc/Uri_Zwick.pdf

範例:Transitive Closure

請參考「Transitive Closure: Matrix Multiplication」。

矩陣元素改成Boolean,矩陣加法改成OR運算,矩陣乘法改成AND運算即可!

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

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

範例:Shortest Path

矩陣元素依然是實數,矩陣加法改成最小值運算,矩陣乘法改成加法運算即可!

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

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

範例:Matching

【待補文字】

Similarity(Graph Kernel)

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

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

範例: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 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://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

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 Drawing(Under Construction!)

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

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》

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/

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