Können 2 Graphen zueinander 2 Homomorphismen haben ohne isomorph zu sein?

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.

de German
X