Graph morphism

From Wikipedia, the free encyclopedia

In mathematics, a graph morphism in graph theory 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.
Retrieved from "http://en.wikipedia.org../../../g/r/a/Graph_morphism.html"