有向グラフの射
この記事では有向グラフの射という概念について定義と基本的な例を紹介します。
有向グラフ
まずは有向グラフの定義について復習しよう。有向グラフとは頂点と向きのついた辺からなる図形で、点と辺の繋がり具合のみに注目した概念であった。
有向グラフ$G$とは、集合$V$と集合$E$及び写像$s:E\to V$と写像$t:E\to V$からなる$4$つ組$G=(V,E,s,t)$のこと。
この定義において、$V$が頂点のなす集合、$E$が辺のなす集合で、$s$が各辺の始点を割り当てる写像、$t$が各辺の終点を割り当てる写像である。
この定義の解釈や例について詳しくは こちらの記事 をご覧ください。
有向グラフの射
この記事の本題である有向グラフの射について説明する。二つの有向グラフ$G, G'$を結びつける概念が有向グラフの射である。二つのグラフを結びつけることで、例えば既知のグラフから未知のグラフについての情報を得ることができる。
$G_1=(V_1,E_1, s_1, t_1), G_2=(V_2, E_2, s_2, t_2)$を有向グラフとする。
$f:G_1\to G_2$が有向グラフの射であるとは、写像$f_V:V_1\to V_2, f_E:E_1\to E_2$の組$f=(f_V, f_E)$であって、以下の図式を可換にするもの。
$$
\require{AMScd}
\begin{CD}
E_1 @>f_E>> E_2 \\
@Vs_1VV @VVs_2V \\
V_1 @>f_V>> V_2
\end{CD}
\hspace{30pt}
\begin{CD}
E_1 @>f_E>> E_2 \\
@Vs_1VV @VVs_2V \\
V_1 @>f_V>> V_2
\end{CD}
$$
$f_V$が頂点の対応を、$f_E$が辺の対応を記述する。また、図式の可換性が辺の繋がり具合を保った対応であることを保証する条件である。
つまり、$G_1$のある辺$e$を$f_E$により$G_2$の辺$e'$に対応させたとき、$e$の始点や終点が$f_V$により$e'$の始点や終点に対応する。
このことから、例えば$G_1$にあるループは$f$により$G_2$のループに対応することが保証される。
一方で、$G_1$のループでない辺が$G_2$のループに対応することは排除されない。
図式の可換性についての補足
この文脈においては、写像の等式を視覚的に表現したものだと思えばよい。
図式
$$
\require{AMScd}
\begin{CD}
E_1 @>f_E>> E_2 \\
@Vs_1VV @VVs_2V \\
V_1 @>f_V>> V_2
\end{CD}
$$
が可換であるとは、次の写像の等式
$$
f_V\circ s_1=s_2\circ f_E
$$
が成立することであり、これは任意の$e\in E_1$に対して
$$
f_V(s_1(e))=s_2(f_E(e))
$$
が成り立つということ。
有向グラフの言葉で言えば、$G_1$の全ての辺$e$について、$e$の始点を$f_V$でうつした$G_2$の頂点$f_V(s_1(e))$と$e$を$f_E$でうつした$G_2$の始点$s_2(f_E(e))$が一致するということを表す。
グラフの射はグラフ準同型とも呼ばれます。準同型の方が一般的な用語かもしれないのですが、今後圏論の話をしていくのでここでは射という言葉を用います。
具体例や図を使った説明については動画をご覧ください。（いずれこちらにも加筆します。）