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 | Quelltext bearbeiten]

Seien und Graphen desselben Typs. Eine bijektive Abbildung heißt Isomorphismus zwischen und , falls gilt:

  • ist Kante von genau dann, wenn Kante von ist in ungerichteten Graphen ohne Mehrfachkanten,
  • ist Kante von genau dann, wenn Kante von ist in gerichteten Graphen ohne Mehrfachkanten,
  • in ungerichteten Graphen mit Mehrfachkanten, d. h. je zwei Ecken sind mit ebenso vielen Kanten verbunden wie ihre Bildecken.
  • in gerichteten Graphen mit Mehrfachkanten,
  • ist Kante von genau dann, wenn Kante von ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung heißt Automorphismus von bzw. , falls zusätzlich gilt.

Prüfung auf Isomorphie[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

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

Graph isomorphism a.svg Graph isomorphism b.svg

Software[Bearbeiten | Quelltext bearbeiten]

Siehe auch[Bearbeiten | Quelltext bearbeiten]