Isomorphie von Graphen

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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:

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[Bearbeiten]

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[Bearbeiten]

Diese beiden Graphen sind isomorph, obwohl sie unterschiedlich dargestellt werden können.

G_1 = (V_1, E_1) G_2 = (V_2, E_2) p:V_1 \rightarrow V_2
Graph isomorphism a.svg Graph isomorphism b.svg  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[Bearbeiten]

Siehe auch[Bearbeiten]