Einteilung in Isomorphieklassen

Für alle n ≥ 1 lassen sich alle Graphen mit der Eckenmenge { 1, …, n } in Isomorphieklassen einteilen. Instruktiv ist der Fall n = 3:

Beispiel

Sei E = { 1, 2, 3 }. Dann gibt es genau acht Graphen G₁, …, G₈ mit der Eckenmenge E. Sie sind definiert durch die Kantenmengen

K₁ = { },	K₂ = { 12 },	K₃ = { 13 },	K₄ = { 23 },
K₅ = { 12, 13 },	K₆ = { 12, 23 },	K₇ = { 13, 23 },	K₈ = { 12, 13, 23 }.

Die Graphen G₂, G₃ und G₄ sind paarweise zueinander isomorph, ebenso wie die Graphen G₅, G₆ und G₇. Ansonsten bestehen nur noch die trivialen Isomorphien G_k ≅ G_k für k = 1, …, 8.

Die acht Graphen G₁, …, G₈ mit den Ecken { 1, 2, 3 }. Gleichfarbige Graphen sind isomorph, verschiedenfarbige Graphen sind nicht isomorph.

Für G₂ und G₃ gilt zum Beispiel: Die isolierte Ecke 3 von G₂ muss durch jeden Isomorphismus auf die isolierte Ecke 2 von G₃ abgebildet werden. Bei den durch eine Kante verbundenen Ecken ist ein Tausch möglich, die beiden Ecken sind strukturell nicht unterscheidbar. Insgesamt gibt es zwischen G₂ und G₃ genau zwei Isomorphismen, nämlich die Bijektionen f, g : { 1, 2, 3 } → { 1, 2, 3 } mit

f (1) = 1,	f (2) = 3,	f (3) = 2,
g(1) = 3,	g(2) = 1,	g(3) = 2.

Analoges gilt für die anderen zueinander isomorphen Graphen. Für die Graphen G₆, G₇ und G₈ beachte der Leser, dass die eindeutig bestimmten Ecken vom Grad 2 (die gemeinsame Ecke der beiden Kanten) durch einen Isomorphismus einander zugeordnet werden müssen, die beiden anderen Ecken können wieder ausgetauscht werden.

Insgesamt erhalten wir also die vier Isomorphieklassen (Mengen zueinander isomorpher Graphen):

{ G₁ }, { G₂, G₃, G₄ }, { G₅, G₆, G₇ }, { G₈ }.

Wir können diese Klassen visuell darstellen, indem wir aus jeder Klasse einen beliebigen Graphen auswählen und die Namen der Ecken weglassen:

Symbolische Darstellung der Isomorphieklassen der Graphen mit drei Ecken

In analoger Weise lassen sich die Graphen mit 4, 5, 6, … Ecken bis auf Isomorphie klassifizieren. Eine Klassifikation der 64 Graphen mit der Eckenmenge { 1, 2, 3, 4 } können wir noch relativ gut per Hand durchführen (Übung). Allgemein wird das Vorhaben aber schnell sehr aufwendig: Ist n ≥ 1 beliebig, so gibt es genau 2^m Graphen mit der Eckenmenge { 1, …, n }, wobei

m = n(n − 1)/2.

Es ist keine allgemeine Formel für die Anzahl der Isomorphieklassen in Abhängigkeit von n bekannt. Mit Hilfe von Computern lässt sich diese Anzahl für kleine n berechnen:

n	Anzahl der Graphen	Anzahl der Isomorphieklassen
1	1	1
2	2	2
3	8	4
4	64	11
5	1024	34
6	32768	156
7	2097152	1044
8	268435456	12346
9	68719476736	274668
10	35184372088832	12005168