Isomorphie von Graphen

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, 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₂ ist in ungerichteten Graphen ohne Mehrfachkanten,
• $\left(v,w\right)$ ist Kante von G₁ 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 ebensovielen Kanten verbunden wie ihre Bildecken.
• E₁((v,w))=E₂((p(v),p(w))) in gerichteten Graphen mit Mehrfachkanten,
• {v₁,...,v_k} ist Kante von G₁ genau dann, wenn {p(v₁),...,p(v_k)} Kante von G₂ ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung p heißt Automorphismus von G₁ bzw. G₂, falls zusätzlich $G_1=G_2$ gilt.

Prüfung auf Isomorphie

Zur Prüfung der Isomorphie zweier gegebener Graphen ist kein effizienter 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.

Beispiel

$G_1 = (V_1, E_1)$	$G_2 = (V_2, E_2)$	$p:V_1 \rightarrow 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

• http://cs.anu.edu.au/people/bdm/nauty/ - nauty, ein Programm zur Berechnung der Automorphismengruppen und der kanonischen Labelings von Graphen. Zwei Graphen sind genau dann isomorph, wenn ihre kanonischen Labelings übereinstimmen.