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

隣接行列とグラフのトポロジ

前回，隣接行列に関して説明したので，今回は隣接行列とグラフの関係を詳しく見ていきたい． 隣接行列はそれを見ればどのように点が接続されているかがわかる．接続されているかどうかだけを気にする場合，数学ではトポロジという言葉を使う．たとえば，Berlin の S-Bahn, U-Bahn の Web site にあるLiniennetz は実際に距離が近いかどうかではなく，電車が駅に行けるかどうかという図である．隣の駅までの距離はあまり関係なく，実際のBerlin の地図の上の線路とはずいぶん異なっている．しかし，トポロジ(=つながりの関係)は正しい． 

図 7 に戻ってみよう．ここには Alexanderplatz に接続されている駅が書かれている．

Figure 7: Graph example 2. Each node is a train station.

この図の隣接行列は以下のようになる．以下の行列には駅名の最初の4文字のみ示した．

\begin{eqnarray*} \begin{array}{ccccc} & \mbox{Wein.} & \mbox{Alex.} & \mbox{Hack.} & \mbox{Jann.} \\ \begin{array}{c} \\ \mbox{Wein.}\\ \mbox{Alex.}\\ \mbox{Hack.}\\ \mbox{Jann.}\\ \end{array} & \left[ \begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \\ \end{array} \right. & \begin{array}{c} 1\\ 0\\ 1\\ 1\\ \end{array} & \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{array} & \left. \begin{array}{c} 0\\ 1\\ 0\\ 0\\ \end{array} \right] \end{array} \end{eqnarray*}

 隣接行列の列の 1 の数はいくつの辺がその点から出ているかに対応する．たとえば，Weinmeisterstr の列だけを取り出すとそれは以下のようになる．

\begin{eqnarray*} \begin{array}{ccccc} \begin{array}{c} \mbox{Wein.} \end{array} & \left[ \begin{array}{c} 0 \\ \end{array} \right. & \begin{array}{c} 1\\ \end{array} & \begin{array}{c} 0\\ \end{array} & \left. \begin{array}{c} 0\\ \end{array} \right] \end{array} \end{eqnarray*}

1 の数は 1 である．つまり Weinmeisterstr から出ている辺の数は 1 である．この数を点の degree と言う．Alexanderplatz の場合，以下に示すように1 が 3 つ あるので degree は 3 である．

\begin{eqnarray*} \begin{array}{ccccc} \begin{array}{c} \mbox{Alex.} \end{array} & \left[ \begin{array}{c} 1 \\ \end{array} \right. & \begin{array}{c} 0\\ \end{array} & \begin{array}{c} 1\\ \end{array} & \left. \begin{array}{c} 1\\ \end{array} \right] \end{array} \end{eqnarray*}

図 7 で点の degree，つまり辺の数がどのようになっているか確認できるだろう． 

次回は隣接行列の演算がどのような意味を持っているかについても紹介しよう．