グラフ理論 - 連結性 #Python3

グラフとは

物と物の間に何か関係がある時に、その関係の内容は考えず、"何と何がつながっているのか" だけを問題にしたい時がある。そんな時に考えられるのがグラフである。グラフは頂点とその頂点間をつなぐ辺からなる構造体であり、頂点の集合を V, 辺の集合を E として、$G = (V, E)$ と表す。
今回は、E の要素が V のデカルト積

集合 A , B のデカルト積 $A×B=${$a,b \mid a∈A∧b∈B$ }

について２元部分集合となる, つまり $E⊆V×V$ が成り立つものを考える。
グラフにはハイパーグラフと呼ばれ, $E⊆2^V$ のように辺が頂点集合のべき集合

集合 S のべき集合は S の部分集合の全体の集合

に存在するような物もあり、そこでは辺は2点間のつながりだけでなく、任意個数の頂点を結ぶことができる.

ここで考えるのは単純グラフ G で、G には自己ループや多重辺がない。つまり端点が同じであるような辺や、同じ端点の組み合わせもつ辺が存在しない。

連結性

今回の主題はグラフに関する連結性という性質である。連結性があるグラフとは, どの点から辿り始めてもどの点へでも行ける, つまり, 任意の2頂点をつなぐ路が必ず存在するような物のことである。ここで注意したいのは, 任意の2点は直接つながっている必要はないということである。

すべての頂点が他の頂点と1辺で直接つながっているようなグラフは完全グラフと呼ばれ$K^n$ と表す。ここで$n$はグラフの位数(=頂点の数)
であり、例えば$K^3$は三角形である.

今回はグラフがこの連結性を持つかどうかをとても簡単に判定できてしまう方法を示す。

ラプラシアン行列

あるグラフが与えられ、それが連結かと問われた時に路を考えてアルゴリズミックに解こうとすると、位数が少し大きくなるだけで難しくなってしまう.しかし、ラプラシアン行列と呼ばれる行列を導入することでそれを代数的に求めることができる。

位数が $n$ で頂点 $V_k$ の次数(=辺の数)が $d_k$ となっているグラフ $G$ を考える。例えば, 先の完全グラフ $K^3$ を考えると、この場合 $n=3, d_1=d_2=d_3=2$ となる。このグラフは勿論, 連結グラフでもある。
ここで、このグラフを行列で表すことにする。位数を取って, $n×n$ 行列 $L$ を作り、

$(i,j)$ 成分 $L_{ij}$ と $L_{ji}$ には $G$ の頂点 $V_i$ と $V_j$ が辺でつながっているのなら -1 を, つながっていないなら $0$ を代入する
$i=j$ となる対角成分には $V_i$ の次数を入力する

これだけの作業で作られたこの行列はラプラシアン行列と呼ばれ、大変便利な特性を持っている.

階数が グラフの位数と連結成分の数の差 である
二次形式が単純
Stieltjes 行列である
半正定値行列である

今回は $rank (L)$ を使って行列の連結性を判定する. 上で出てきた連結成分の数とは簡単に言うと、グラフが何個の連結グラフをから出来てるか、ということである。全体としては一つの連結グラフではないけど、"部分として小さな連結グラフを複数含んでいて、それらの集合を一つのグラフとて見る" という事があるのだ。逆に言えば、今考えている位数 $n$ のグラフが連結なら、その連結成分の個数は勿論全体としての $1$であるわけだから、次が成り立つのである

rank(L)=n-1

Proof.
ラプラシアン行列の定義は, (向き付け)接続行列を用いて, $L:=NN^T$ である。また、ラプラシアン行列は固有ベクトル $e=(1,...,1)$ を固有値 $μ=0$ に対して持つ.

∵ $L$ は対角成分が次数となっている対角行列 $D$ と、辺がある成分には $1$ それ以外には $0$ を持つ隣接行列 $A$ を用いて, $L=D-A$ と表せ, $Le=De-Ae=[deg(v_1)-deg(v_1), ...,deg(v_n)-deg(v_n)]^T= 0$
また、$N$ は(向き付け)接続行列と呼ばれる $|V|×|E|$ 行列で,
$N(i,j)=${1 if $v_i$ が辺$e_j$の先, -1 if $v_i$ が辺$e_j$の尾, $0$ if $v_i∈e_j$} で表される。また、ラプラシアン行列は辺の向き付けには結局依存しない。

ここで、グラフ $G$ をその連結要素で $G=G_1⊕G_2⊕...⊕G_k$ と表すと, 任意のベクトル $x$ に対して次の二次形式が成り立つ。
$x^TLx=x^TNN^Tx=||N^Tx||^2=\sum_{v_i,v_j∈E} (x_i-x_j)^2$
今、$E(G)=E(G_1)∪E(G_3)...∪ E(G_k)$ という直和になっているので次が言える。
$x^TLx=\sum_{v_i,v_j∈E(G_1)} (x_i-x_j)^2+\sum_{v_i,v_j∈E(G_2)} (x_i-x_j)^2+...+\sum_{v_i,v_j∈E(G_k)} (x_i-x_j)^2$

∵ 向き付け接続行列の定義より、$N^T$ は各行にその辺の端点に対応する $1$ と $-1$ を一つずつ持ち、それ以外は $0$
$⊕$ は非交和と呼ばれ、互いに素な頂点集合を持つ２つのグラフ $G,H$ に対して $V(G)∪V(H)$ を頂点集合に, $E(G)∪E(H)$ を辺集合に持つようなグラフ

$x$ が固有値 $μ$ をもつ固有ベクトルであるとすると、$Lx=0$ であるので $x^TLx=0$ となり、上の議論より, $G$ の任意の連結成分 $G_a$ に対して $\sum_{v_i,v_j∈E(G_a)} (x_i-x_j)^2=0$ が言える。よって、$x$ の成分は $G$ の全ての構成要素で等しい。$G$ が連結なら, $x$ は全ての成分が等しく、$x$ は $e$ の実数倍になる。よって $μ$ の幾何学的重複度が $1$ であること、またそこから代数的重複度も $1$ であり $μ$ は単純固有値であることが言える。逆に, $G$ が $k≥2$ なる $k$ について, $G_1,G_2,.., G_k$で連結でないとすると、$n=|V(G)|, z_i∈\mathbb{R}^n$ として定義する、構成要素$G_i$ の頂点で成分が$1$, それ以外で$0$となるベクトル$z_i$について、$N^Tz_i=0$ と、$Lz_i=NN^Tz_i=0$ が言える。$z_1,z_2,...,z_k$ は線形独立なベクトル集合なので、$μ$ の重複度は最小で $k$ である。しかし、$G_i$ は定義よりそれぞれ連結であるので、連結グラフは単純固有値 $μ$ を持ち、$μ$ は代数的重複度 $k$ を持つことが示された。

幾何学的重複度と代数的重複度はそれぞれ、固有空間の次元と、固有方程式の $n$重解についての $n$ のことである

いま、グラフ$G$が連結である事と、$μ=0$ が $L$ の単純固有値である事が同値であり、$μ$ の代数的重複度が $G$ の連結要素の数である事が示された。よって、一般に、グラフのラプラシアン行列の階数は、行数－線形独立な行ベクトルの数, つまり, 位数と連結成分数 $k$ を用いて $n-k$ と一致することがわかる。

Pythonでの実装

今回は与えられた頂点集合と辺集合からそのグラフのラプラシアン行列を作り、階数を計算し、その連結性を判定する。
持っている情報は、頂点の数 $v$ , 辺の数 $e$ と、端点の情報 $i,j$ で表された辺の集合とする。また辺は一通りのみで表されているとする

import numpy as np

l = [1,2,3,4]   # 例えば(1,2) を繋ぐ辺と(3,4)を繋ぐ辺を持つとする
l2 = []
l3 = []
        
for i in range(v):
    l2.append(0)
for i in range(v):  # 要素が全て0の２次元リスト
    l3.append(l2)

m = np.array(ll)   # ラプラシアン行列の土台を作る

for i in l[::2]:   # 辺の端点に一致するmの成分に-1を代入してく
    x = i
    y = l[l.index(i)+1]
    g[x-1][y-1] -= 1
    g[x-1][y-1] -= 1



for i in range(1, v+1):
    c = l.count(x)
    g[i-1][i-1] += c   # 対角成分に入れる次数を元々入ってる0に足す

rslt = np.linalg.matrix_rank(m)   # 行列の階数を計算してくれる
if int(rslt) == int(v-1):
    print("Connected")
else:
    print("Disconnected")

こうして与えられた辺のの情報だけでその連結性が簡単に判別できる。といってもここで一番すごいのはNumPyの関数かもしれない。。
作った行列が本当にラプラシアン行列なのかを必要条件的に確認する方法はいくつかある。
例えばラプラシアン行列はその定義から対称行列であるし、

$(i,j)$ 成分と$(j,i)$ 成分には辺があるのなら $-1$ が、ないなら $0$ が入ってるから

行や列はそれぞれ成分の和が明らかに0になる。また、Stieltjes 行列であるラプラシアン行列の平方根もまたStieltjes 行列である。

参考文献

The Laplacian Matrix of a Graph, R.B. Bapat, 1996
The Adjacency Matrix
Properties of the Laplacian
二次形式
隣接行列,ラプラシアン行列
単純固有値