Isomorphie von Graphen

Die Isomorphie von Graphen (oder Graphenisomorphie) ist in der Graphentheorie die Eigenschaft zweier Graphen, strukturell gleich zu sein.

Bei der Untersuchung graphentheoretischer Probleme kommt es meist nur auf die Struktur der Graphen, nicht aber auf die Bezeichnung ihrer Knoten an. In den allermeisten Fällen sind die untersuchten Grapheneigenschaften dann invariant bzgl. Isomorphie (gr. ἴσος ísos „gleich“ und μορφή morphé „Form“, „Gestalt“), die im Folgenden genauer definiert wird.

Definitionen

Seien $G_{1}=\left(V_{1},E_{1}\right)$ und $G_{2}=\left(V_{2},E_{2}\right)$ Graphen desselben Typs. Eine bijektive Abbildung $p\colon V_{1}\to V_{2}$ heißt Isomorphismus zwischen $G_{1}$ und $G_{2}$, falls gilt:

• $\left\{v,w\right\}$ ist Kante von $G_{1}$ genau dann, wenn $\left\{p(v),p(w)\right\}$ Kante von $G_{2}$ ist in ungerichteten Graphen ohne Mehrfachkanten.
• $\left(v,w\right)$ ist Kante von $G_{1}$ genau dann, wenn $\left(p\left(v\right),p\left(w\right)\right)$ Kante von $G_{2}$ ist in gerichteten Graphen ohne Mehrfachkanten.
• $E_{1}\left(\left\{v,w\right\}\right)=E_{2}\left(\left\{p\left(v\right),p\left(w\right)\right\}\right)$ in ungerichteten Graphen mit Mehrfachkanten, d. h., je zwei Ecken sind mit ebenso vielen Kanten verbunden wie ihre Bildecken.
• $E_{1}\left(\left(v,w\right)\right)=E_{2}\left(\left(p\left(v\right),p\left(w\right)\right)\right)$ in gerichteten Graphen mit Mehrfachkanten.
• $\left\{v_{1},\dotsc ,v_{k}\right\}$ ist Kante von $G_{1}$ genau dann, wenn $\left\{p\left(v_{1}\right),\dotsc ,p\left(v_{k}\right)\right\}$ Kante von $G_{2}$ ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung $p$ heißt Automorphismus von $G_{1}$ bzw. $G_{2}$, falls zusätzlich $G_{1}=G_{2}$ gilt.

Prüfung auf Isomorphie und Graphen-Isomorphismus-Problem

Zur Prüfung der Isomorphie zweier gegebener Graphen ist kein effizienter (polynomialzeitlicher) Algorithmus bekannt. Mehr noch, die Komplexität des bestmöglichen Algorithmus ist bis heute noch nicht bestimmt. Insbesondere ist die Isomorphie von Graphen eines der wenigen bekannten Probleme in NP, für die weder bekannt ist, ob sie in P enthalten, noch ob sie NP-vollständig sind. Die Frage, ob das Graphen-Isomorphismus-Problem in P ist (oder ob es NP-vollständig ist) ist eines der großen offenen Probleme der Informatik. Es ist das letzte der 12 Probleme in dem Buch Computers and Intractability (1979) von Michael Garey und David S. Johnson, von denen nicht bekannt ist, in welche der Komplexitätsklassen NP-vollständig oder P sie gehören (oder nicht gehören). Deshalb wurde es auch schon als eigene Komplexitätsklasse GI definiert und es wurde untersucht, ob andere Probleme GI-schwer oder GI-vollständig sind, wobei die Definitionen in analoger Weise wie bei NP-schwer und NP-vollständig erfolgen.

László Babai gab im Dezember 2015 an, einen Algorithmus gefunden zu haben, der das Problem in der Zeit $e^{{(\log {n})}^{O(1)}}$ löst (mit der Anzahl $n$ der Knoten des Graphen). Dieses Verhalten wird als quasipolynomial bezeichnet, da die Laufzeit schneller als polynomial wächst, aber einem polynomialen Verhalten nahe kommt. Die vorher beste Abschätzung stammte von Babai und Eugene Luks 1983, die die Schranke $e^{O({\sqrt {(n\cdot \log {n})}})}$ angab.

Beispiel

Diese beiden Graphen sind isomorph, obwohl ihre Darstellungen sich erheblich unterscheiden.

$G_{1}=(V_{1},E_{1})$	$G_{2}=(V_{2},E_{2})$	$p\colon V_{1}\to V_{2}$
		$p(a)=1$ $p(b)=6$ $p(c)=8$ $p(d)=3$ $p(g)=5$ $p(h)=2$ $p(i)=4$ $p(j)=7$

Software

• nauty. Ein Programm zur Berechnung der Automorphismengruppen und der kanonischen Labelings von Graphen. Zwei Graphen sind genau dann isomorph, wenn ihre kanonischen Labelings übereinstimmen.
• NetworkX. Eine freie Python-Bibliothek

Siehe auch

• Homöomorphie (Graphentheorie)