グラフの調和関数とラプラシアン行列

グラフとは、頂点の集合と、頂点をつなぐ辺の集合の組。考えるグラフは単純グラフとする。単純グラフとは、ループ(両端が同一の点である辺)と多重辺(ある2頂点をつなぐ辺が複数ある状態)のないグラフのこと。

f(x)を(単純)グラフの頂点から実数への関数とする。
頂点aと辺でつながっている頂点の集合を $X_a$ と書く。a自身は含まない。f(x)が調和関数とは、 $X_a$ での値の平均が、aでの値と等しいこと、つまり $\displaystyle\frac{1}{|X_a|}\sum_{x\in X_a}f(x)=f(a)$ (|A|で集合Aの要素数を表すとする)

連結で有限なグラフにおいて、調和関数は定数関数しかない。グラフが連結とは、どんな2頂点の間も、辺を辿ってたどりつけること。次の平均値の性質を使って証明する: 数集合の平均値は最大値より小さく、平均値と最大値が一致するのは、集合のすべての値が等しいときのみ。
証明:f(x)を調和関数とする。グラフは有限だから、f(x)が最大となる頂点が存在する。その1つをaとする。調和関数の定義より、{f(x)|x∊ $X_a$ }の平均はf(a)に等しい。平均値の性質より、{f(x)|x∊ $X_a$ }の最大値Mはf(a)以上だが、f(a)の最大性より、M=f(a).平均値の性質より、すべてのx∊ $X_a$ でf(x)=f(a).次にb∊ $X_a$ をとり同様の議論をして、すべてのx∊ $X_b$ でf(x)=f(b)=f(a).これを繰り返すことで、すべての頂点xでf(x)=f(a)がわかる(グラフが連結だから)。調和関数は、グラフの連結性を測ると言える。

グラフに付随する行列をいくつか定義する。

グラフの頂点に自然数で番号を振る。i番目の頂点を $a_i$ と書く。
グラフの次数行列 $D$ とは次で定義される行列:\begin{pmatrix}
|X_{a_1}|& && 0 \\\
& |X_{a_2}| & & \\\
& & \ddots & \\\
0 & & &|X_{a_n}|
\end{pmatrix}

ただし、nはグラフの頂点の総数。

グラフの隣接行列 $A$ とは、ij成分が次の $\chi_{ij}$ である行列:
$\chi_{ij}=\begin{cases}1(a_iとa_jをつなぐ辺がある) \\0(a_iとa_jをつなぐ辺がない)\end{cases}$
ただし、 $\chi_{ii}=0$ と定める。

行列というより表のようだが、次のラプラシアン行列を考えると、調和関数との関係が出てくる。

グラフのラプラシアン行列 $L$ とは、 $L=D-A$ で定義される行列のこと。これは解析学のラプラシアン∆の類似で、グラフ調和関数に作用させると０になる:
$L{\boldsymbol f}={\boldsymbol o}, ~{\boldsymbol f}=\left(\begin{array}{c}f(a_1) \\f(a_2) \\\vdots \\f(a_n)\end{array}\right)$
これは実際に展開すると確認できる：
$D{\boldsymbol f}=(|X_{a_i}|f(a_i))_i,\\A{\boldsymbol f}=(\displaystyle\sum_{x\in X_i}f(x))_i,\\L{\boldsymbol f}=D{\boldsymbol f}-A{\boldsymbol f}={\boldsymbol o}$
(ただし $(w_i)_i$ で第i成分が $w_i$ の縦ベクトルを表すとする。)