Ungerichtete Graphen/Homomorphismus/Einführung/Textabschnitt
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
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.