Isomorphie von Graphen - LinkFang.de





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 [math]G_1=\left(V_1,E_1\right)[/math] und [math]G_2=\left(V_2,E_2\right)[/math] Graphen desselben Typs. Eine bijektive Abbildung [math]p\colon V_1\to V_2[/math] heißt Isomorphismus zwischen [math]G_1[/math] und [math]G_2[/math], falls gilt:

  • [math]\left\{v,w\right\}[/math] ist Kante von [math]G_1[/math] genau dann, wenn [math]\left\{p(v),p(w)\right\}[/math] Kante von [math]G_2[/math] ist in ungerichteten Graphen ohne Mehrfachkanten,
  • [math]\left(v,w\right)[/math] ist Kante von [math]G_1[/math] genau dann, wenn [math]\left(p\left(v\right),p\left(w\right)\right)[/math] Kante von [math]G_2[/math] ist in gerichteten Graphen ohne Mehrfachkanten,
  • [math]E_1\left(\left\{v,w\right\}\right)=E_2\left(\left\{p\left(v\right),p\left(w\right)\right\}\right)[/math] in ungerichteten Graphen mit Mehrfachkanten, d. h. je zwei Ecken sind mit ebenso vielen Kanten verbunden wie ihre Bildecken.
  • [math]E_1\left(\left(v,w\right)\right)=E_2\left(\left(p\left(v\right),p\left(w\right)\right)\right)[/math] in gerichteten Graphen mit Mehrfachkanten,
  • [math]\left\{v_1, \dotsc, v_k\right\}[/math] ist Kante von [math]G_1[/math] genau dann, wenn [math]\left\{p\left(v_1\right), \dotsc, p\left(v_k\right)\right\}[/math] Kante von [math]G_2[/math] ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung [math]p[/math] heißt Automorphismus von [math]G_1[/math] bzw. [math]G_2[/math], falls zusätzlich [math]G_1=G_2[/math] 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

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

[math]G_1 = (V_1, E_1)[/math] [math]G_2 = (V_2, E_2)[/math] [math]p:V_1 \rightarrow V_2[/math]
[math] p(a) = 1[/math]

[math] p(b) = 6[/math]

[math] p(c) = 8[/math]

[math] p(d) = 3[/math]

[math] p(g) = 5[/math]

[math] p(h) = 2[/math]

[math] p(i) = 4[/math]

[math] p(j) = 7[/math]

Software

Siehe auch


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Isomorphie von Graphen (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.