第03回 隣接行列のイ・イ・ト・コ・ロ
今回は隣接行列に絞って書く。というのも、この隣接行列というのは色々とアレンジしやすい。
補グラフ
例えば下のようなグラフ。
グラフGの、つながっていない点同士を結んで、つながっている部分は削除すると、補グラフが出来る。
ちなみに、この例のグラフは同型（頂点の次数がGとで等しい*1）なので、自己補グラフという特別な名前がついている。
さらには、これらのグラフを重ね合わせるとすべての点同士が結ばれている。このように、単純グラフ（多重辺やループが無いグラフ）で、すべての点が結ばれているグラフを完全グラフという。
Gとを行列で表してみると
このようになる。ループが無いので対角成分は同じとして、それ以外は0と1が反転しているだけだ。ということは、行列Gを用意しておけばGの補グラフは容易に生成できることがわかる。
重み付グラフ
各辺に重みのついたグラフ。辺に長さがあると考えても良い。このようなグラフを考えるとき、これまで"1"としていた部分に重みの値をそのまま入れることで容易に重み付グラフのデータを表現することが出来る。たとえば以下のようなグラフ
これを行列で表現してみると
のようになる。
有向グラフ
文字通り、向きのあるグラフ。辺を道と考えると、一方通行があるグラフということだ。
このように、辺の部分を矢印で書いたグラフを行列で表してみると、
となり、対角行列に対して対称ではなくなる。
もし、「一方通行」と「もともとつながっていない」ということを区別したければ
というように、0以外の値にするのも良いだろう。
また、グラフ理論の応用としてよく例に出されるGoogleのPageRankシステムでは、各列の合計値が1になる推移確率行列と呼ばれるものを使用している。この辺はSofware Design10月号のひなた先生(id:yaneurao)で簡単に説明されているので、読んでおくと参考になる。でももうすぐ11月号が出るから、はよ買わんと売り切れるでー（´ー｀）
つづく
