Der Isomorphiebegriff

Wir wollen nun allgemein zwei beliebige Graphen

G₁ = (E₁, K₁) und G₂ = (E₂, K₂)

isomorph oder strukturgleich nennen, wenn sie sich im Sinne der obigen Diskussion nur durch die Namen ihrer Ecken unterscheiden. Wie fassen wir diese Anschauung in eine präzise Definition? Die Umbenennung der Ecken wird durch eine Bijektion f von E₁ nach E₂ gegeben, das ist relativ problemlos. Aber wie bringen wir zum Ausdruck, dass die Bijektion korrekt ist? Alle graphentheoretischen Eigenschaften sollen wechselseitig erhalten bleiben, etwa:

(1)	In G₁ gilt d(a) = 5 genau dann, wenn d(f (a)) = 5 in G₂.

(2)	Die Ecke a ist genau dann die Ecke eines Dreiecks in G₁, wenn f (a) die Ecke eines Dreiecks in G₂ ist.

(3)	G₁ ist genau dann ein Kreis, wenn G₂ ein Kreis ist.

(4)	G₁ ist genau dann bipartit, wenn G₂ bipartit ist.

(5)	G₁ und G₂ haben die gleiche Größe (Anzahl der Kanten).

Die Definition der Isomorphie soll möglichst einfach sein und nicht aus einer langen Liste von Erhaltungseigenschaften bestehen, die in der Praxis schwer zu überprüfen ist und sich am Ende als unvollständig herausstellt. Um die entscheidende Bedingung zu finden, beobachten wir, dass ein Graph lediglich aus Ecken und Kanten besteht und sich alles Weitere wie Grad, Dreieck, Kreis usw. daraus ableitet. Die Ecken haben wir durch die Forderung der Bijektivität der Übersetzungsfunktion f schon berücksichtigt, die Kanten dagegen noch gar nicht. Es liegt nahe, zu fordern, dass f Kanten respektiert: f übersetzt eine Kante von G₁ in eine Kante von G₂, und ebenso bleibt das Fehlen einer Kante gewahrt. Wir definieren also:

Definition (Isomorphie, Isomorphismus)

Zwei Graphen G₁ = (E₁, K₁) und G₂ = (E₂, K₂) heißen isomorph, falls eine Abbildung f : E₁ → E₂ existiert mit den Eigenschaften:

(a)	f : E₁ → E₂ ist bijektiv.(Eckenbedingung)

(b)	Für alle a, b  ∈  E₁ gilt: ab  ∈  K₁ genau dann, wenn f (a)f (b)  ∈  K₂.(Kantenbedingung)

Eine derartige Abbildung f : E₁ → E₂ heißt ein Isomorphismus von G₁ nach G₂ oder zwischen G₁ und G₂.

Sind G₁ und G₂ isomorph, so schreiben wir G₁ ≅ G₂. Weiter schreiben wir f : G₁ ≅ G₂, falls f ein Isomorphismus von G₁ nach G₂ ist.

Beispiele

(1)	Haben G₁ und G₂ jeweils genau eine Ecke, so gilt G₁ ≅ G₂.

(2)	Haben G₁ und G₂ jeweils genau zwei Ecken, so sind G₁ und G₂ genau dann isomorph, wenn sie beide die einzig mögliche Kante enthalten oder beide diese Kante nicht enthalten.

(3)	Die vollständig bipartiten Graphen K_3, 2 und K_{2, 3} sind isomorph. Ein Isomorphismus ist gegeben durch f : { 1, …, 5 } → { 1, …, 5 } mit f (1) = 3, f (2) = 4, f (3) = 5, f (4) = 1, f (5) = 2. Die isomorphen Graphen K_3, 2 (links) und K_{2, 3} (rechts)

(4)	Die beiden folgenden Graphen sind isomorph, und f : E₁ → E₂ ist ein Isomorphismus: Offenbar ist f bijektiv. Dass f die Kantenbedingung erfüllt, lässt sich mit einiger Mühe „Kante für Kante“ überprüfen.

(5)

Die Äquivalenz „genau dann, wenn“ in der Kantenbedingung kann nicht zu „impliziert“ abgeschwächt werden. Ist G₁ = ({ 1, …, n }, ∅) und G₂ = K_n für ein n ≥ 2, so ist die Identität auf der Menge { 1, …, n } bijektiv und für alle a, b  ∈  E₁ gilt:

ab  ∈  K₁ impliziert f (a)f (b)  ∈  K₂.

Die beiden Graphen sind aber nicht isomorph.

Das letzte Beispiel zeigt, dass die Kantenbedingung nicht nur besagt, dass f Kanten erhält. Sie besagt stärker, dass sowohl Kanten und als auch Nichtkanten erhalten bleiben. Etwas salopp können wir sie so formulieren:

Ein Isomorphismus übersetzt Kanten (in beiden Richtungen).