【４】グラフのラプラシアン

　次数行列Ｄ＝｛ｄij｝とは

　　ｄii=ｄｅｇi（次数），ｄij=０(i≠j)

と定めたものである．たとえば，冒頭のグラフ例では

　　　　［１，０，０］

　　Ｄ＝［０，１，０］

　　　　［０，０，２］

位数４の完全グラフでは

　　　　［３，０，０，０］

　　Ｄ＝［０，３，０，０］

　　　　［０，０，３，０］

　　　　［０，０，０，３］

　また，グラフＧのラプラシアンΔＧを

　　ΔＧ＝次数行列Ｄ−隣接行列Ｂ

で定義する．冒頭のグラフでは

　　　　　　　　　［　１，　０，−１］

　　ΔＧ＝Ｄ−Ｂ＝［　０，　１，−１］

　　　　　　　　　［−１，−１，　２］

位数４の完全グラフでは

　　　　［０，１，１，１］

　　Ｂ＝［１，０，１，１］

　　　　［１，１，０，１］

　　　　［１，１，１，０］

より

　　　　　［３，−１，−１，−１］

　　ΔＧ＝［−１，３，−１，−１］

　　　　　［−１，−１，３，−１］

　　　　　［−１，−１，−１，３］

　そのスペクトルをＳｐｅｃ（ΔＧ）とすると，

(1)完全グラフ

　　Ｓｐｅｃ（ΔＧ）＝［　ｋ，　０］

　　　　　　　　　　　［ｋ−１，１］

(2)閉路グラフ

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

　　　　　　　　　　　［　　　　　１　　　　　　　］　　　(i=1~k)

(3)道

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

　　　　　　　　　　　［　　　　　１　　　　　　］　　　(i=1~k)

(4)完全２部グラフ

　　Ｓｐｅｃ（ΔＧ）＝［ｐ＋ｑ，　ｐ，　　ｑ，　０］

　　　　　　　　　　　［　１　，ｑ−１，ｐ−１，１］

で与えられる．

　位数ｋのグラフのラプラシアンΔの固有値をμとすると

　　０≦μ≦ｋ

となる．

［注］隣接行列でなく推移行列を使ってラプラシアンを定義することもある．

　　ΔＧ＝単位行列Ｉ−推移行列Ｐ

ラプラシアンの定義は文献によって異なる場合があるので注意を要する．

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