計算機科学のブログ

グラフの基礎 グラフの行列表現 行列による連結性の解析 隣接行列の要素を整数とした積

情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.4(グラフの行列表現)、7.4.3(行列による連結性の解析)、問7.21の解答を求めてみる。

隣接行列。

A G = [ 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 ]

連結性について。

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

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

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

f、gからa、b、c、d、eへの道は存在しない。

連結成分は{a, b, c, d, e}と{f, b}。