Sunday, December 2, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (8)


隣接行列

行列は数を二次元のます目上に並べたものである.これは数の表のように見える.ある規則で数を並べると,それがグラフを示すことと同じことになる.それを説明しよう.行列はグラフを表現するだけではなく,さらにいろいろなことができるのだが,ここでは特にグラフの表現をすることに集中して説明する.行列に関してもっと詳しく知りたい人には,文献 [1] をお勧めする.

行列について述べる動機はグラフを記述することにある.ここでいうグラフを表現する方法の一つとして隣接行列がある.ここでその定義を述べておこう.
Definition of adjacency matrix: n 個の点を持つグラフは \(n \times n\) の大きさの隣接行列で表現することができる.ここで,点\(i\) と点 \(j\) 間に有向辺がある場合,行列の成分 \(a_{i,j}\) を \(1\) とし,辺がない場合には \(0\) とする.
これだけである.つまり隣接する点(= 辺で接続されている点)の要素を 1,そうでない要素を 0 とするような行列を隣接行列と呼ぶ.

例として人間関係のグラフを考え,好きか嫌いかの関係を隣接行列で示そう.好きという関係がある場合には点の間に辺を置くとここでは決める.嫌いな場合に辺を置くとしても良いが,私は嫌いな関係よりも好きな関係を知りたいので,今回は好きな関係とする.注意して欲しいのはこういう部分は私が勝手に決めることができるということである.これは事実とかではなくて,問題を解こうとしている人が矛盾が起きない限り,勝手に決めることができる.もし私が,「定義する」とか「仮定する」とか「と,考えてみよう」と言ったら,それは私が決めたことであって,読者には賛成してもらいたいと思っている.もし読者が賛成しない場合,その後の議論は意味をなさない.

次回は具体的なグラフと隣接行列の例としてアリスに登場してもらい,その人間関係を示そう.

参考文献


[1] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition'', Wellesley-Cambridge Press,  2009

No comments:

Post a Comment