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

Circuit

矩陣對角線,即是自環。

矩陣n次方的對角線,即是長度n的迴路。

A¹對角線:一步回到原處。
A²對角線:兩步回到原處。
A³對角線:三步回到原處。
A¹對角線總和:自環數量。
A²對角線總和:邊數的兩倍。(A預先刪除自環)
A³對角線總和:三角形數量的六倍。(A預先刪除自環)
trace(A) = L                         loop number L
trace(A²) = 2E   when trace(A) = 0   edge number E
trace(A³) = 6T   when trace(A) = 0   triangle number T

Directed Acyclic Graph

重排編號,重排橫條直條,形成三角矩陣(上下皆可),而且對角線是零。

順帶一提,有向圖可以拆解成一群自環(對角線矩陣)、兩個有向無環圖(上下三角矩陣,不含對角線)。重排編號,得到不同拆解方式。

Component

rank(U) = V - C。無向圖的上三角矩陣(不含對角線),矩陣維度=點數-連通分量數量。

換句話說,特徵值為零的數量,等於連通分量數量。

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

Matching

Tutte Matrix:權重換成變數。下三角矩陣變號。刪除對角線。

Tᵢⱼ = { xᵢⱼ    if i < j and edge (i,j) exists
      { -xⱼᵢ   if i > j and edge (i,j) exists
      { 0      otherwise

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

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

Adjacency Spectrum

Adjacency Spectrum

Adjacency Matrix的V個特徵值。

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

Random Walk

隨機漫步,容易繞行於平均度數較高的子圖,近似於團。

無限大次方A,最大特徵值的特徵向量,元素絕對值較大者,近似於團。

Laplacian Matrix

Laplace Operator

「拉普拉斯運算子」。處處求得梯度的散度。

微積分的梯散:鄰點減自身,通通加總,除以dx平方。

圖論的梯散:自身減鄰點,通通加總。

微積分和圖論的定義,相差一個負號,相差一個分母。

Laplacian Matrix

「梯散矩陣」。拉普拉斯運算子,寫成矩陣L。

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

L D A代表Laplacian 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ⱼ)²   點對相減平方總和(有向圖)

Dirichlet Energy

「狄利克雷能量」。各處梯度長度平方和。等於xᵀLx。

也有人再乘上1/2,迎合物理學的能量定義。

  sum ‖grad xᵢ‖²
= ½ sum sum Aᵢⱼ (xᵢ - xⱼ)²
= xᵀLx

微積分的狄利克雷能量:正方形網格。梯度是右點減自己、上點減自己。將梯度值填在邊上,那麼各處梯度長度平方和,即是各點上邊右邊平方和,剛好每條邊都數一次,等於xᵀLx。

圖論的狄利克雷能量:任意圖。亦等於xᵀLx。

【尚無正式名稱】

「對應梯度差異平方和」。等於(x-y)ᵀL(x-y)。

  sum ‖grad xᵢ - grad yᵢ‖²
= ½ sum sum Aᵢⱼ [(xᵢ - xⱼ) - (yᵢ - yⱼ)]² 
= ½ sum sum Aᵢⱼ [(xᵢ - yᵢ) - (xⱼ - yⱼ)]²
= (x-y)ᵀL(x-y)

將梯度值填在邊上,那麼對應梯度差異平方和,即是各邊差異平方和,剛好每條邊都數一次,等於(x-y)ᵀL(x-y)。

主要應用:給定原圖,求得新圖,令兩圖相仿。

Cut

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

https://csustan.csustan.edu/~tom/Clustering/GraphLaplacian-tutorial.pdf

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.

Laplacian Spectrum

Laplacian Spectrum

Laplacian Matrix的V個特徵值。

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

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

Spanning Tree

去掉最小的特徵值0,其他V-1個特徵值的乘積,等於生成樹數量。

Commute-Time Distance

隨機漫步,由i到j、由j到i的平均邊數。

d(i,j) = L⁺ᵢᵢ + L⁺ⱼⱼ - 2L⁺ᵢⱼ。其中L⁺是虛擬反矩陣。

走一步的矩陣P = D⁻¹A。

https://math.stackexchange.com/questions/1679597/
https://math.stackexchange.com/questions/1321305/

Incidence Matrix

Incidence Matrix

「關聯矩陣」。點邊關係。不討論自環。

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

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

Laplacian Matrix

L = MMᵀ。L代表無向圖的Laplacian 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

Laplacian 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不足)。

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