グラフの隣接行列では結ぶ辺の有無を（０，１）で表したものが一般的である．すなわち，

　　結ぶ辺があるとき・・・１

　　結ぶ辺がないとき・・・０

　　それ自身のとき・・・・０

である．

　たとえば，

　　１　３　２

　　・−・−・

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

　　　　［０，０，１］

　　Ｂ＝［０，０，１］

　　　　［１，１，０］

となる．（１，２）要素は０であるから１←→２を結ぶ道はないが，（１，３）は１であるから１←→３を結ぶ道が存在するというわけである．また，それ自身のとき０であるから，主対角線要素はすべて０となる．このようにグラフは行列の形で表現できるので，グラフ論は行列論とみなすこともできるのである．

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

【２】隣接行列の固有値

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

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

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

　　　　｜　λ，　０，−１｜

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

　　　　｜−１，−１，　λ｜

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

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

　　１　２　３

　　・−・−・

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

　　　　［０，１，０］

　　Ｂ＝［１，０，１］

　　　　［０，１，０］

となるから

　　　　｜　λ，−１，　０｜

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

　　　　｜　０，−１，　λ｜

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

　　Σλi＝０

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

　　｜λ｜≦Δ

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

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

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

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

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

であることがわかる．

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