グラフの基礎 グラフの行列表現 行列による連結性の解析 新幹線の路線図、隣接行列
情報系のための離散数学 (猪股 俊光 (著)、南野 謙一 (著)、共立出版)の第7章(グラフの基礎)、7.4(グラフの行列表現)、7.4.3(行列による連結性の解析)、問7.20の解答を求めてみる。
- 東京
- 山形
- 福島
- 秋田
- 盛岡
- 新青森
隣接行列。
連結行列。
連結性について。
コード
#!/usr/bin/env python3
import numpy as np
a1 = np.array([
[0, 0, 1, 0, 0, 0],
[0, 0, 1, 0, 0, 0],
[1, 1, 0, 0, 1, 0],
[0, 0, 0, 0, 1, 0],
[0, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 1, 0]
])
def f(o):
if o != 0:
return 1
return 0
a = a1
vectorize = np.vectorize(f)
for n in range(2, 6):
an = a1
for _ in range(n):
an = an.dot(a1)
an = vectorize(an)
print(f'a{n}')
print(an)
a += an
a = vectorize(a)
print('a')
print(a)
print('\na1')
print(a1)
print('a*')
print(a)
入出力結果(Terminal, Zsh)
% ./sample20.py
a2
[[0 0 1 1 0 1]
[0 0 1 1 0 1]
[1 1 0 0 1 0]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[1 1 0 0 1 0]]
a
[[0 0 1 1 0 1]
[0 0 1 1 0 1]
[1 1 0 0 1 0]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[1 1 0 0 1 0]]
a3
[[1 1 0 0 1 0]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[0 0 1 1 0 1]
[1 1 0 0 1 0]
[0 0 1 1 0 1]]
a
[[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]]
a4
[[0 0 1 1 0 1]
[0 0 1 1 0 1]
[1 1 0 0 1 0]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[1 1 0 0 1 0]]
a
[[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]]
a5
[[1 1 0 0 1 0]
[1 1 0 0 1 0]
[0 0 1 1 0 1]
[0 0 1 1 0 1]
[1 1 0 0 1 0]
[0 0 1 1 0 1]]
a
[[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]]
a1
[[0 0 2 1 0 1]
[0 0 2 1 0 1]
[2 2 0 0 2 0]
[1 1 0 0 2 0]
[0 0 2 2 0 2]
[1 1 0 0 2 0]]
a*
[[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]
[1 1 1 1 1 1]]
%
どの駅も長くて3つの駅で行き来できる。