学習目標
- グラフ，点，辺の定義を理解する．
- 無向グラフと有向グラフの違いを理解する．
- 次数，出次数，入次数を求めることができる．
- パスとその長さの定義を理解する．
グラフとは
グラフ（graph）は，点（vertex）の集合 V と辺（edge）の集合 E から構成され，G=(V,E) で表される．
グラフは，有向グラフ（directed graph）と無向グラフ（undirected graph）に分けられる．
無向グラフ
無向グラフは，辺の方向を持たないグラフである．辺は，2つの点の集合として表される．
例 6.1 (無向グラフの例) グラフ
G = (\{v_1, v_2, v_3, v_4\}, \{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_1\},\{v_1,v_3\}\})
は，点の集合 V=\{v_1,v_2,v_3,v_4\} と辺の集合 E=\{\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_4\},\{v_4,v_1\},\{v_1,v_3\}\} からなる．図 6.1 はこのグラフを表している．
コード
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
# グラフの作成（頂点を番号で定義）
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])
# 頂点ラベルを LaTeX 形式に変換
labels = {i: rf"$v_{i}$" for i in G.nodes()}
# レイアウト（円形）
pos = nx.circular_layout(G)
# ラベルの位置を少し外側へ移動
label_pos = {}
for k, (x, y) in pos.items():
r = np.sqrt(x**2 + y**2) # 原点からの距離
scale = 1.15 # 外側に押し出す係数（調整可）
label_pos[k] = (x / r * scale, y / r * scale)
plt.figure(figsize=(5, 4))
# ノード描画
nx.draw_networkx_nodes(G, pos, node_color="#16212d", node_size=120, edgecolors="#16212d")
# エッジ描画
nx.draw_networkx_edges(G, pos, edge_color="#5b6b7c", width=1.2)
# 外側にラベル描画
nx.draw_networkx_labels(G, label_pos, labels, font_size=12, font_weight="regular")
plt.axis("off")
plt.show()
グラフ G = (V, E) において，e = \{v, u\} \in E を満たすとき，点 v と u は隣接（adjacent）しているといい，e は v と u を接続（incident）しているという．
点 v に接続している辺の数を，v の次数（degree）という．例 6.1 の場合，v_1 の次数は 3，v_2 の次数は 2 である．
有向グラフ
有向グラフは，辺に方向があるグラフである．辺は，2つの点の順序対として表される．
例 6.2 (有向グラフの例) グラフ
G = (\{v_1, v_2, v_3, v_4\}, \{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1),(v_1,v_3)\})
は，点の集合V=\{v_1,v_2,v_3,v_4\}と辺の集合E=\{(v_1,v_2),(v_2,v_3),(v_3,v_4),(v_4,v_1),(v_1,v_3)\}からなる．図 6.2 はこのグラフを表している．
コード
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
# グラフの作成（頂点を番号で定義）
G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])
# 頂点ラベルを LaTeX 形式に変換
labels = {i: rf"$v_{i}$" for i in G.nodes()}
# レイアウト（円形）
pos = nx.circular_layout(G)
# ラベルの位置を少し外側へ移動
label_pos = {}
for k, (x, y) in pos.items():
r = np.sqrt(x**2 + y**2) # 原点からの距離
scale = 1.15 # 外側に押し出す係数（調整可）
label_pos[k] = (x / r * scale, y / r * scale)
plt.figure(figsize=(5, 4))
# ノード描画
nx.draw_networkx_nodes(G, pos, node_color="#16212d", node_size=120, edgecolors="#16212d")
# エッジ描画
nx.draw_networkx_edges(G, pos, edge_color="#5b6b7c", width=1.2, arrowsize=15)
# 外側にラベル描画
nx.draw_networkx_labels(G, label_pos, labels, font_size=12, font_weight="regular")
plt.axis("off")
plt.show()
グラフ G = (V, E) において，点 v から出る辺の数を出次数（outdegree）といい，点 v に入る辺の数を入次数（indegree）という．例 6.2 の場合，v_1 の出次数は 2，入次数は 1 である．
辺 (v, u) において，u を v の successor，v を u の predecessor という． 点 v の successor の集合 \mathcal{S}(v) と predecessor の集合 \mathcal{P}(v) は，
\mathcal{S}(v) = \{u \in V \mid (v, u) \in E\},
\mathcal{P}(v) = \{u \in V \mid (u, v) \in E\}
で定義される．例 6.2 において，\mathcal{S}(v_1) = \{v_2, v_3\}，\mathcal{P}(v_1) = \{v_4\} である．
パス
G = (V, E) において，パス（path）P とは，点の組
P = (v_{i_1}, v_{i_2}, \ldots, v_{i_k})
であって，各 j = 1, 2, \ldots, k-1 に対して (v_{i_j}, v_{i_{j+1}}) \in E を満たすものをいう．パスの長さ（length）は，パスに含まれる辺の数である．
まとめ
- グラフは点の集合 V と辺の集合 E から構成され，G = (V, E) と表される．
- 無向グラフの辺は2つの点の集合であり，有向グラフの辺は2つの点の順序対である．
- 点 v に接続する辺の数を次数と呼ぶ．有向グラフでは，v から出る辺の数を出次数，v に入る辺の数を入次数と呼ぶ．
- 辺 (v, u) に対して u を v の successor，v を u の predecessor と呼び，それぞれの集合を \mathcal{S}(v)，\mathcal{P}(v) と表す．
- パスは隣接する点を順に並べた点の組であり，その長さはパスに含まれる辺の数である．
