Graph morphism

A graph morphism assigns the nodes and edges of a given graph to the nodes and edges of another graph while the shape of the original graph is preserved. In the case of labeled graphs the node and edge labeling is preserved too. Mathematically a graph morphism is a pair of functions, where one of these functions is a node mapping and the other one is an edge mapping.

In termini of labeled directed multigraphs a graph morphism is defined as follows: Given two labeled directed multigraphs $G=(\Sigma _{V},\Sigma _{E},V_{G},E_{G},s_{G},t_{G},\ell _{V_{G}},\ell _{E_{G}})$ and $H=(\Sigma _{V},\Sigma _{E},V_{H},E_{H},s_{H},t_{H},\ell _{V_{H}},\ell _{E_{H}})$. Then a graph morphism is a pair of functions $\varphi =(\varphi _{V}\colon V_{G}\to V_{H},\varphi _{E}\colon E_{G}\to E_{H})$ with

• $s_{H}\circ \varphi _{E}=\varphi _{V}\circ s_{G}$ and $t_{H}\circ \varphi _{E}=\varphi _{V}\circ t_{G}$, which denotes the preservation of the shape.
• $\ell _{V_{G}}=\ell _{V_{H}}\circ \varphi _{V}$ and $\ell _{E_{G}}=\ell _{E_{H}}\circ \varphi _{E}$, which denotes the preservation of the node and edge labeling.