Ungerichtete Graphen/Homomorphismus/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus stets folgt, heißt Graphhomomorphismus.

Ein Homomorphismus von Graphen ist einfach eine relationserhaltende Abbildung, er führt adjazente Knotenpunkte in adjazente Knotenpunkte über. Er wird kurz als notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.



Lemma

Eine Hintereinanderschaltung von Graphhomomorphismen ist wieder ein Graphhomomorphismus.

Beweis

Siehe Aufgabe.



Definition  

Es seien und Graphen. Ein Graphhomomorphismus heißt Isomorphismus, wenn es einen Graphhomomorphismus

derart gibt, dass

und

gilt.


Definition  

Zwei Graphen und heißen isomorph, wenn es einen Graphisomorphismus gibt.

Isomorphe Graphen sind hinsichtlich sämtlicher graphentheoretischen Eigenschaften als gleich anzusehen.

Gelegentlich braucht man die folgende Variante eines Graphhomomorphismus, insbesondere, wenn durch eine Kante verbundene Knotenpunkte auf einen Punkt abgebildet werden sollen.


Definition  

Es seien und Graphen. Eine Abbildung mit der Eigenschaft, dass aus entweder oder aber folgt, heißt schwacher Graphhomomorphismus.