グラフのラプラシアン固有値0の重複度と連結成分の関係
はじめに
研究を進めるにあたり、グラフのラプラシアン固有値0の重複度と連結成分の関係について証明を考える機会がありました。
Mathlogで記事を書いてみたいという気持ちと、研究の過程で出会った定理について考えた記録を残したいという思いにより、この記事を作成しました。
$n$個の頂点を持つ単純グラフ$G$を考えたとき，$v_i$（$0\leq i\leq n-1$）をグラフ$G$の頂点とし，$\deg(v_i)$を頂点$v_i$の次数とする．
ここで， $$D=\text{diag}(\deg(v_1),\deg(v_2),\dots,\deg(v_n))$$とし，$A$をグラフ$G$の隣接行列とする． $$L=D-A$$により定義される行列$L$をラプラシアン行列という．
このとき，$L$の要素は
$$L_{i,j}=\begin{cases}
\deg(v_i) &\text{$i=j$}\\
-1 &\text{$i\neq j$ and $v_i$と$v_j$が隣接}\\
0 &\text{otherwise}
\end{cases}
\quad \text{（$1\leq i,j\leq n$）}$$ によって与えられる．
グラフ$G$のラプラシアン固有値$0$の重複度は，連結成分の個数に等しい．
ラプラシアン固有値$0$の重複度を$m_0$，グラフの連結成分を$C_l$（$1\leq l\leq c$）とする．
$C_l$（$1\leq l\leq c$）に対応した値が全て$1$，その他の値が全て$0$という$n$次ベクトル$x'_l={}^t[0,\dots,0,\underbrace{1,\dots,1}_{\text{$C_l$に対応した部分}},0,\dots,0] \quad \text{（$1\leq l\leq c$）}$が線形独立な固有値$0$の固有ベクトルとして構成できるので，$m_0\geq c$である．$x={}^t[x_1,x_2,\dots,x_n]$をラプラシアン固有値$0$の固有ベクトルとすると，${}^tx'Lx'=0$ であるから，
$0={}^tx'Lx'$
$=\sum_{l=1}^c\sum_{j\in C_l} x_j(L x)_j$
$=\sum_{l=1}^c\left(\sum_{j\in C_l} D_{j,j}x_j^2-\sum_{j,k\in C_l} A_{j,k}x_jx_k\right)$ （$L=D-A$より）
$=\sum_{l=1}^c\left(\sum_{j\in C_l} \sum_{k\in C_l} A_{j,k}x_j^2-\sum_{j,k\in C_l} A_{j,k}x_jx_k\right)$
$=\sum_{l=1}^c\sum_{j\in C_l} x_j \sum_{k\in C_l} A_{j,k} (x_j-x_k)$
$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} \left(x_jA_{j,k}(x_j-x_k)+x_kA_{k,j}(x_k-x_j)\right)$
$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} (x_jA_{j,k}-x_kA_{k,j})(x_j-x_k)$
ここで，$A_{j,k}=A_{k,j}$（$1\leq j,k\leq n$）より，
$=\frac{1}{2}\sum_{l=1}^c\sum_{j,k\in C_l} A_{j,k}(x_j-x_k)^2$
である．
連結成分$C_l$（$1\leq l\leq c$）上の任意の$2$頂点$j,k\in C_l$（$1\leq l\leq c$）は経路$j\rightarrow p_1\rightarrow p_2\rightarrow \dots \rightarrow p_s\rightarrow k$（$p_1,\dots,p_s\in C_l$（$1\leq l\leq c$））が存在して，$A_{j,p_1}=A_{p_1,p_2}=\dots=A_{p_s,k}=1 \quad \text{（$1\leq l\leq c$）}$である．
したがって，$x_j=x_{p_1}=x_{p_2}=\dots=x_{p_s}=x_k \quad \text{（$j,p_1,\dots,p_s,k\in C_l$（$1\leq l\leq c$））}$であるから，$x$がラプラシアン固有値$0$の固有ベクトルとなるとき，$x={}^t[\underbrace{a_1,\dots,a_1}_{\text{$C_1$に対応した部分}},\underbrace{a_2,\dots,a_2}_{\text{$C_2$に対応した部分}},\dots,\underbrace{a_c,\dots,a_c}_{\text{$C_c$に対応した部分}}] \quad \text{（$a_l\in\mathbb{C}$，$1\leq l\leq c$）}$である．
よって，ラプラシアン固有値$0$の固有ベクトル$x$は$x'_l$（$1\leq l\leq c$）を用いて$x=\sum_{l=1}^ca_lx'_l \quad \text{（$a_l\in\mathbb{C}$，$1\leq l\leq c$）}$である．
$x'_l$（$1\leq l\leq c$）の線形結合として表せるから，$c\geq m_0$である．
よって，$m_0=c$であるから，グラフ$G$のラプラシアン固有値$0$の重複度は，連結成分の個数に等しい．
この記事を高評価した人
この記事に送られたバッジ
投稿者
