图同态

在图论中, 图同态是图之间的映射, 保持图中边和顶点的关系.

1定义

图同态

定义 1.1 (图同态). 对于图 $G_1=(V_1,E_1,d_1),G_2=(V_2,E_2,d_2)$, 它们之间的图同态, 记作 $f:G_1\to G_2$, 包含如下信息:

•	映射 $f:V_1\to V_2$,

•	映射 $f:E_1\to E_2$,

且满足如下条件:

•	对任何 $e\in E_1$, 若 $d_1(e)=(x,y)$, 则在 $⟨\genfrac{}{}{0ex}{}{V_2}{2}⟩$ 中有$$d_2(f(e))=(f(x),f(y)).$$

定义 1.2 (图范畴). 所有图及其间的图同态构成范畴 $\mathsf{Graph}$, 称为图范畴.

有向图同态

定义 1.3 (有向图同态). 对于有向图 $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_1\to V_2$,

•	映射 $f:E_1\to E_2$,

且满足如下条件:

•	对任何 $e\in E_1$, 都有$$\begin{array}{rl}{s}_2(f(e))& =f(s_1(e)),\\ t_2(f(e))& =f(t_1(e)).\end{array}$$

定义 1.4 (有向图范畴). 所有有向图及其间的有向图同态构成范畴 $\mathsf{Quiv}$, 称为有向图范畴或箭图范畴.

2性质

•	图范畴和有向图范畴中, 始对象是空图, 终对象是只有一个顶点、一条边的图.

•	有向图范畴有子对象分类子, 证明参见该文.

术语翻译

图同态 • 英文 graph homomorphism • 法文 morphisme de graphes • 俄文 гомоморфизм графов