Graph-Isomorphie
Gibt es einen Algorithmus oder Heuristiken für die graph-Isomorphismus?
Theorem: Ein graph dargestellt werden kann und verschiedene Zeichnungen.
Was der beste Ansatz zu finden, andere Zeichnung des Graphen?
- dieser Algorithmus kann die Antwort sein Ihr suchen. link für einen polynomialzeit-Algorithmus für Graphen isomorph, Prüfung und Zuordnung
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Es ist eine Hölle von einem problem.
Allgemein, die grundlegende Idee ist die Vereinfachung der graph in eine kanonische form, und führen Sie dann einen Vergleich der kanonischen Formen. Aume generiert werden, mit diesem Ziel, aber Spannbaum nicht eindeutig sind, so dass Sie brauchen, um eine kanonische Weg, um Sie zu erstellen.
Haben Sie nach dem kanonischen Formen, die Sie durchführen können, Isomorphie-Vergleich (relativ) leicht, aber das ist nur der start, da nicht-isomorphe Graphen im wesentlichen können die gleichen spanning tree. (z.B. denken über einen Spannbaum T und einer einzigen Zugabe von einer Kante, um es zum erstellen von T'. Diese beiden Graphen sind nicht isomorph, aber Sie haben den gleichen spanning tree).
Anderen Techniken zu vergleichen mit einbeziehen Deskriptoren (z.B. Anzahl der Knoten, Anzahl der Kanten), die können falsch positive im Allgemeinen.
Ich schlage vor, Sie starten mit der wiki-Seite über die graph-Isomorphismus-problem. Ich habe auch ein Buch zu empfehlen: "Graphentheorie und deren Anwendungen". Es ist ein Wälzer, aber lohnt sich jede Seite.
Als von Ihnen heißt, jede mögliche räumliche Verteilung eines gegebenen Graphen die Ecken ist ein isomorph. Es werden also zwei Graphen isomorph, haben die gleiche Topologie, und Sie sind, im Ende, das gleiche Diagramm von topologischen Sicht. Eine andere Sache ist, zum Beispiel, zu finden, die isomorph Strukturen genießen besonderen Eigenschaften (z.B. mit nicht kreuzenden Kanten, falls vorhanden), und das hängt von den Eigenschaften, die Sie wollen.
Einer der besten algorithmen gibt, für die Suche nach graph isomorphisms ist VF2.
Ich habe eine schriftliche high-level-übersicht des VF2 angewandten Chemie - wo es sehr verbreitet ist. Der Beitrag berührt die Unterschiede zwischen VF2 und Ullmann. Es gibt auch eine von-scratch-Umsetzung der VF2, der in Java geschrieben, die hilfreich sein könnten.
Einem sehr ähnlichen problem - graph automorphism - kann gelöst werden, indem frechen, die im source-code. Dieser findet alle Symmetrien eines Graphen. Wenn Sie zwei Grafiken, verbinden Sie in eine und jeder Isomorphismus entdeckt werden kann, als ein automorphism der Verknüpfung.
Disclaimer: ich bin einer der co-Autoren von frechen.
Gibt es algorithmen, dies zu tun-allerdings habe ich nicht Ursache hatte, um ernsthaft zu untersuchen Sie noch. Ich glaube, dass Donald Knuth ist entweder schriftlich oder geschrieben hat, auf dieses Thema in seiner Kunst der Computing-Serie, der während seines zweiten Durchgang zu (re -) schreiben.
Als für einen einfachen Weg, etwas zu tun, das in der Praxis funktionieren könnte auf die kleinen Grafiken, die ich empfehlen würde, zählen Grad, dann für jeden vertex, beachten Sie auch den Satz der Grad für diejenigen Knoten, die benachbart sind. Diese wird dann geben Sie eine Reihe von potentiellen vertex isomorphisms für jeden Punkt. Dann versuchen Sie einfach, alle diejenigen, die (per brute force, aber die Wahl der Scheitelpunkten in aufsteigender Reihenfolge der möglichen vertex-Isomorphie-Sätze) aus dieser eingeschränkten Menge. Intuitiv werden die meisten Graphen Isomorphie kann das praktisch berechnete diese Weise, obwohl es natürlich wäre degenerierten Fällen, die eine lange Zeit dauern.
Kurzem stieß ich auf das folgende paper : http://arxiv.org/abs/0711.2010
Dieses Papier schlägt vor, "Einen polynomialzeit-Algorithmus für das Graph-Isomorphie"
Mein Projekt - Griso - bei sf.net: http://sourceforge.net/projects/griso/ mit dieser Beschreibung:
Griso ist ein graph-Isomorphismus-Testprogramm in C++ geschrieben. Es basiert auf meiner eigenen POLYNOM-ZEIT (in diesem Punkt ist das Salz des Projekts) - Algorithmus. Finden Sie Griso-sample-input/output auf http://funkybee.narod.ru/graphs.htm Seite.
Als für Heuristiken: ich habe fantasierte über eine modifizierte Ullmann-Algorithmus, wo man nicht nur die Verwendung der Breite zum ersten mal suchen, aber mischen Sie es mit depth-first Suche den Weg, dass Sie zuerst verwenden Sie die Breite der ersten Suche intensiv, als Sie eine Obergrenze für die Breite der Analyse tiefer gehen nach der Prüfung ein paar Nachbarn, und Sie senken die breadh jedem Schritt auf eine gewisse Menge. Dies ist praktisch, wie finde ich meinen Weg auf einer Karte an: wählen Sie zunächst selbst mit Breite-zuerst-Suche, suchen Sie dann die route mit depth first search - weitgehend, und das ist die beste Entwicklung meines Gehirns ist, der jemals erfunden wurde. 🙂 Auf lange Sicht etwas Intelligenz kann Hinzugefügt werden, für die Erhöhung der Breite der ersten Suche Nachbarn zählen an den kritischen Punkten - zum Beispiel, wo gibt es eine große Anzahl von benachbarten Knoten mit der selben Kante zu zählen. Wie die überprüfung Ihrer tatsächlichen Strecke mal mit dem Auto (ohne gps).
Habe ich herausgefunden, dass der Algorithmus gehört in die Kategorie der k-dimension Weisfeiler-Lehman-algorithmen, und es nicht mit regulären Graphen. Mehr hier:
http://dabacon.org/pontiff/?p=4148
Original-post folgt:
Ich gearbeitet habe, das problem zu finden isomorph Graphen in einer Datenbank von Graphen (enthält Chemische Zusammensetzungen).
Kurz gesagt, erstellt der Algorithmus ein hash-Wert eine Grafik mit der power-iteration-Methode. Möglicherweise gibt es falsche positive hash-Kollisionen, aber die Wahrscheinlichkeit ist äußerst klein (ich hatte keine solche Kollisionen mit Zehntausenden von Graphen).
Der Algorithmus funktioniert, ist dies:
Do N (wo N ist der radius der Kurve) Iterationen. Bei jeder iteration und für jeden Knoten:
Auf der ersten Stufe, ein-Knoten-hash ist betroffen durch die direkten Nachbarn von ihm. Auf der zweiten Stufe, ein-Knoten-hash ist betroffen durch die Nachbarschaft, die 2-hops, Weg von ihm. Auf der N-TEN Schritt ein Knoten in der hash-betroffen von der Nachbarschaft N-hüpft um ihn herum. Sie müssen nur weiterhin mit dem Powerhash für N = graph_radius Schritte. Am Ende der Grafik-Zentrum-Knoten-hash betroffen-das gesamte graph.
Zur fertigen hash Sortieren der Letzte Schritt der Knoten hashes und verketten Sie zusammen. Danach können Sie vergleichen die final-hashes zu finden, wenn zwei Graphen sind isomorph. Wenn Sie Etiketten, und fügen Sie diese (im ersten Schritt) in den internen hashes berechnen Sie für jeden Knoten.
Gibt es mehr hintergrund hier:
https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF
Finden Sie den Quellcode gibt es hier:
https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py