3

グラフのラプラシアン固有値0の重複度と連結成分の関係

782
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$の重複度は,連結成分の個数に等しい.

投稿日:20201121

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

ufo
ufo
3
782
大学院生M1。情報&数学系。グラフ理論を中心に線形代数や確率も少しかじりながら研究中。共同研究論文が今年中に投稿される(かも)。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中