Ungerichtete Graphen/Homomorphismus/Einführung/Textabschnitt

Definition

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ stets ${}\varphi (v)\varphi (v')\in F$ 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 ${}\varphi \colon G\rightarrow H$ notiert. Ein Untergraph ist im Wesentlichen dasselbe wie ein injektiver Graphhomomorphismus.

Lemma

Eine Hintereinanderschaltung von Graphhomomorphismen ist wieder ein Graphhomomorphismus.

Beweis

Siehe Aufgabe.

$\Box$

Definition

Es seien ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$ heißt Isomorphismus, wenn es einen Graphhomomorphismus

$\psi \colon H\longrightarrow G$

derart gibt, dass

${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

und

${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

gilt.

Definition

Zwei Graphen ${}G=(V,E)$ und ${}H=(W,F)$ heißen isomorph, wenn es einen Graphisomorphismus ${}\varphi \colon G\rightarrow H$ 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 ${}G=(V,E)$ und ${}H=(W,F)$ Graphen. Eine Abbildung ${}\varphi \colon V\rightarrow W$ mit der Eigenschaft, dass aus ${}vv'\in E$ entweder ${}\varphi (v)=\varphi (v')$ oder aber ${}\varphi (v)\varphi (v')\in F$ folgt, heißt schwacher Graphhomomorphismus.