グラフ準同型 | Nola's Backyard

二つの有向グラフ

G=(V_G,E_G,s_G,t_G),\qquad H=(V_H,E_H,s_H,t_H)

を考える。ここで $V$ は頂点の集合、 $E$ は辺の集合、 $s,t:E\to V$ はそれぞれ各辺の始点と終点を与える写像とする。

$G$ から $H$ へのグラフ写像 $f:G\to H$ とは、次の二つの写像の組

f_V:V_G\to V_H,\qquad f_E:E_G\to E_H

であって、辺の始点と終点を保つものをいう。すなわち、

s_H\circ f_E=f_V\circ s_G, \qquad t_H\circ f_E=f_V\circ t_G

を満たす。

Hint

言い換えると、 $G$ の辺 $e:u\to v$ は、 $H$ の辺

f_E(e):f_V(u)\to f_V(v)

へ送られる。

単純グラフの場合

辺を頂点の組として扱う単純グラフでは、頂点写像 $f_V$ が隣接関係を保つという定義だけで表すことも多い。自由圏の普遍性で使うグラフ写像は、平行な辺も区別できるように、頂点写像と辺写像の両方を明示する上の定義である。