学習目標
- グラフ，点，辺の定義を理解する．
- 無向グラフと有向グラフの違いを理解する．
- 次数，出次数，入次数を求めることができる．
- パスとその長さの定義を理解する．
- 有向非巡回グラフ（DAG）の定義を理解し，トポロジカルオーダーを求めることができる．
グラフとは
グラフ（graph）は，点（vertex）の集合 V と辺（edge）の集合 E から構成され，G=(V,E) で表される．
グラフは，無向グラフ（undirected graph）と有向グラフ（directed graph）に分けられる．
無向グラフ
無向グラフは，辺に方向がないグラフである．辺は，2つの点からなる集合として表される．
例 6.1 (無向グラフの例) 点の集合 V と辺の集合 E を
\begin{aligned}
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\}\}
\end{aligned}
とすると，G=(V,E) は無向グラフである．図 6.1 はこのグラフを表している．
コード
import networkx as nx
import matplotlib.pyplot as plt
def draw_graph(G, pos):
"""グラフ G を座標 pos に従って描画する．
有向グラフの場合は，辺を矢印で表す．
"""
# 点のラベルを LaTeX 形式に変換
labels = {i: rf"$v_{i}$" for i in G.nodes()}
arrow_options = {"arrowstyle": "-|>", "arrowsize": 12} if G.is_directed() else {}
fig, ax = plt.subplots(figsize=(5, 3.5))
nx.draw_networkx(
G,
pos,
labels=labels,
node_color="white",
edgecolors="black",
linewidths=1.0,
node_size=450,
font_size=11,
width=1.0,
ax=ax,
**arrow_options,
)
ax.set_aspect("equal")
ax.margins(0.1)
ax.axis("off")
plt.show()
# グラフの作成（点を番号で定義）
G = nx.Graph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])
# 点の座標を固定
pos = {1: (0, 1), 2: (1.4, 1), 3: (1.4, 0), 4: (0, 0)}
draw_graph(G, pos)
グラフ 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 である．
点 v に隣接する点を v の隣接点（neighbor）という．点 v の隣接点の集合 \mathcal{N}(v) は，
\mathcal{N}(v) = \{u \in V \mid \{v, u\} \in E\}
で定義される．例 6.1 において，\mathcal{N}(v_1) = \{v_2, v_3, v_4\} である．
有向グラフ
有向グラフは，辺に方向があるグラフである．辺は，2つの点の順序対として表される．
例 6.2 (有向グラフの例) 点の集合 V と辺の集合 E を
\begin{aligned}
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)\}
\end{aligned}
とすると，G=(V,E) は有向グラフである．図 6.2 はこのグラフを表している．
コード
# グラフの作成（点を番号で定義）
G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)])
# 点の座標を固定（無向グラフの例と同じ配置）
pos = {1: (0, 1), 2: (1.4, 1), 3: (1.4, 0), 4: (0, 0)}
draw_graph(G, pos)
有向グラフ G = (V, E) において，点 v から出る辺の数を出次数（outdegree）といい，点 v に入る辺の数を入次数（indegree）という．例 6.2 の場合，v_1 の出次数は 2，入次数は 1 である．
辺 (v, u) において，u を v の後続点（successor），v を u の先行点（predecessor）という． 点 v の後続点の集合 \mathcal{S}(v) と先行点の集合 \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 を満たし，v_{i_1}, v_{i_2}, \ldots, v_{i_k} がすべて異なるものをいう．パスの長さ（length）は，パスに含まれる辺の数である．例 6.2 において，(v_1, v_2, v_3, v_4) は長さ 3 のパスである．一方，(v_1, v_3, v_4, v_1, v_2) は v_1 を2回含むため，パスではない．
閉路（cycle）とは，点の列 C = (v_{i_1}, v_{i_2}, \ldots, v_{i_k})（k > 1）であって，各 j = 1, 2, \ldots, k-1 に対して (v_{i_j}, v_{i_{j+1}}) \in E を満たし，v_{i_1} = v_{i_k} かつ v_{i_1}, v_{i_2}, \ldots, v_{i_{k-1}} がすべて異なるものをいう．例 6.2 において，(v_1, v_3, v_4, v_1) は閉路である．
有向非巡回グラフ
有向非巡回グラフ（directed acyclic graph, DAG）とは，閉路を含まない有向グラフである．例 6.2 のグラフは閉路 (v_1, v_3, v_4, v_1) を含むため，DAG ではない．
トポロジカルソート（topological sort）とは，DAG において，すべての辺 (v, u) \in E に対して v が u よりも前に来るように点を並べることである．トポロジカルソートによって得られる点の順序をトポロジカルオーダー（topological order）という．
例 6.3 (トポロジカルソートの例) 図 6.3 は DAG の例である．
コード
# グラフの作成（点を番号で定義）
G = nx.DiGraph()
G.add_edges_from([(1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5)])
# 点の座標を固定
pos = {1: (0, 0.5), 2: (1.2, 1), 3: (1.2, 0), 4: (2.4, 1), 5: (2.4, 0)}
draw_graph(G, pos)
点を (v_1, v_2, v_3, v_4, v_5) の順に並べる．すべての辺 (v_i, v_j) \in E について i < j であるから，v_i は v_j よりも前に来る．したがって，この並べ方はトポロジカルソートの条件を満たす．
(v_1, v_3, v_2, v_4, v_5) の順に並べても，すべての辺 (v_i, v_j) \in E について v_i が v_j よりも前に来るため，トポロジカルソートの条件を満たす．このように，トポロジカルオーダーは一意に定まるとは限らない．
一方，(v_1, v_2, v_4, v_3, v_5) の順では，辺 (v_3, v_4) について v_4 が v_3 よりも前に来るため，トポロジカルソートの条件を満たさない．
まとめ
- グラフは点の集合 V と辺の集合 E から構成され，G = (V, E) と表される．
- 無向グラフの辺は2つの点からなる集合であり，有向グラフの辺は2つの点の順序対である．
- 点 v に接続する辺の数を次数と呼ぶ．有向グラフでは，v から出る辺の数を出次数，v に入る辺の数を入次数と呼ぶ．
- 無向グラフでは，点 v の隣接点の集合を \mathcal{N}(v) と表す．
- 有向グラフの辺 (v, u) に対して u を v の後続点，v を u の先行点と呼ぶ．点 v の後続点の集合を \mathcal{S}(v)，先行点の集合を \mathcal{P}(v) と表す．
- パスは，各点から次の点へ向かう辺が存在し，すべての点が異なる点の列である．その長さはパスに含まれる辺の数である．
- 閉路は，ある点から辺をたどり，途中で同じ点を2度通ることなく出発点に戻る点の列である．閉路を含まない有向グラフを有向非巡回グラフ（DAG）と呼ぶ．
- DAG の点を，すべての辺 (v, u) について v が u よりも前に来るように並べることをトポロジカルソートと呼び，得られる点の順序をトポロジカルオーダーと呼ぶ．トポロジカルオーダーは一意とは限らない．
練習問題
練習 6.1 図 6.4 の DAG について，次の問いに答えよ．
コード
# グラフの作成（点を番号で定義）
G = nx.DiGraph()
G.add_edges_from([(1, 3), (2, 3), (3, 4), (3, 5), (4, 6), (5, 6)])
# 点の座標を固定
pos = {1: (0, 1), 2: (0, 0), 3: (0.8, 0.5), 4: (1.6, 1), 5: (1.6, 0), 6: (2.4, 0.5)}
draw_graph(G, pos)
- 各点の出次数と入次数を求めよ．
- 各点 v について，\mathcal{S}(v) と \mathcal{P}(v) を求めよ．
- トポロジカルオーダーをすべて求めよ．
