競プロ向けグラフの話

集合 V, E と関数 f: E \to V \times V の組 (V, E, f) をグラフという．

競プロでは有限のグラフを扱うので， \#V = n, \#E = m として全単射 I_v: \{ i \in \mathbb{N} \mid 0 \leq i < n \} \to V, I_e: \{ i \in \mathbb{N} \mid 0 \leq i < m \} \to E を考えることができる．

e \in E のうち f(e) = (v, v) であるようなようなものをループという． e_1, e_2 \in E であって e_1 \neq e_2 かつ f(e_1) = f(e_2) であるようなものを多重辺という．

ループと多重辺のないグラフを単純グラフという．多重辺がないので f は単射である．

E_1 \cap E_2 = \varnothing, E_1 \cup E_2 = E であるような E_1, E_2 と全単射 \mathrm{rev}: E_1 \to E_2 が存在して， e \in E_1 と v_1, v_2 \in V について f(e) = (v_1, v_2) \Rightarrow f(\mathrm{rev}(e)) = (v_2, v_1) が成り立つとき，無向グラフという．

f(e) = (v_1, v_2) であるような e について， \mathrm{from}(e) = v_1, \mathrm{to}(e) = v_2 とする．

関数 w: E \to \mathbb{R} を重みと呼ぶ．

グラフが単純であるとする． E に無効値 0 を追加した集合 E' = E \sqcup \{0\} を考え， g: V^2 \to E' を \forall (v_1, v_2) \in V^2, \forall e \in E, g(v_1, v_2) = e \Leftrightarrow f(e) = (v_1, v_2) を満たすように定める． n \times n 行列であって「i 行 j 列が 0」\Leftrightarrow「g(v_i, v_j) \notin E」を満たすものを隣接行列という．同じく n \times n 行列であって， g(v_i, v_j) = e \in E なら i 行 j 列が w(e) ， g(v_i, v_j) \notin E なら i 行 j 列が \infty であるようなものを重み付き隣接行列という．

各 v \in V について \mathrm{next}(v) = \mathrm{from}^{-1}(\{v\}) とする． v_1 \neq v_2 \Rightarrow \mathrm{next}(v_1) \cap \mathrm{next}(v_2) = \varnothing ， \bigcup_{v \in V} \mathrm{next}(v) = E である． \#\mathrm{next}(v) = k は自然数なので全単射 I_v: \{i \in \mathbb{N} \mid 0 \leq i < k\} \to \mathrm{next}(v) を考えることができる．各 v について \mathrm{to} \circ I_v からベクタを作り， 2 次元ベクタとして持ったものを隣接リストという．ここに w \circ I_v を加えたものを重み付き隣接リストという．