二学期 知識情報工学実験 (分子情報工学コース)

補足説明

距離行列：
グラフ中の二つのノード間の「距離」は、 この２点を結ぶパスがあれば その中で最短なパスの長さで定義し、 もし２点を結ぶパスが存在しなければ ∞ と定義する。
各ノード間の距離の情報を要素として行列表現したものが、 「距離行列」である。 （距離行列は隣接行列のベキ乗から生成することができる）

生成法（ベキ乗による方法）：
  1. 距離行列Ｄの初期値を、隣接行列Ａとする。 （隣接行列中の１の要素は、距離１ ＝自明）
  2. ｋ＝２ とする。
  3. Ａ^ｋ を計算する。（＾ はベキ乗演算子）
  4. Ｄの非対角要素 ｄ（ｉ, ｊ）＝０で、 かつ 対応する Ａ^ｋの要素 ａ^ｋ（ｉ, ｊ）≠０ ならば、ｄ（ｉ, ｊ）＝ｋ とする。
  5. Ｄの非対角要素 ｄ（ｉ, ｊ）が全て決定する （０でなくなる）か、または ｋ＞ｍ（エッジ数）のとき 処理を終了する。
    （残った非対角のゼロ要素は、距離∞を表わす）
  6. そうでなければ、ｋ＝ｋ＋１ として、ステップ３へ戻る。

Sample Graph 　　 A(G) 

A-matrix :                                 D(1) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1|  0  1  0  0  0  1  1  0  0  0           1|  0  1  0  0  0  1  1  0  0  0
  2|  1  0  1  0  0  0  0  0  0  0           2|  1  0  1  0  0  0  0  0  0  0
  3|  0  1  0  1  0  0  0  0  0  0           3|  0  1  0  1  0  0  0  0  0  0
  4|  0  0  1  0  1  0  0  1  0  0           4|  0  0  1  0  1  0  0  1  0  0
  5|  0  0  0  1  0  1  0  0  0  0           5|  0  0  0  1  0  1  0  0  0  0
  6|  1  0  0  0  1  0  0  0  0  0           6|  1  0  0  0  1  0  0  0  0  0
  7|  1  0  0  0  0  0  0  0  0  0           7|  1  0  0  0  0  0  0  0  0  0
  8|  0  0  0  1  0  0  0  0  1  1           8|  0  0  0  1  0  0  0  0  1  1
  9|  0  0  0  0  0  0  0  1  0  0           9|  0  0  0  0  0  0  0  1  0  0
 10|  0  0  0  0  0  0  0  1  0  0          10|  0  0  0  0  0  0  0  1  0  0
				                                             
A^2 :				           D(2) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1|  3  0  1  0  1  0  0  0  0  0           1|  0  1  2  0  2  1  1  0  0  0
  2|  0  2  0  1  0  1  1  0  0  0           2|  1  0  1  2  0  2  2  0  0  0
  3|  1  0  2  0  1  0  0  1  0  0           3|  2  1  0  1  2  0  0  2  0  0
  4|  0  1  0  3  0  1  0  0  1  1           4|  0  2  1  0  1  2  0  1  2  2
  5|  1  0  1  0  2  0  0  1  0  0           5|  2  0  2  1  0  1  0  2  0  0
  6|  0  1  0  1  0  2  1  0  0  0           6|  1  2  0  2  1  0  2  0  0  0
  7|  0  1  0  0  0  1  1  0  0  0           7|  1  2  0  0  0  2  0  0  0  0
  8|  0  0  1  0  1  0  0  3  0  0           8|  0  0  2  1  2  0  0  0  1  1
  9|  0  0  0  1  0  0  0  0  1  1           9|  0  0  0  2  0  0  0  1  0  2
 10|  0  0  0  1  0  0  0  0  1  1          10|  0  0  0  2  0  0  0  1  2  0
				                                             
A^3 :				           D(3) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1|  0  4  0  2  0  4  3  0  0  0           1|  0  1  2  3  2  1  1  0  0  0
  2|  4  0  3  0  2  0  0  1  0  0           2|  1  0  1  2  3  2  2  3  0  0
  3|  0  3  0  4  0  2  1  0  1  1           3|  2  1  0  1  2  3  3  2  3  3
  4|  2  0  4  0  4  0  0  5  0  0           4|  3  2  1  0  1  2  0  1  2  2
  5|  0  2  0  4  0  3  1  0  1  1           5|  2  3  2  1  0  1  3  2  3  3
  6|  4  0  2  0  3  0  0  1  0  0           6|  1  2  3  2  1  0  2  3  0  0
  7|  3  0  1  0  1  0  0  0  0  0           7|  1  2  3  0  3  2  0  0  0  0
  8|  0  1  0  5  0  1  0  0  3  3           8|  0  3  2  1  2  3  0  0  1  1
  9|  0  0  1  0  1  0  0  3  0  0           9|  0  0  3  2  3  0  0  1  0  2
 10|  0  0  1  0  1  0  0  3  0  0          10|  0  0  3  2  3  0  0  1  2  0
				                                             
A^4 :				           D(4) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1| 11  0  6  0  6  0  0  2  0  0           1|  0  1  2  3  2  1  1  4  0  0
  2|  0  7  0  6  0  6  4  0  1  1           2|  1  0  1  2  3  2  2  3  4  4
  3|  6  0  7  0  6  0  0  6  0  0           3|  2  1  0  1  2  3  3  2  3  3
  4|  0  6  0 13  0  6  2  0  5  5           4|  3  2  1  0  1  2  4  1  2  2
  5|  6  0  6  0  7  0  0  6  0  0           5|  2  3  2  1  0  1  3  2  3  3
  6|  0  6  0  6  0  7  4  0  1  1           6|  1  2  3  2  1  0  2  3  4  4
  7|  0  4  0  2  0  4  3  0  0  0           7|  1  2  3  4  3  2  0  0  0  0
  8|  2  0  6  0  6  0  0 11  0  0           8|  4  3  2  1  2  3  0  0  1  1
  9|  0  1  0  5  0  1  0  0  3  3           9|  0  4  3  2  3  4  0  1  0  2
 10|  0  1  0  5  0  1  0  0  3  3          10|  0  4  3  2  3  4  0  1  2  0
				                                             
A^5 :				           D(5) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1|  0 17  0 14  0 17 11  0  2  2           1|  0  1  2  3  2  1  1  4  5  5
  2| 17  0 13  0 12  0  0  8  0  0           2|  1  0  1  2  3  2  2  3  4  4
  3|  0 13  0 19  0 12  6  0  6  6           3|  2  1  0  1  2  3  3  2  3  3
  4| 14  0 19  0 19  0  0 23  0  0           4|  3  2  1  0  1  2  4  1  2  2
  5|  0 12  0 19  0 13  6  0  6  6           5|  2  3  2  1  0  1  3  2  3  3
  6| 17  0 12  0 13  0  0  8  0  0           6|  1  2  3  2  1  0  2  3  4  4
  7| 11  0  6  0  6  0  0  2  0  0           7|  1  2  3  4  3  2  0  5  0  0
  8|  0  8  0 23  0  8  2  0 11 11           8|  4  3  2  1  2  3  5  0  1  1
  9|  2  0  6  0  6  0  0 11  0  0           9|  5  4  3  2  3  4  0  1  0  2
 10|  2  0  6  0  6  0  0 11  0  0          10|  5  4  3  2  3  4  0  1  2  0
				                                             
A^6 :				           D(6) :                            
   |  1  2  3  4  5  6  7  8  9 10            |  1  2  3  4  5  6  7  8  9 10
---+------------------------------         ---+------------------------------
  1| 45  0 31  0 31  0  0 18  0  0           1|  0  1  2  3  2  1  1  4  5  5
  2|  0 30  0 33  0 29 17  0  8  8           2|  1  0  1  2  3  2  2  3  4  4
  3| 31  0 32  0 31  0  0 31  0  0           3|  2  1  0  1  2  3  3  2  3  3
  4|  0 33  0 61  0 33 14  0 23 23           4|  3  2  1  0  1  2  4  1  2  2
  5| 31  0 31  0 32  0  0 31  0  0           5|  2  3  2  1  0  1  3  2  3  3
  6|  0 29  0 33  0 30 17  0  8  8           6|  1  2  3  2  1  0  2  3  4  4
  7|  0 17  0 14  0 17 11  0  2  2           7|  1  2  3  4  3  2  0  5  6  6
  8| 18  0 31  0 31  0  0 45  0  0           8|  4  3  2  1  2  3  5  0  1  1
  9|  0  8  0 23  0  8  2  0 11 11           9|  5  4  3  2  3  4  6  1  0  2
 10|  0  8  0 23  0  8  2  0 11 11          10|  5  4  3  2  3  4  6  1  2  0


[FINAL]
D-matrix :
   |  1  2  3  4  5  6  7  8  9 10
---+------------------------------
  1|  0  1  2  3  2  1  1  4  5  5
  2|  1  0  1  2  3  2  2  3  4  4
  3|  2  1  0  1  2  3  3  2  3  3
  4|  3  2  1  0  1  2  4  1  2  2
  5|  2  3  2  1  0  1  3  2  3  3
  6|  1  2  3  2  1  0  2  3  4  4
  7|  1  2  3  4  3  2  0  5  6  6
  8|  4  3  2  1  2  3  5  0  1  1
  9|  5  4  3  2  3  4  6  1  0  2
 10|  5  4  3  2  3  4  6  1  2  0

＜参考＞ ノード１からの距離のイメージ
Sample Graph
図１　隣接行列からの距離行列の生成過程
（合ってるかな？）

知識情報工学実験（分子情報工学コース）のページに戻る