【３】重要なグラフのスペクトル

　行列と固有値，グラフとそれを表す固有値との間には密接な関係がある．冒頭のグラフ例で説明するが，グラフＧのスペクトルを重複度を含めて

　　Ｓｐｅｃ（Ｇ）＝［　√２，　０，−√２］

　　　　　　　　　　［　１，　　１，　　１］

と表すことにする．

(1)完全グラフ：位数ｋのグラフでどの２点も隣接しているとき完全グラフという．それには正ｋ角形＋すべての対角線をイメージすればよく，ｖ＝ｋ，ｅ＝kＣ2である．その隣接行列は

　　　　［０，１，・・・，１，１］

　　　　［１，０，・・・，１，１］

　　Ｂ＝［・・・・・・・・・・・］

　　　　［１，１，・・・，０，１］

　　　　［１，１，・・・，１，０］

したがって，固有多項式は

　　　　｜λ，−１，・・・，−１，−１｜

　　　　｜−１，λ，・・・，−１，−１｜

　　Φ＝｜・・・・・・・・・・・・・・｜

　　　　｜−１，−１，・・・，λ，−１｜

　　　　｜−１，−１，・・・，−１，λ｜

となる．

　これは巡回行列式であるから，ζを１の原始ｋ乗根（すなわちｋ乗してはじめて１になる複素数）とすると

　　Φ＝Π（λ−ζ^i−・・・−ζ^(k-1)i）　　(i=0~k-1)

で表される．(i=0~k-1)であるから右辺はｋ個の整式の積となり，Φ＝０はλに関するｋ次方程式となる．このことより

　　Ｓｐｅｃ（Ｇ）＝［ｋ−１，　−１］

　　　　　　　　　　［　１　，ｋ−１］

が得られる．

(2)閉路グラフ：正ｋ角形をイメージすればよく，ｖ＝ｋ，ｅ＝ｋである．その隣接行列は

　　　　［０，１，０，・・・，０，１］

　　　　［１，０，１，・・・，０，０］

　　Ｂ＝［０，１，０，・・・，０，０］

　　　　［・・・・・・・・・・・・・］

　　　　［１，０，０，・・・，１，０］

したがって，固有多項式は

　　　　｜λ，−１，０，・・・，０，−１｜

　　　　｜−１，λ，−１，・・・，０，０｜

　　Φ＝｜０，−１，λ，・・・・，０，０｜

　　　　｜・・・・・・・・・・・・・・・｜

　　　　｜−１，０，０，・・・，−１，λ｜

となる．

　これも巡回行列式であり，

　　Ｓｐｅｃ（Ｇ）＝［２ｃｏｓ（２πｉ／ｋ）］

　　　　　　　　　　［　　　　１　　　　　　］　　　(i=0~k-1)

(3)道： １　２　３・・・・・ｋ−１　ｋ

　　　　・−・−・−・−・−・−・−・

　この隣接行列は

　　　　［０，１，０，・・・，０，０］

　　　　［１，０，１，・・・，０，０］

　　Ｂ＝［０，１，０，・・・，０，０］

　　　　［・・・・・・・・・・・・・］

　　　　［０，０，０，・・・，１，０］

したがって，固有多項式は

　　　　｜λ，−１，０，・・・，０，０｜

　　　　｜−１，λ，−１，・・，０，０｜

　　Φ＝｜０，−１，λ，・・・，０，０｜

　　　　｜・・・・・・・・・・・・・・｜

　　　　｜０，０，０，・・・，−１，λ｜

となる．

　３重対角行列式より，

　　Ｓｐｅｃ（Ｇ）＝［２ｃｏｓ（２πｉ／（ｋ＋１））］

　　　　　　　　　　［　　　　　　１　　　　　　　　］　　　(i=0~k-1)

(4)完全２部グラフ：位数ｐ対位数ｑの総当たりをイメージしてもらいたい．結果だけ書くと

　　Ｓｐｅｃ（Ｇ）＝［　√ｐｑ，　０，　　−√ｐｑ］

　　　　　　　　　　［　１，　　ｐ＋ｑ−２，　　１］

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