Ein Homomorphismus ist eine Abbildung zwischen zwei Graphen desselben Typs (gerichtet / ungerichtet).
Definition:
Seien \(G_1 = (V_1, E_1)\) und \(G_2 = (V_2, E_2)\) zwei ungerichtete Graphen. Eine Abbildung \(f: V_1 \to V_2\) heißt Homomorphismus zwischen \(G_1\) und \(G_2\), wenn gilt: Ist \(\{u, v\}\) eine Kante von \(G_1\), dann ist \(\{f(u), f(v)\}\) eine Kante von \(G_2\).
Beispiel:
Seien \(G_1\) und \(G_2\) zwei Graphen:
G1: G2:
0----1 f
-----> 4----5
2----3
Ein Beispiel für einen Homomorphismus \(f\) von \(G_1\) nach \(G_2\) ist:
\(f(0) = f(2) = 4,\quad f(1) = f(3) = 5\).
Folgende Behauptungen sind wahr:
\(\{0, 1\}\) ist eine Kante von \(G_1\), also ist \(\{f(0), f(1)\} = \{4, 5\}\) eine Kante von \(G_2\).
\(\{2, 3\}\) ist eine Kante von \(G_1\) ist, also ist \(\{f(2), f(3)\} = \{4, 5\}\) eine Kante von \(G_2\).
Daher ist \(f\) ein Homomorphismus von \(G_1\) nach \(G_2\).
Neben den Homomorphismen zwischen ungerichteten Graphen gibt es auch Homomorphismen zwischen gerichteten Graphen, Graphen mit Mehrfachkanten, …
Weitere Informationen.