Aᵀx.x的元素们,起点是1,其余点是0.
元素是布林,元素加法是布林OR,元素乘法是布林AND.
Aᵀx是入边数量,Ax是出边数量.x的元素们,通通是1.
元素是实数,元素加法是实数加法,元素乘法是实数乘法.
Aᴺ.N是步数.
矩阵次方,总共O(logN)次矩阵乘法.
Strassen's Algorithm需要用到元素加法反运算,然而布林OR没有反运算.改弦易辙,以实数代替布林,零当作false,非零当作true.
把一张图想像成道路地图,把图上的点想像成地点,把图上的边想像成道路.现在我们在意的是:由某一点开始,走过N条道路后,可以到达哪些点?
走过N条道路,各位应该马上想试试看Graph Traversal──可是遇到重复地点就没辙了.Graph Traversal只能拜访一个点一次.
如果i点可以走到某一个j点,这个j点又可以走到k点,那么就可以由i点走到k点,刚好两条道路.
穷举所有可能的j点,就可以判断i点走到k点,是否刚好两条道路!
写成数学式子:
r₂(i k):i点走到k点,是否刚好2条道路.
i点到j点,j点到k点,穷举j点──宛如矩阵乘法求元素(ik).一次矩阵乘法就将所有(ik)配对通通算好.
元素加法是布林OR,元素乘法是布林AND,Adjacency Matrix自己乘上自己,就是走两条道路的情况了!
两条添加一条就是三条,三条添加一条就是四条.逐次添加一条道路,慢慢累积,最后就得到走N条道路的情况.
走两条道路的矩阵,再乘上一次Adjacency Matrix,就是走三条道路的矩阵.走N条道路的矩阵,就是N次方.
另外这个方法也可以用来计算从一点走到另外一点,走N条道路,总共有几种走法.各位可以想想看.
以路径长度进行分类.每一个点,走零条,走一条,走两条,......,走无限多条边,到达图上哪些点.
一张图总共V个点.走路不绕圈子,V-1条边足矣.
矩阵多项式,Horner's Rule一加一乘.总共O(V)次矩阵乘法与矩阵加法.
为了收敛,添加一个倍率α,让α < 1.
元素是实数,元素加法是实数min,元素乘法是实数加法.
矩阵乘法,然而实数min没有反运算,必须采用特殊手法避开反运算,例如Seidel's Algorithm.
矩阵对角线,即是自环.
矩阵n次方的对角线,即是长度n的回路.
A²对角线总和:边数的两倍.(A预先删除自环)
A³对角线总和:三角形数量的六倍.(A预先删除自环)
重排编号,重排横条直条,形成三角矩阵(上下皆可),而且对角线是零.
顺带一提,有向图可以拆解成一群自环(对角线矩阵),两个有向无环图(上下三角矩阵,不含对角线).重排编号,得到不同拆解方式.
换句话说,特征值为零的数量,等于连通分量数量.
证明手法:重排编号,重排横条直条,让连通分量靠在一起,形成分块矩阵.
Tutte Matrix:权重换成变数.下三角矩阵变号.删除对角线.
rank(T):最大匹配的边数的两倍.
度数正规化Â = √D⁻¹A√D,特征值介于±1.第二大的特征值小于1,则图连通.
Random Walk
随机漫步,容易绕行于平均度数较高的子图,近似于团.
无限大次方A∞,最大特征值的特征向量,元素绝对值较大者,近似于团.
微积分的梯散:邻点减自身,通通加总,除以dx平方.
图论的梯散:自身减邻点,通通加总.
微积分和图论的定义,相差一个负号,相差一个分母.
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ᵀLx是两两相减平方,通通加总.
写成代数式子.
Dirichlet Energy
"狄利克雷能量".各处梯度长度平方和.等于xᵀLx.
也有人再乘上1/2,迎合物理学的能量定义.
微积分的狄利克雷能量:正方形网格.梯度是右点减自己,上点减自己.将梯度值填在边上,那么各处梯度长度平方和,即是各点上边右边平方和,刚好每条边都数一次,等于xᵀLx.
图论的狄利克雷能量:任意图.亦等于xᵀLx.
将梯度值填在边上,那么对应梯度差异平方和,即是各边差异平方和,刚好每条边都数一次,等于(x-y)ᵀL(x-y).
主要应用:给定原图,求得新图,令两图相仿.
min xᵀLx.x的元素们,只能是0或1,不能全0全1.
对称正半定矩阵.特征值是正数或零,特征向量正规正交.
Spanning Tree
去掉最小的特征值0,其他V-1个特征值的乘积,等于生成树数量.
随机漫步,由i到j,由j到i的平均边数.
d(ij) = L⁺ᵢᵢ + L⁺ⱼⱼ - 2L⁺ᵢⱼ.其中L⁺是虚拟反矩阵.
走一步的矩阵P = D⁻¹A.
无向图:点碰边1,否则0.
有向图:点碰出边+1,点碰入边-1,否则0.
L代表无向图的Laplacian Matrix,M代表有向图的Incidence Matrix.
证明手法:重排点边编号,重排横条直条,让连通分量靠在一起,形成分块矩阵.
证明手法:重排点边编号,重排横条直条,让对角线是1.其余1数量不足以连成斜线.
Laplacian Matrix的任意一个cofactor的行列式,等于生成树数量.此性质称作"Matrix Tree Theorem".
cofactor就是随便砍掉一个直条与一个横条,剩下来的矩阵.根据砍掉的位置,乘上系数+1或-1 .请参考维基百科"Minor".
L砍掉一个直条与一个横条是L'.M砍掉一个横条是M'.
各个方阵,恰是C(EV-1)的各种可能组合.E条边取V-1条边,逐个判断是不是生成树.
一个方阵,视作Incidence Matrix随便砍掉一个横条.方阵的行列式:连通±1(因为是树),不连通0(因为rank不足).
两两自乘,成为非负数;通通加总,就是生成树数目.