グラフ（graph）は，点（vertex）の集合 \(V\) と辺（edge）の集合 \(E\) から構成され，\(G=(V,E)\) で表される．
グラフは，有向グラフ（directed graph）と無向グラフ（undirected graph）に分けられる．
無向グラフ
無向グラフは，辺の方向を持たないグラフである．辺は，2つの点の集合として表される．
例 7.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\}\}\) からなる．図 7.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=(4, 4))
# ノード描画
nx.draw_networkx_nodes(G, pos, node_color="black", node_size=120, edgecolors="black")
# エッジ描画
nx.draw_networkx_edges(G, pos, edge_color="black", 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）という．例 7.1 の場合，\(v_1\) の次数は 3，\(v_2\) の次数は 2 である．
有向グラフ
有向グラフは，辺に方向があるグラフである．辺は，2つの点の順序対として表される．
例 7.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)\}\)からなる．図 7.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=(4, 4))
# ノード描画
nx.draw_networkx_nodes(G, pos, node_color="black", node_size=120, edgecolors="black")
# エッジ描画
nx.draw_networkx_edges(G, pos, edge_color="black", 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）という．例 7.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\}
\] で定義される．例 7.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）は，パスに含まれる辺の数である．
