■行列式の計算(その13)

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

 次数行列D={dij}とは

  dii=degi(次数),dij=0(i≠j)

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

    [1,0,0]

  D=[0,1,0]

    [0,0,2]

位数4の完全グラフでは

    [3,0,0,0]

  D=[0,3,0,0]

    [0,0,3,0]

    [0,0,0,3]

 また,グラフGのラプラシアンΔGを

  ΔG=次数行列D−隣接行列B

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

         [ 1, 0,−1]

  ΔG=D−B=[ 0, 1,−1]

         [−1,−1, 2]

位数4の完全グラフでは

    [0,1,1,1]

  B=[1,0,1,1]

    [1,1,0,1]

    [1,1,1,0]

より

     [3,−1,−1,−1]

  ΔG=[−1,3,−1,−1]

     [−1,−1,3,−1]

     [−1,−1,−1,3]

 そのスペクトルをSpec(ΔG)とすると,

(1)完全グラフ

  Spec(ΔG)=[ k, 0]

           [k−1,1]

(2)閉路グラフ

  Spec(ΔG)=[2−2cos(2πi/k)]

           [     1       ]   (i=1~k)

(3)道

  Spec(ΔG)=[2−2cos(πi/k)]

           [     1      ]   (i=1~k)

(4)完全2部グラフ

  Spec(ΔG)=[p+q, p,  q, 0]

           [ 1 ,q−1,p−1,1]

で与えられる.

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

  0≦μ≦k

となる.

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

  ΔG=単位行列I−推移行列P

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

===================================