【１】隣接行列のベキ乗

　この隣接行列を２乗すると

　　　　　［１，１，０］

　　Ｂ^2＝［１，１，０］

　　　　　［０，０，２］

となるが，このことは何を意味するのだろうか？　（１，２）要素は１，（３，３）は２であるが，これは長さ２の道の数に一致している．一般にＢ^nの（ｉ，ｊ）要素はｉ←→ｊの長さｎの道の数になっているのである．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】隣接行列の固有値

　位数ｋのグラフの固有値は隣接行列の固有値，すなわち，固有多項式

　　Φ＝ｄｅｔ（λＩ−Ｂ）＝０

の解λで与えられる．冒頭に掲げたグラフの固有多項式は

　　　　｜　λ，　０，−１｜

　　Φ＝｜　０，　λ，−１｜＝λ^3−２λ

　　　　｜−１，−１，　λ｜

で，固有値は０，±√２と計算される．

　グラフに異なるラベルを付けても固有値は同じになる．

　　１　２　３

　　・−・−・

のようにラベルしたグラフの隣接行列は

　　　　［０，１，０］

　　Ｂ＝［１，０，１］

　　　　［０，１，０］

となるから

　　　　｜　λ，−１，　０｜

　　Φ＝｜−１，　λ，−１｜＝λ^3−２λ

　　　　｜　０，−１，　λ｜

　固有値λはすべて実数でその和は０となる．

　　Σλi＝０

また，グラフが連結なとき，最大次数をΔとすると

　　｜λ｜≦Δ

となる．冒頭の例ではΔ＝２である．

　また，隣接行列Ｂの固有値をλ1，・・・，λkとすると，Ｂ^nの固有値は

　　λ1^n，・・・，λk^n

となる．このことから長さｎの道の数は

　　ｔｒ（Ｂ^n）＝Σλi^n

であることがわかる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝