Adjacency Matrix

Adjacency Matrix

矩陣A。點與點關係。

Transpose of Adjacency Matrix

Aᵀ可以翻轉所有邊的方向。

Vertex Labeling

向量x。

Edge Labeling

矩陣W。

Neighbor

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

元素是布林,元素加法是布林OR,元素乘法是布林AND。

Degree

Aᵀx是入邊數量,Ax是出邊數量。x的元素們,通通是1。

元素是實數,元素加法是實數加法,元素乘法是實數乘法。

Walk

Aᴺ。N是步數。

元素是布林,元素加法是布林OR,元素乘法是布林AND。

矩陣次方,總共O(logN)次矩陣乘法。

矩陣乘法,直接計算O(V³),Strassen's Algorithm O(Vω)。

Strassen's Algorithm需要用到元素加法反運算,然而布林OR沒有反運算。改弦易轍,以實數代替布林,零當做false,非零當做true。

Walk詳細解釋

把一張圖想像成道路地圖,把圖上的點想像成地點,把圖上的邊想像成道路。現在我們在意的是:由某一點開始,走過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點──宛如矩陣乘法求元素(i,k)。一次矩陣乘法就將所有(i,k)配對通通算好。

元素加法是布林OR,元素乘法是布林AND,adjacency matrix自己乘上自己,就是走兩條道路的情況了!

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

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

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

UVa 10681

Transitive Closure

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

以路徑長度進行分類。每一個點,走零條、走一條、走兩條、……、走無限多條邊,到達圖上哪些點。

A* = I ⋁ A ⋁ A² ⋁ ... ⋁ A

一張圖總共V個點。走路不繞圈子,V-1條邊足矣。

A* = I ⋁ A ⋁ A² ⋁ ... ⋁ AV-1

矩陣多項式,Horner's Rule一加一乘。總共O(V)次矩陣乘法與矩陣加法。

(一)以實數代替布林。

A* = I + A + A² + ... + AV-1

矩陣乘法,得以使用Strassen's Algorithm O(Vω)。

(二)級數化作分式。

A* = I + A + A² + ... = (I - A)⁻¹

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

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

反矩陣,高斯消去法O(V³)。

UVa 12695

Strongly Connected Component

(A* ⋀ A*ᵀ)x。往返,鄰居,一次找一個。

Path

D = ∞I + W + W² + ... + WV-1

元素是實數,元素加法是實數min,元素乘法是實數加法。

矩陣乘法,然而實數min沒有反運算,必須採用特殊手法避開反運算,例如Seidel's Algorithm。

http://theory.stanford.edu/~virgi/cs367/
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
https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides14.pdf

Laplace Matrix

Laplace Matrix(Laplacian Matrix)

L模仿「Laplace Operator」,Lx模仿「中央與四周的差距總和(四周減中央)」。理應是L = A - D,卻誤植成L = D - A。圖論專家不知道是哪根筋不對勁。大家只好將錯就錯。

L D A分別代表Laplace Matrix、Degree Matrix、Adjacency Matrix。

Pairwise Product / Pairwise Squared Distance

Ax是鄰點總和。

一點:[x₁]             (無向圖、完全圖、有自環)
二點:[x₁ + x₂, x₁ + x₂]
三點:[x₁ + x₂ + x₃, x₁ + x₂ + x₃, x₁ + x₂ + x₃]

xᵀAx是兩兩相乘、通通加總。

一點:x²
二點:x₁² + x₂² + x₁x₂ + x₂x₁
三點:x₁² + x₂² + x₃² + x₁x₂ + x₂x₁ + x₁x₃ + x₃x₁ + x₂x₃ + x₃x₂

Lx是自己與鄰點的差距總和。

一點:[x₁-x₁]
二點:[(x₁-x₁)+(x₁-x₂), (x₂-x₁)+(x₂-x₂)]
三點:[(x₁-x₁)+(x₁-x₂)+(x₁-x₃), (x₂-x₁)+(x₂-x₂)+(x₂-x₃), (x₃-x₁)+(x₃-x₂)+(x₃-x₃)]

xᵀLx是兩兩相減平方、通通加總。

一點:0
二點:(x₁-x₂)²
三點:(x₁-x₂)² + (x₁-x₃)² + (x₂-x₃)²

寫成代數式子。

Ax   = [ ∑ⱼ aᵢⱼ xⱼ ]                      鄰點總和
xᵀAx = ∑ᵢ ∑ⱼ aᵢⱼ xᵢ xⱼ                    點對相乘總和
Lx   = [ ∑ⱼ aᵢⱼ (xᵢ - xⱼ) ]               鄰點與自身差異總和(無向圖)
xᵀLx = 1/2 ∑ᵢ ∑ⱼ aᵢⱼ (xᵢ - xⱼ)²           點對相減平方總和(無向圖)
(Dout-A)x        = [ ∑ⱼ aᵢⱼ (xᵢ - xⱼ) ]   鄰點與自身差異總和(有向圖)
xᵀ(Din+Dout-2A)x = ∑ᵢ ∑ⱼ aᵢⱼ (xᵢ - xⱼ)²   點對相減平方總和(有向圖)

Cut

min xᵀLx。x的元素們,只能是0或1,不能全0全1。

Partition

《Minimal Dirichlet Energy Partitions for Graphs》

I haven't spent my skill points on inequality.

Random Walk

《Random Walk st-Connectivity》

I haven't spent my skill points on inequality.

Isomorphism

《Spectral Graph Isomorphism》

I haven't spent my skill points on inequality.

Incidence Matrix

Incidence Matrix

點邊關係。不討論自環。

無向圖:點碰邊1,否則0。

有向圖:點碰出邊+1,點碰入邊-1,否則0。

Laplace Matrix

L = MMᵀ。L代表無向圖的Laplace Matrix,M代表有向圖的Incidence Matrix。

Component

rank(M) = V - C。矩陣維度,等於點數減去連通分量數量。

證明手法:點邊編號重排,交換橫條,交換直條,讓連通分量靠在一起,形成分塊矩陣。

Tree

det(submatrix(V-1)×(V-1)(M)) = ±1。樹的Incidence Matrix,隨便砍掉一個橫條,行列式一定是+1或-1。

證明手法:點邊編號重排,交換橫條,交換直條,讓對角線是1。其餘1數量不足以連成斜線。

Spanning Tree

Laplace Matrix的任意一個cofactor的行列式,等於生成樹數量。此性質稱作「Matrix Tree Theorem」。

cofactor就是隨便砍掉一個直條與一個橫條,剩下來的矩陣。根據砍掉的位置,乘上係數+1或-1 。請參考維基百科「Minor」。

證明手法:觀察Incidence Matrix。

L砍掉一個直條與一個橫條是L'。M砍掉一個橫條是M'。

L = MMᵀ。L' = M'M'ᵀ。det(L') = det(M'M'ᵀ)。

Cauchy-Binet公式,展開det(M'M'ᵀ),得到許多(V-1)×(V-1)方陣的行列式,兩兩自乘、通通加總。

各個方陣,恰是C(E,V-1)的各種可能組合。E條邊取V-1條邊,逐個判斷是不是生成樹。

一個方陣,視作Incidence Matrix隨便砍掉一個橫條。方陣的行列式:連通±1(因為是樹),不連通0(因為rank不足)。

兩兩自乘,成為非負數;通通加總,就是生成樹數目。

Adjacency Spectrum(Under Construction!)

Adjacency Spectrum

Adjacency Matrix的V個特徵值。

實施「傅立葉轉換(向量版本)」或「譜分解(矩陣版本)」,所得結果稱做Spectrum。Adjacency Matrix實施譜分解,所得結果稱做Adjacency Spectrum。

Euler Characteristic

tr(A) = 0
tr(A²) = 2E   E is # of edges
tr(A³) = 6T   T is # of triangles

Component

特徵值為零的數量,等於連通成分數量。

度數正規化Â = √D⁻¹A√D,特徵值介於±1。第二大的特徵值小於1,則圖連通。

http://web.cs.elte.hu/~lovasz/eigenvals-x.pdf
https://ilyaraz.org/static/class/scribes/scribe14.pdf
https://ilyaraz.org/static/class/scribes/scribe15.pdf

Clique

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

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):完美匹配是否存在。

Laplace Spectrum(Under Construction!)

Laplace Spectrum

Laplace Matrix的V個特徵值。

L是對稱正半定矩陣,特徵值是正數或零,特徵向量正規正交。

xᵀLx的高峻處、低窪處,位於最大、最小特徵值的特徵向量上方。

L的最小特徵值恰是0,低窪處皆是最小值0。最小值位於特徵值0的特徵向量1。

特徵向量,然並卵。

對稱正半定矩陣,特徵向量互相垂直。

第一小的特徵向量是[1,1,1,...],特徵值是0。

第二小的特徵向量(Fiedler vector)有點用處,如同套環。

curve:    t->x(t) t->y(t) t=0~1    two function
polyline: i->x[i] i->y[i] i=0~n-1  two array
surface:  uv->x(u,v) uv->y(u,v) uv->z(u,v)  three 2d function
mesh:  uv merge to i

eigenfunction of laplace operator of curve:    t->f(i)   infinite functions
                                                         (plot as nodal sets)
eigenvector   of laplace operator of polyline: i->f(i)   n vectors
                                                         (sin/cos wave)
eigenfunction/vector plot on curve/polyline as various colors. [-1,+1]->[0,255]
nodal set of eigenfunction -----> meaningless?
nodal set of Fiedler vector ----> look likes rings

Spanning Tree

前V-1大特徵值的乘積,等於生成樹數量。

Graph Property(Under Construction!)

Reachability

可達程度。走k步可以到哪裡。

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://web.stanford.edu/~boyd/papers/cvx_opt_graph_lapl_eigs.html

Graph Sampling(Under Construction!)

Graph Stream

《Graph Stream Algorithms: A Survey》

Graph Sketch

《Graph Sketches: Sparsification, Spanners, and Subgraphs》

Graph Sparsification

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

http://stellar.mit.edu/S/course/18/sp18/18.408/index.html

Spanner

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

Expander

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

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!)

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

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