計算機科学のブログ

グラフの基礎 有効グラフ、隣接行列、連結行列

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、章末問題の7.5の解答を求めてみる。

  • 駅東口
  • 県庁前
  • 中央公園
  • 図書館
  • バスセンター
  • 病院前

隣接行列。

[ 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 ]

連結行列。

コード、入出力結果(Wolfram Language, Jupyter Notebook)

A = {{0, 0, 0, 0, 0, 0},
     {1, 0, 0, 0, 0, 0},
     {0, 1, 0, 0, 0, 0},
     {0, 1, 0, 0, 0, 0},
     {0, 0, 1, 1, 0, 1},
     {0, 0, 0, 0, 0, 0}}

{{0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, 
 
>   {0, 0, 1, 1, 0, 1}, {0, 0, 0, 0, 0, 0}}
A // TraditionalForm
Output
{{1, 0, 0, 0, 0, 0},
 {0, 1, 0, 0, 0, 0},
 {0, 0, 1, 0, 0, 0},
 {0, 0, 0, 1, 0, 0},
 {0, 0, 0, 0, 1, 0},
 {0, 0, 0, 0, 0, 1}} +
Dot[A] +
Dot[A, A] +
Dot[A, A, A] +
Dot[A, A, A, A] +
Dot[A, A, A, A, A]

{{1, 0, 0, 0, 0, 0}, {1, 1, 0, 0, 0, 0}, {1, 1, 1, 0, 0, 0}, {1, 1, 0, 1, 0, 0}, 
 
>   {2, 2, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 1}}
% // TraditionalForm
Output