Eigenschaften von isomorphen Graphen

Die Isomorphie zwischen Graphen besitzt, wie zum Beispiel die Kongruenzrelation modulo m der Zahlentheorie, die drei charakteristischen Eigenschaften der Gleichheit:

Satz (elementare Eigenschaften der Isomorphie)

Seien G₁, G₂, G₃ Graphen. Dann gilt:

(1)	G₁ ≅ G₁(Reflexivität)

(2)	G₁ ≅ G₂ impliziert G₂ ≅ G₁ (Symmetrie)

(3)	G₁ ≅ G₂ und G₂ ≅ G₃ impliziert G₁ ≅ G₃ (Transitivität)

Beweis

zu (1) : Die Identität id : E₁ → E₁ ist bijektiv. Für alle a, b  ∈  E₁ gilt wegen id(a) = a und id(b) = b:

ab  ∈  K₁ genau dann, wenn id(a)id(b)  ∈  K₁.

Also gilt id : G₁ ≅ G₁.

zu (2) : Sei f : G₁ ≅ G₂. Da f bijektiv ist, ist die Umkehrabbildung g = f ⁻¹ eine Bijektion von E₂ nach E₁. Seien c, d  ∈  E₂ beliebig. Da f bijektiv ist, gibt es a, b  ∈  E₁ mit f (a) = c und f (b) = d. Mit g(c) = a und g(d) = b erhalten wir die Äquivalenzenkette

cd  ∈  K₂	genau dann, wenn	f (a)f (b)  ∈  K₂
	genau dann, wenn	ab  ∈  K₁
	genau dann, wenn	g(c)g(d)  ∈  K₁

Also gilt g : G₂ ≅ G₁.

zu (3) : Seien f : G₁ ≅ G₂ und g : G₂ ≅ G₃. Dann ist die Verknüpfung h = g ∘ f eine Bijektion von E₁ nach E₃. Für alle a, b  ∈  E₁ gilt:

ab  ∈  K₁	genau dann, wenn	f (a)f (b)  ∈  K₂
	genau dann, wenn	g(f (a))g(f (b))  ∈  K₃
	genau dann, wenn	h(a)h(b)  ∈  K₃

Also gilt h : G₁ ≅ G₃.

Nach unserer Motivation ist zu erwarten, dass zwei isomorphe Graphen in allen graphentheoretischen Eigenschaften übereinstimmen. Dass dies so ist, kann schrittweise aus der Definition der Isomorphie gefolgert werden, denn diese Eigenschaften lassen sich auf Ecken und Kanten zurückführen. So bedeutet etwa

„Die Ecke a ist Ecke eines Dreiecks in G₁.“

dass es zwei Ecken b ≠ c in E₁ gibt mit ab, bc, ca  ∈  K₁. Dann sind f (a), f (b) und f (c) drei verschiedene Ecken von E₂ mit f (a)f (b), f (b)f (c), f (c)f (a)  ∈  K₂. Folglich gilt:

„Die Ecke f (a) ist die Ecke eines Dreiecks in G₂.“

Ein Isomorphismus übersetzt Dreiecke (in beiden Richtungen)

Ebenso gilt zum Beispiel für alle a, b₁, …, b_n  ∈  E₁ (Übung):

(+) N(a) = { b₁, …, b_n } genau dann, wenn N(f (a)) = { f (b₁), …, f (b_n) }.

Damit haben für alle a  ∈  E₁ die Ecken a und f (a) den gleichen Grad, d. h. es gilt d(a) = d(f (a)).

Ein Isomorphismus übersetzt Nachbarn (in beiden Richtungen)

Aus (+) ergibt sich:

Satz (Gradfolgenbedingung)

Zwei isomorphe Graphen haben die gleiche Gradfolge.

So haben obige Graphen zum Beispiel die gemeinsame Gradfolge

2, 3, 3, 3, 4, 4, 4, 4, 4, 5.

Die Bedingung ist des Satzes ist nicht hinreichend: Zwei Graphen können die gleiche Gradfolge besitzen ohne isomorph zu sein (Übung).

Zahlreiche andere Eigenschaften bleiben unter Isomorphie erhalten. Einige davon sind:

Beispiele

(1)	Ein Isomorphismus zwischen zwei Graphen übersetzt Kantenzüge in Kantenzüge, Wege in Wege, Kreise in Kreise. Offenheit und Einfachheit bleiben dabei wechselseitig erhalten.

(2)	Sind G₁ und G₂ isomorph, so ist G₁ genau dann zusammenhängend, wenn G₂ dies ist. Allgemeiner entspricht die Anzahl der Zusammenhangskomponenten von G₁ denen von G₂.

(3)	Ist f : G₁ ≅ G₂ ein Isomorphismus von G₁ nach G₂, so ist eine Kante ab von G₁ genau dann eine Brücke in G₁, wenn die Kante f (a)f (b) von G₂ eine Brücke in G₂ ist. Damit haben G₁ und G₂ die gleiche Anzahl an Brücken.

(4)	Ein Isomorphismus f : G₁ ≅ G₂ erhält den Abstand, d. h. es gilt d_G₁(a, b) = d_G₂(f (a), f (b)) für alle Ecken a, b von G₁. Weiter gilt: Gibt es in G₁ genau einen Weg der Länge 3 von a nach b, so gibt es in G₂ genau einen Weg der Länge 3 von f (a) nach f (b), usw.

(5)	Sind G₁ = (E₁, K₁) und G₂ = (E₂, K₂) isomorph, so ist G₁ genau dann bipartit, wenn G₂ dies ist. Denn ein Isomorphismus übersetzt eine bipartite Zerlegung von E₁ in eine bipartite Zerlegung von E₂. Allgemeiner ist G₁ für jedes k ≥ 2 genau dann k-partit, wenn G₂ dies ist.

(6)	Isomorphe Graphen enthalten die gleiche Anzahl an Dreiecken und allgemeiner Kreisen der Länge 4, 5, 6, …

Eine allgemeine Definition, was genau eine „graphentheoretische Eigenschaft“ ist, ist möglich, und mit ihrer Hilfe lässt sich beweisen, dass zwei isomorphe Graphen die gleichen graphentheoretischen Eigenschaften besitzen. Wir begnügen uns an dieser Stelle mit den gegebenen Beispielen. Die Intuition ist hier in der Regel sehr zuverlässig. Im Zweifel lässt sich immer nachweisen, dass eine bestimmte Eigenschaft unter Isomorphie erhalten bleibt.