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

隣接行列

行列は数を二次元のます目上に並べた表である．ある規則で数を並べると，それがグラフを示すことと同じことになるので，ここで述べる．つまり動機はグラフを記述することにある．そのようにグラフを表現する方法の一つとして隣接行列がある．ここでその定義を述べておこう．行列に関して簡単な紹介を付録 A に記しておく．さらに行列に関して知りたい読者には文献[7]を参照して欲しい．

Definition: 隣接行列は N 個の点を持つグラフを表現するものであり，\(N \times N\) の大きさを持つ．ここで，点\(i\) と点 \(j\) 間に有向辺がある場合，行列の成分 \(a_{i,j}\) を \(1\) とし，辺がない場合には\(0\) とする．

これだけである．つまり隣接する点(= 辺で接続されている点)の要素を 1，そうでない要素を 0 とするような行列を隣接行列と呼ぶ．

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

次回は Alice に登場してもらって好き嫌いグラフを書いてみることにする．

文献

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