In der Graph-Theorie, einem Isomorphismus von Graphen G und H ist eine Bijektion zwischen den Scheitelpunkt-Sätzen von G und H

solch, dass irgendwelche zwei Scheitelpunkte u und v von G in G angrenzend sind, wenn, und nur wenn ƒ (u) und (v) ƒ in H angrenzend sind. Diese Art der Bijektion wird "Rand bewahrende Bijektion" in Übereinstimmung mit dem allgemeinen Begriff des Isomorphismus allgemein genannt, der eine Struktur bewahrende Bijektion ist.

In der obengenannten Definition, wie man versteht, sind Graphen ungeleitete nichtetikettierte nichtbelastete Graphen. Jedoch kann der Begriff des Isomorphismus auf alle anderen Varianten des Begriffs des Graphen, durch das Hinzufügen der Voraussetzungen angewandt werden, um die entsprechenden zusätzlichen Elemente der Struktur zu bewahren: Kreisbogen-Richtungen, Rand-Gewichte, usw., mit der folgenden Ausnahme. Wenn gesprochen, über das Graph-Beschriften mit einzigartigen Etiketten, die allgemein von der ganzen Zahl genommen sind, erstrecken sich 1..., n, wo n die Zahl der Scheitelpunkte des Graphen ist, wie man sagt, sind zwei etikettierte Graphen isomorph, wenn die entsprechenden zu Grunde liegenden unetikettierten Graphen isomorph sind.

Wenn ein Isomorphismus zwischen zwei Graphen besteht, dann werden die Graphen isomorph genannt, und wir schreiben. Im Fall, wenn die Bijektion ist eines Graphen auf sich kartografisch darzustellen, d. h., wenn G und H ein und derselbe Graph sind, wird die Bijektion einen automorphism von G genannt.

Der Graph-Isomorphismus ist eine Gleichwertigkeitsbeziehung auf Graphen, und als solcher verteilt er die Klasse aller Graphen in Gleichwertigkeitsklassen. Eine Reihe von zu einander isomorphen Graphen wird eine Isomorphismus-Klasse von Graphen genannt.

Beispiel

Die zwei Graphen, die unten gezeigt sind, sind trotz ihrer verschieden aussehenden Zeichnungen isomorph.

Motivation

Der formelle Begriff "des Isomorphismus", z.B, des "Graph-Isomorphismus", gewinnt den informellen Begriff, dass einige Gegenstände "dieselbe Struktur" haben, wenn man individuelle Unterscheidungen von "Atom"-Bestandteilen von fraglichen Gegenständen ignoriert, sieh das Beispiel oben. Wann auch immer die Individualität von "Atom"-Bestandteilen (Scheitelpunkte und Ränder, für Graphen) für die richtige Darstellung dessen wichtig ist, dass durch Graphen modelliert wird, wird das Modell durch das Auferlegen von zusätzlichen Beschränkungen der Struktur raffiniert, und andere mathematische Gegenstände werden verwendet: Digraphe, etikettierte Graphen, gefärbt Graphen, haben Bäume und so weiter einwurzeln gelassen. Die Isomorphismus-Beziehung kann auch für alle diese Generalisationen von Graphen definiert werden: Die Isomorphismus-Bijektion muss die Elemente der Struktur bewahren, die die fragliche Objektart definieren: Kreisbogen, Etiketten, Farben des Scheitelpunkts/Randes, die Wurzel des eingewurzelten Baums, usw.

Der Begriff des "Graph-Isomorphismus" erlaubt uns, Graph-Eigenschaften zu unterscheiden, die zu den Strukturen von Graphen selbst von mit Graph-Darstellungen vereinigten Eigenschaften innewohnend sind: Graph-Zeichnungen, Datenstrukturen für Graphen, Graph labelings, usw. Zum Beispiel, wenn ein Graph genau einen Zyklus hat, dann haben alle Graphen in seiner Isomorphismus-Klasse auch genau einen Zyklus. Andererseits, im allgemeinen Fall, wenn die Scheitelpunkte eines Graphen (vertreten durch) die ganzen Zahlen 1, 2 sind... N, dann der Ausdruck

kann für zwei isomorphe Graphen verschieden sein.

Anerkennung des Graph-Isomorphismus

Lehrsatz von Whitney

Der Graph-Isomorphismus-Lehrsatz von Whitney, der von H. Whitney gezeigt ist, stellt fest, dass zwei verbundene Graphen isomorph sind, wenn, und nur wenn ihre Liniengraphen mit einer einzelnen Ausnahme isomorph sind: K, der ganze Graph auf drei Scheitelpunkten und der ganze zweiteilige Graph K, die nicht isomorph sind, aber haben beide K als ihr Liniengraph. Der Graph-Lehrsatz von Whitney kann zu Hypergraphen erweitert werden.

Algorithmische Annäherung

Während Graph-Isomorphismus auf eine klassische mathematische Weise, wie veranschaulicht, durch den Lehrsatz von Whitney studiert werden kann, wird er anerkannt, dass es ein Problem ist, mit einer algorithmischen Annäherung angepackt zu werden. Das rechenbetonte Problem der Bestimmung, ob zwei begrenzte Graphen isomorph sind, wird das Graph-Isomorphismus-Problem genannt.

Seine praktischen Anwendungen schließen in erster Linie cheminformatics, mathematische Chemie (Identifizierung von chemischen Zusammensetzungen), und elektronische Designautomation (Überprüfung der Gleichwertigkeit von verschiedenen Darstellungen des Designs eines elektronischen Stromkreises) ein.

Neugierig ist es auch eines nur einiger Probleme in der rechenbetonten Kompliziertheitstheorie, die NP, aber nicht bekannt gehört, jedem seiner wohl bekannten (und, wenn P  NP, zusammenhanglos) Teilmengen zu gehören: P und NP-complete. Es ist einer von nur zwei, aus 12 ganzen, verzeichnete Probleme, in wessen Kompliziertheit ungelöst bleibt. D. h. wie man bewiesen hat, ist es darin nicht eingeschlossen, noch von, P oder NP-complete nicht ausgeschlossen worden. Es ist jedoch das bekannt, wenn das Problem NP-complete dann die polynomischen Hierarchie-Zusammenbrüche zu einem begrenzten Niveau ist.

bekannt, ist seine Generalisation, das Subgraph-Isomorphismus-Problem, NP-complete.

Die Hauptgebiete der Forschung für das Problem sind Design von schnellen Algorithmen, sowohl für das allgemeine Problem als auch für spezielle Klassen von Graphen und theoretische Untersuchungen seiner rechenbetonten Kompliziertheit.

Siehe auch

• Graph-Homomorphismus
• Graph automorphism Problem
• Graph-Kanonisation