# Google Colab の場合は2行目のコメントを外して実行: ライブラリインストール(1回だけ)
# !pip install networkx matplotlib

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_edges_from([(1, 3), (1, 4), (2, 3), (2, 4), (4, 5)])

pos = {1: (0, 1), 2: (1, 1), 3: (0, 0), 4: (1, 0), 5: (2, 0.5)}
plt.figure(figsize=(5, 3))
nx.draw_networkx(G, pos, node_color='white', edgecolors='black', node_size=500)
plt.axis('off')
plt.tight_layout()
plt.show()

print('ノード集合 V =', sorted(G.nodes()))
print('エッジ集合 E =', sorted(G.edges()))

ノード集合 V = [1, 2, 3, 4, 5]
エッジ集合 E = [(1, 3), (1, 4), (3, 2), (4, 2), (4, 5)]

print('位数 |V| =', G.number_of_nodes())
print('サイズ |E| =', G.number_of_edges())
print('各ノードの次数:', dict(G.degree()))
print('次数の総和 =', sum(d for _, d in G.degree()), '= 2|E| =', 2 * G.number_of_edges())
print('連結か:', nx.is_connected(G))

位数 |V| = 5
サイズ |E| = 5
各ノードの次数: {1: 2, 3: 2, 4: 3, 2: 2, 5: 1}
次数の総和 = 10 = 2|E| = 10
連結か: True

H = G.copy()
H.remove_node(4)   # ノード4と、接続するエッジ(1,4)、(2,4)、(4,5)が消える
print('ノード4を除去:', sorted(H.nodes()), sorted(H.edges()))

H = G.copy()
H.remove_edge(1, 3)  # エッジだけ消え、ノード1、3は残る
print('エッジ(1,3)を除去:', sorted(H.nodes()), sorted(H.edges()))

ノード4を除去: [1, 2, 3, 5] [(1, 3), (3, 2)]
エッジ(1,3)を除去: [1, 2, 3, 4, 5] [(1, 4), (3, 2), (4, 2), (4, 5)]

# ケーニヒスベルクの橋(地区1〜4、橋7本。多重枝があるのでMultiGraphを使う)
K = nx.MultiGraph()
K.add_edges_from([(1, 3), (1, 3), (1, 2), (1, 2), (1, 4), (3, 4), (2, 4)])
print('各ノードの次数:', dict(K.degree()))
print('オイラーグラフか:', nx.is_eulerian(K))

各ノードの次数: {1: 5, 3: 3, 2: 3, 4: 3}
オイラーグラフか: False

# 道路網(エッジ: 始点、終点、長さ[m])
roads = [(1, 2, 100), (2, 3, 140), (2, 4, 130), (1, 3, 150), (1, 3, 250),
         (3, 4, 120), (3, 4, 250)]
R = nx.MultiGraph()
for u, v, w in roads:
    R.add_edge(u, v, weight=w)

pos = {1: (0, 0), 2: (1.2, 1.2), 3: (1.6, 0), 4: (3.2, 0)}
plt.figure(figsize=(6, 3.5))
nx.draw_networkx_nodes(R, pos, node_color='white', edgecolors='black', node_size=500)
nx.draw_networkx_labels(R, pos)
for i, (u, v, w) in enumerate(roads):
    rad = 0.25 if (u, v) in [(1, 3), (3, 4)] and i in [4, 6] else 0.0
    nx.draw_networkx_edges(R, pos, edgelist=[(u, v)],
                           connectionstyle=f'arc3,rad={rad}')
plt.axis('off')
plt.tight_layout()
plt.show()

print('各ノードの次数:', dict(R.degree()))
print('道路の総延長:', sum(w for _, _, w in roads), '[m]')
print('オイラーグラフか:', nx.is_eulerian(R))

各ノードの次数: {1: 3, 2: 3, 3: 5, 4: 3}
道路の総延長: 1140 [m]
オイラーグラフか: False

# 最小の組合せに対応する2本を複製してオイラーグラフにする
R2 = R.copy()
R2.add_edge(1, 2, weight=100)
R2.add_edge(3, 4, weight=120)
print('複製後の次数:', dict(R2.degree()))
print('オイラーグラフか:', nx.is_eulerian(R2))

route = [u for u, v in nx.eulerian_circuit(R2, source=1)] + [1]
print('一筆書きルート:', ' -> '.join(map(str, route)))
print('総距離:', sum(w for _, _, w in roads) + 100 + 120, '[m]')

複製後の次数: {1: 4, 2: 4, 3: 6, 4: 4}
オイラーグラフか: True
一筆書きルート: 1 -> 3 -> 4 -> 3 -> 4 -> 2 -> 3 -> 1 -> 2 -> 1
総距離: 1360 [m]

INF = float('inf')

# エッジ: (始点, 終点, コスト)
E = [(1, 2, 25), (1, 3, 10), (2, 3, 5), (2, 4, 20), (5, 2, 5),
     (3, 4, 35), (3, 5, 5), (3, 6, 20), (5, 4, 30), (5, 6, 10),
     (5, 7, 40), (4, 7, 10)]
n = 7
s = 1

# コスト行列(d[i][j] = エッジ(i,j)のコスト、なければ∞)
d = [[INF] * (n + 1) for _ in range(n + 1)]
for u, v_, w in E:
    d[u][v_] = w

# STEP1
v = [INF] * (n + 1)
p = [0] * (n + 1)
v[s] = 0
M = set(range(1, n + 1)) - {s}
i = s

while True:
    # STEP2: ノードi から行けるノードの暫定コストを更新
    for j in M:
        if d[i][j] < INF and v[j] > v[i] + d[i][j]:
            v[j] = v[i] + d[i][j]
            p[j] = i
    # STEP3: 暫定コスト最小のノードを確定
    j0 = min(M, key=lambda j: v[j])
    # STEP4
    M.remove(j0)
    if not M:
        break
    i = j0

print('最短コスト v =', v[1:])
print('直前ノード p =', p[1:])

# p をたどって最短経路を復元
route = [7]
while route[-1] != s:
    route.append(p[route[-1]])
route.reverse()
print('ノード1から7への最短経路:', ' -> '.join(map(str, route)), '(コスト', v[7], ')')

最短コスト v = [0, 20, 10, 40, 15, 25, 50]
直前ノード p = [0, 5, 1, 2, 3, 5, 4]
ノード1から7への最短経路: 1 -> 3 -> 5 -> 2 -> 4 -> 7 (コスト 50 )

D = nx.DiGraph()
D.add_weighted_edges_from(E)
dist, path = nx.single_source_dijkstra(D, s)
print('networkx の最短コスト:', [dist[j] for j in range(1, n + 1)])
print('networkx の最短経路(1から7):', path[7])
print('自作実装と一致:', [dist[j] for j in range(1, n + 1)] == v[1:] and path[7] == route)

networkx の最短コスト: [0, 20, 10, 40, 15, 25, 50]
networkx の最短経路(1から7): [1, 3, 5, 2, 4, 7]
自作実装と一致: True

C = nx.Graph()
C.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1)])
A = nx.to_numpy_array(C, nodelist=[1, 2, 3, 4], dtype=int)
print(A)

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

組合せ	追加距離 [m]
{1, 2} と {3, 4}	100 + 120 = 220
{1, 3} と {2, 4}	150 + 130 = 280
{1, 4} と {2, 3}	230 + 140 = 370

反復	確定するノード	$v = (v_1, \dots, v_7)$
1	1	$(0, 25, 10, \infty, \infty, \infty, \infty)$
2	3	$(0, 25, 10, 45, 15, 30, \infty)$
3	5	$(0, 20, 10, 45, 15, 25, 55)$
4	2	$(0, 20, 10, 40, 15, 25, 55)$
5	6	$(0, 20, 10, 40, 15, 25, 55)$
6	4	$(0, 20, 10, 40, 15, 25, 50)$
7	7	終了

グラフ理論入門¶

1. グラフとは¶

2. 基本用語¶

3. 部分グラフとグラフの操作¶

4. 一筆書きとオイラーグラフ¶

4.1 応用: ごみ収集ルート¶

5. 最短経路問題とダイクストラ法¶

5.1 例題¶

6. 隣接行列¶

7. 道路ネットワークへの応用¶

8. 注意事項¶