Graph homomorphism
|
|
In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps
- vertices to vertices
- undirected edges to undirected edges or collapses the edge onto a vertex.
- directed edges to directed edges (without changing direction) or collapses the edge onto a vertex
| Contents |
Definition
A graph homomorphism <math>f<math> from a graph <math>G:=(V,E)<math> to a graph <math>G':=(V',E')<math> is a function
- <math>f:V \cup E \to V' \cup E'<math>
on the edges and vertices of <math>G<math> such that
- vertices of <math>G<math> go to vertices of <math>G'<math>,
- if <math>e<math> is an edge of <math>G<math> with endpoints <math>v<math> and <math>w<math> then either <math>f(e)<math> is an edge of <math>G'<math> with endpoints <math>f(v)<math> and <math>f(w)<math>, or <math>f(e)=f(v)=f(w)<math>, and
- if <math>e<math> is a directed edge of <math>G<math> from <math>v<math> to <math>w<math> then either <math>f(e)<math> is a directed edge of <math>H<math> from <math>f(v)<math> to <math>f(w)<math>, or <math>f(e)=f(v)=f(w)<math>.
The above definition works even when <math>G<math> and <math>G'<math> are allowed to have multiedges and loops. In the case of simple graphs, the definition can is slightly simpler: where an edge maps is determined by where its endpoints map.
Some authors use a stricter definition than the one given here, in which an edge is not allowed to map to a vertex. Thus, if the destination graph has no loops, adjacent vertices can't map to the same vertex.
If the homomorphism <math>f<math> is a bijection, then the inverse function is also a graph homomorphism, so <math>f<math> is a graph isomorphism. In this case, the two graphs are identical from the viewpoint of graph theory. Determining whether there is an isomorphism between two graphs is an important problem in computational complexity theory; see graph isomorphism problem.
Examples
The function
- <math>f:G \to K_1<math>
mapping a graph <math>G<math> to the complete graph with one vertex is a graph homomorphism.
Notes
In terms of graph coloring, a k-coloring of G, without restrictions, is equivalent to a homomorphism of G into Kk, the complete graph on k vertices. (Each vertex of <math>G<math> is colored according to which vertex of <math>K_k<math> it goes to.) As an extension of that analogy, a homomorphism of G into H is also sometimes called an H-coloring.
Properties
- Graph homomorphism preserve connectedness and diconnectedness.
- A graph H is a subgraph of G if and only if there exists a monomorphism <math>f:H\to G<math>.