Was ist ein Homomorphismus (Graphen)?

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.

de German
X