4 Laplacian Matrix ぱらぱらめくる『Graphs and Matrices』
- エッジが無いノードペアは0、エッジありのペアは-1、対角成分はノードの次数であるような行列がLaplacian matrix
- L=D-A (ただし、Dは対角行列で対角成分がノードの次数、Aはadjacency matrix)
- L=Q Q^T (ただしQはincidence matrix)でもある
- Lは対称で半正定値。ランクはn-k (kは連結成分数)、
。行和と列和がゼロ。余因子は等しい(ただし、余因子はminor 行列L(i|j)のdeterminantに(-1)^{i+j}を掛けたもの(こちらを参照)
- 4.3 Matrix-tree theorem
- 余因子の値は全域木の数に等しく、複数のノードを除いたL(W|W)では全域木の森になっており、det L(W|W)は森にある全域木の本数となっている。また、それぞれの全域木に一つずつWの要素が含まれる
- 4.4 固有値の上界
- 4.5 Edge-Laplacian of a tree
- Edge-Laplacianとは K = Q^T Q (Qはincidence matrix)のこと （Laplacian は L = Q Q^T)
- Laplacianがノードについてのそれなのに対して、Edge-Laplacianはエッジ数ｘエッジ数の行列
- このKとHQ=Iなる行列Hとに関係がある
- Edge-Laplacianとは K = Q^T Q (Qはincidence matrix)のこと （Laplacian は L = Q Q^T)
