Graph-Isomorphie beschreibt die strukturelle Gleichheit zweier Graphen: Zwei Graphen sind isomorph, wenn sie sich nur in der Benennung ihrer Knoten unterscheiden, im Aufbau aber exakt gleich sind. Isomorphe Graphen haben dieselbe Form — man kann die Knoten so umbenennen, dass beide identisch aussehen.
Definition
Ein Isomorphismus zwischen zwei Graphen G und H ist eine umkehrbar eindeutige Abbildung f der Knotenmenge von G auf die Knotenmenge von H, die Kanten erhält: Eine Kante zwischen zwei Knoten in G existiert genau dann, wenn die Bild-Kante zwischen den Bild-Knoten in H existiert. Gibt es eine solche Abbildung, heißen G und H isomorph.
Warum das schwer zu erkennen ist
Auf den ersten Blick sieht ein Graph mit denselben
Knoten- und Kantenzahlen wie ein anderer aus — muss aber nicht isomorph sein. Eine einfache Prüfung ist die Gradfolge: Isomorphe Graphen haben stets dieselbe Liste der Knotengrade. Die Umkehrung gilt nicht: Zwei Graphen mit gleicher Gradfolge können trotzdem verschieden sein. Ein Gegenbeispiel sind zwei Graphen mit sechs Knoten und Gradfolge 3-3-3-3-3-3: Der eine zerfällt in zwei Dreiecke, der andere bildet eine Sechser-Kette — die Gradfolge täuscht. Erst die vollständige Vergleiche der Verbindungsstruktur entscheidet.
Das Graph-Isomorphie-Problem
Die Frage, ob zwei Graphen isomorph sind, ist eines der berühmten Probleme der theoretischen Informatik. Das Problem liegt in NP, ist aber weder als NP-vollständig noch als polynomial lösbar nachgewiesen — es gilt als einer der besten Kandidaten für eine Klasse zwischen P und NP. In der Praxis lassen sich selbst Millionen-Knoten-Graphen heute schnell vergleichen, etwa mit dem Weisfeiler-Lehman-Verfahren, das Knoten schrittweise nach ihrer Nachbarschaftsstruktur unterscheidet.
Anwendungen
- Chemie: Molekülstrukturen vergleichen — dieselbe Verbindung kann in Datenbanken unterschiedlich gezeichnet sein.
- Netzwerke: Topologien abgleichen, etwa ob zwei Teilnetze baugleich aufgebaut sind.
- Suchen: Einen gesuchten Teilgraphen in einem größeren Graphen wiederfinden (Subgraph-Isomorphie, als Erweiterung deutlich schwerer).
Abgrenzung
Isomorphie ist ein Vergleichskonzept: ungerichtete und gerichtete Graphen haben je eigene Isomorphie-Definitionen (bei gerichteten Graphen muss zusätzlich die Kantenrichtung erhalten bleiben). Verwandt, aber anders: Ein Subgraph ist ein Ausschnitt eines Graphen, kein Vergleich zweier Graphen. Auch Zusammenhangskomponenten, Zyklen und Adjazenzmatrizen bleiben unter Isomorphismen erhalten — ein Indiz, dass zwei Graphen isomorph sein können.