Zwei Graphen können zueinander 2 Homomorphismen haben ohne isomorph zu sein.
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\).
Seien \(G_1 = (V_1, E_1)\) und \(G_2 = (V_2, E_2)\) zwei ungerichtete Graphen. Eine bijektive Abbildung \(f: V_1 \to V_2\) heißt Isomorphismus zwischen \(G_1\) und \(G_2\), wenn gilt: \(\{u, v\}\) ist eine Kante von \(G_1\), genau dann wenn \(\{f(u), f(v)\}\) eine Kante von \(G_2\) ist.
Beispiel:
Seien \(G_1\) und \(G_2\) zwei Graphen:
G1: G2:
0----1 f
-----> 4----5
<-----
2----3 g
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\).
\(f\) ist ein Homomorphismus von \(G_1\) nach \(G_2\) weil gilt:
\(\{0, 1\} \in G_1 \Rightarrow \{f(0), f(1)\} = \{4, 5\} \in G_2\)
\(\{2, 3\} \in G_1 \Rightarrow \{f(2), f(3)\} = \{4, 5\} \in G_2\)
Ein Beispiel für einen Homomorphismus \(g\) von \(G_2\) nach \(G_1\) ist:
\(g(4) = 2,\quad g(5) = 3\).
\(g\) ist ein Homomorphismus von \(G_2\) nach \(G_1\) weil gilt:
\(\{4, 5\} \in G_2 \Rightarrow \{g(4), g(5)\} = \{2, 3\} \in G_1\)
Es gibt zwischen \(G_1\) und \(G_2\) in jede Richtung einen Homomorphismus, \(G_1\) und \(G_2\) sind aber nicht isomorph. Die Mengen der Kanten \(V(G_1)\) und \(V(G_2)\) sind nicht gleich mächtig. Daher gibt es keine bijektive Abbildung zwischen \(G_1\) und \(G_2\).
Weitere Informationen.