Die Frage nach der Isomorphie
Sind zwei Graphen G1 und G2 gegeben, so stellt sich die Frage:
Wie können wir zeigen oder widerlegen, dass die beiden Graphen isomorph sind?
Hierzu gibt es im Wesentlichen zwei Möglichkeiten:
Beweis der Isomorphie
Wir konstruieren einen Isomorphismus f : G1 ≅ G2.
Widerlegung der Isomorphie
Wir geben eine graphentheoretische Eigenschaft an, die auf den einen Graphen zutrifft, auf den anderen aber nicht. Standardeigenschaften, die wir überprüfen können sind:
Ordnung, Größe, Gradfolge,
bipartit, tripartit, …
zusammenhängend, Anzahl der Zusammenhangskomponenten,
enthält ein Dreieck, enthält ein Viereck,
enthält zwei Dreiecke mit/ohne gemeinsame Ecke,
enthält genau einen Kreis, enthält genau zwei Kreise, enthält zwei sich berührende Kreise, …
Beispiel
Seien G1 und G2 die Graphen mit der gemeinsamen Eckenmenge
E1 = E2 = { 1, …, 7 }
und den Kantenmengen
K1 = { 12, 24, 25, 34, 36, 45, 46, 67 },
K2 = { 12, 13, 14, 24, 36, 45, 47, 67 }.
Die beiden Graphen stimmen in Ordnung und Größe überein. Die Gradfolgen lauten:
1, 1, 2, 2, 3, 3, 4 für G1,
1, 2, 2, 2, 2, 3, 4 für G2.
Da sich die Gradfolgen unterscheiden, sind G1 und G2 nicht isomorph. Anhand eines Ecken-Kanten-Diagramms fällt der Unterschied relativ gut ins Auge (dies ist keineswegs immer der Fall):
Der linke Graph hat zwei Ecken mit Grad eins, der rechte nur eine
Es ist kein Kriterium bekannt, mit dem effizient entschieden werden könnte, ob zwei Graphen G1 und G2 isomorph sind oder nicht. Natürlich können wir alle Bijektionen von E1 nach E2 auflisten und die Kantenbedingung für jede Bijektion überprüfen. Haben G1 und G2 genau n Ecken, so gibt es n! Bijektionen von E1 nach E2, sodass dieser Weg aus praktischer Sicht ineffizient und für große Graphen unmöglich ist. Für zwei Graphen mit je 20 Ecken wären zum Beispiel
20! = 2432902008176640000
Bijektionen zu überprüfen. Durch die in „Widerlegung der Isomorphie“ genannten Kriterien kann eine Anwort „nein“ manchmal schnell gefunden werden. Wenn aber alle Standard-Kriterien sowohl auf den ersten als auch auf den zweiten Graphen zutreffen, heißt dies noch nicht, dass die beiden Graphen isomorph sind.