グ ラ フ の固有値について
2011SE063 市川智彦
指導教員：小藤俊幸

0
 1
A=
 0
 10

はじ めに1

現代社会においてネットワークは重要である. 社会的なネットワークは大規模なものになっていて，手計算で求めることは非常に難しい. ネットワークをグラフに対応する行列の固有値を調べるとグラフの特性がわかる，例えば，
かる.

2

 −1

L=
 0

 −10

実際的な問題を考えるためには大規模的なグラフを解析しなければならない，大規模なグラフを手計算で求めることは非常に難しい. したがって，グラフ，隣接行列，ラプラシアン行列を定義し固有値を求めるために数値計算法のひとつであるシルベスター二分法を学び，実験を行った.

ここに，V (G) は空集合ではなく，E(G) は V (G) の相異なる元の非順序集合のことである.E(G) は空集合でもよ11101

00 0 1 0−1 0 −13 −1 −1−1 2 −1−1 −1 400 −100 0 −1 1

図 3 ラプラシアン行列グラ フ
グラフ G とは，集合の対（V (G)，E(G)）のことである.

01010

図 2 隣接行列

固有値を求めたことにより，グラフの閉歩道の個数が分

2

10110

3. 第 i 行 (列) の成分の和は点 vi の次数に等しい
図 2 に図 1 の隣接行列の例を示す．

い.V (G) をグラフ G の点集合あるいは頂点集合といい， 3.2

ラ プラ シ ア ン 行列

V (G) の元の点あるいは頂点という.V (G) は有限集合とす
V (G) = {v1 ，v2 ，…，vp } であるグラフ G に対して，次る. また，E(G) を G の辺集合といい，E(G) の元を G の 数行列 C = (cij ) とは p × p 行列で，cij = 0 (i 6= j) で定辺という. 記述の簡略化を考えて，混乱が生じない場合は められる対角行列である. また，このとき，V (G)，E(G) をそれぞれ V ，E で表す. 図 1 に例を示す．
L (G) = C (G) − A (G)(2)[3] V (G) = {v1 , v2 ，v3 ，v4 ，v5 }，E(G) = {{v1 ，v2 }，{v1で定めれる p × p 行列をグラフ G のラプラシアン行列，あ，v4 }，{v2 ，v3 }，{v2 ，v4 }，{v3 ，v4 }，{v4 ，v5 }}るいはラプラシアンと言う. ここに，A(G) は隣接行列であv2v3る. 混乱のないときは (2) を L = C − A と略記する.[2] 図
3 に図 1 のラプラシアン行列の例を示す．
v1v4v5

図 1 グラフグラ フ の固有値4

位数 p のグラフ G の固有値とは，G の隣接行列の固有値である.G の隣接行列を A とするとき，G の固有値は，次の λ に関する方程式の p 個の解のことである.

3行列

3.1

隣接行列

G は位数 p のグラフで，V (G) = {v1 ，v2 ，…，vp } とする. この時，G の隣接行列 A(G) = (aij ) とは，その成分
aij が
1 vi vj ∈ E(G)aij =(1)0 vi vj ∈/ E(G)で定められる p × p 行列のことである. 混乱の恐れがな
いときは a(G) を単に A で表す. 行列 A は次の性質を持det(λIp − A) = 0(3)ここに，det 行列は A の行列を意味し，Ip は p × p 単位行列を意味する. λ に関する多項式 det(λIp − A) は G の固有多項式といい，φ(G; λ) で表す. 隣接行列の定義から

φ(G; λ) =pX

ak λp−k(4)k=0とすると，a0 = 1 でその他の全ての ai (1 ≤ i ≤ p) は整数である.[2]

つ.[2]

4.1

1. A は各成分が 0 か 1 の対称行列

1. グラフ G の固有値はすべて実数であり，その和は零である.[2]2. 主対角線の成分はすべて 0グ ラ フ の固有値の性質

2. G は位数 p の連結グラフとし，∆ は G の最大次数とする. このとき，G の任意の固有値 λ に対して | λ |≤ ∆が成立 [2]3. G は位数 p の連結グラフとし，∆ は G の最大次数とする. このとき，G が正則グラフであるための必要十分条件は，G が ∆ を固有値に持つことである.[2]4.2固有値と 閉歩道の個数

位数 p のグラフ G の固有値を λ1 ，λ2 ，…λp とし，長さk の閉歩道の個数を c とすると，

c=pX

λki

シルベスター二分法とは，固有値 λ が含まれる値の範囲を以下のように A のすべての固有値が含まれるように決定する.

λinf ≤ λi ≤ λsup(8)小さい方から i 番目の固有値を λi とする.λi が存在すup

る上限 λiupを初期値として与える.λ = (λiと λlowi+λlowi )/2 として，範囲に含まれる固有値の数 n(λ) を計算する.n(λ) が i 以上のとき λlowの値を λ で更新し、それ以iupup外の場合は λi を更新する.λ = (λi + λlowi )/2 と，n(λ)
を使い，上限と加減を繰り返し更新していく.[3] 以下で実際に図 1 に示すグラフについてシルベスター二分法を用い(5)て固有値を求める.

i=16.2である.[3]5ラ プラ シ ア ン 行列の固有値

5.1定理

図 1 の隣接行列 A は 3 章で求めた.
固有多項式 det[λI − A] = λ(λ4 − 6λ2 − 4λ + 2)

ラプラシアン行列は対称行列であるから，固有値は全て実数である. ここで，ラプラシアン行列の固有値のことを，単にラプラシアン固有値という. 位数 p のグラフ G のラプ

固 有 値[x=−1.749117547746521, x0.33490398537343, x = −1.271330370297698, x2.685543932670793, x = 0.0]

6.3

ラシアン行列の任意の固有値を µ とすると，0≤µ≤p==

ハウ ス ホルダー法の計算

ハウスホルダー法で求めた結果，シルベスター二分法で(6)求めた計算結果と同様に求められた。以下にハウスホルダー法でラプラシアン固有値を求めた結果を示す. 固有多項式 det[λI − L] = (λ − 5)(λ − 4)(λ − 2)(λ − 1)λが成り立つ.[3]5.2

シ ルベス タ ー二分法の計算

固ラ プラ シ ア ン 固有値と 木の個数

有値

[4.999989510, 5.000003815]，とする. このときグラフ G の木の個数 t は以下で求められ[3.999990463, 4.000004768]，[1.999992371, 2.000006676]，[0.999993324, 1.000007629]，[−0.000005722, 0.000008583]

る.[1][2]7

位数 p のグラフ G のラプラシアン固有値を λ1 , λ2 …, λpp1Y
λit=p i=26固有値の数値計算法

6.1

シ ルベス タ ー二分法(7)

終わり にあるグラフ G に対して，隣接行列 A とラプラシアン行列 L を求め，シルベスター二分法とハウスホルダー法を用いてグラフの固有値を求めた. 隣接行列 A の固有値から，(5) を用いるとグラフ G の長さ 3 の閉歩道の個数を求めることができる. 隣接行列の固有値をそれぞれ代入して求め固有値の大小関係を高速に比較するため，固有値の計算ると，閉歩道の個数は 12 個あるとわかった. また，(7) にに二分法を用いる. 二分法はシルベスターの慣性律をを利

ラプラシアン行列の固有値をそれぞれ代入してグラフ G用する.の全域木の個数を求めると，8 個であった. また全域木の個シルベスターの慣性律数はグラフ G のラプラシアン行列から第 (5,5) 成分の余因

A を対称行列，S を正則行列とし，B = S T AS とおくとA と B の正の固有値の数と A と B の負の固有値の数は等しい.

子からも同様に 8 個と求められた. このことから，あるグ修正コレスキー分解
対称行列 A の首座小行列式 δk が全て 0 でないならば

A = LDLT D:対角行列，L:対角成分が 1 の下三角行列と一意に分解できる. 上記した二つの定理を合わせると以下のことが言える. 対称行列 A の正の固有値の個数は修正コレスキー分解 (A ＝ LDLT ) の D の正の成分の個数にに等しい.

ラフに対応する隣接行列，ラプラシアン行列を導き，それぞれの固有値を求めることで，グラフの性質がわかった.

参考文献[1] Chris.Godsil，Gordon.F.Royle:
Theory 2001 13.2 Trees p.52

Algebraic Graph[2] 竹中淑子: 線形代数的グラフ理論，培風館，1989.
[3] 仁平政一・西尾義典: グラフ理論序説，プレアデス出
版，2005.