Get best of the week

Überprüfung des Isomorphismus zweier Graphen und Suche nach isomorphen Teilgraphen: Ein Ansatz, der auf der NB-Pfadanalyse basiert

Hallo alle zusammen.

Es gibt eine solche Aufgabe - zu überprüfen, ob zwei Graphen zueinander isomorph sind. Das heißt, um es einfach auszudrücken, um herauszufinden, ob diese beiden Diagramme „dasselbe“ Diagramm sind, jedoch mit unterschiedlichen Scheitelpunktnummern und, wenn Diagramme grafisch angegeben sind, mit unterschiedlichen räumlichen Positionen. Die Lösung für dieses Problem ist nicht so offensichtlich, wie es jemandem auf den ersten Blick erscheinen mag: Selbst bei kleinen Grafiken gibt ein Blick auf ihre grafische Darstellung nicht immer eine eindeutige Antwort. Siehe zum Beispiel eine Zeichnung im selben Wiki: en.wikipedia.org/wiki/Graph_isomorphism#Example .

Gut Offensichtlich?

Es gibt jedoch eine schwierigere Aufgabe: In einem „großen“ Diagramm nach allen Teilgraphen zu suchen, die isomorph zu einem anderen „kleineren“ Diagramm sind. Dies ist ein noch "dunklerer Wald". Das ist natürlich nicht ganz dunkel, aber die Aufgabe ist nicht die einfachste.

Was haben wir also?

1. Warum ist das alles notwendig?


Und obwohl das Problem der isomorphen (Sub-) Graphen, wie wir bereits erwähnt haben, kompliziert ist, ist es durchaus notwendig und nützlich. Und warum? Und dann zum Beispiel, um die Datenbank nach chemischen Verbindungen zu durchsuchen, die einem bestimmten Molekül anhand seiner Strukturformel ähnlich sind. Man kann es sich doch als Grafik vorstellen, oder? Die Chemoinformatik macht das - es gibt eine solche Wissenschaft. Es gibt aber auch Vergleichsaufgaben mit der Stichprobe, verschiedene bioinformatische Aufgaben und viele andere interessante Dinge.

2. Wie kann dieses Problem gelöst werden?


Der klassische Ansatz zur Lösung dieses Problems wurde 1976 von J. Ullman festgelegt [3], später verbesserte er seinen Algorithmus erheblich [4]. Dieser Ansatz wurde auch in den Arbeiten vieler anderer Autoren weiterentwickelt, beispielsweise Cordella und Co-Autoren [2] (VF2-Algorithmus), Bonnitsi und Co-Autoren [1] (RI-Algorithmus) usw.

Kurz gesagt, das Wesentliche dieses Ansatzes ist „intelligent“ Aufzählen “der möglichen Entsprechungen der Eckpunkte des Beispielgraphen B und des Graphen A, in denen gesucht wird. Diese Suche macht es "klug", verschiedene Bedingungen und Einschränkungen einzugeben, die es Ihnen ermöglichen, ungeeignete Optionen so früh wie möglich auszuschließen. Zu diesen Zwecken können auch verschiedene Vorverarbeitungen der Quelldaten durchgeführt werden.

Wir werden diese Werke hier nicht nacherzählen, aber wir werden den Leser einladen, sie selbstständig kennenzulernen. "Eine Show ist besser als eine Bestellung", und es sollte beachtet werden, dass es im Web gute grafische Beispiele und Erklärungen für diese Algorithmen gibt. Siehe zum Beispiel Folgendes:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - eine sehr gute und klare Erklärung mit einem Beispiel,
issue.life/questions/8176298 - Schritte des VF2-Algorithmus mit einem Beispiel .

Es stellt sich jedoch die Frage: Gibt es andere Möglichkeiten und Ansätze zur Lösung dieses Problems, wenn auch für einige Sonderfälle? Und ich möchte Ihnen eine der möglichen Antworten auf diese Frage vorstellen.

2. Isomorphismus von Graphen und NB-Pfaden


Lassen Sie uns sofort zustimmen: Unter NB-Pfaden (und nicht aus dem Englischen, sondern einfach, weil es so kürzer ist) werden wir maximale nicht verzweigte Pfade nennen, d. H. maximal lange unverzweigte Pfade eines Graphen.

Wenn wir also zwei zueinander isomorphe Graphen haben , existiert für jede Darstellung des ersten Graphen als Folge von maximal erweiterten nicht verzweigten Pfaden (d. H. Diesen unserer NB-Pfade) immer eine entsprechende Darstellung des zweiten Graphen, der ihm entspricht, und gleichzeitig:

  • Bei gerichteten Graphen werden die einander entsprechenden Pfade ausgerichtet.
  • Die Grade der Eckpunkte, die für ungerichtete Diagramme (und für orientierte Diagramme die Anzahl der eingehenden bzw. ausgehenden Kanten) einander entsprechen, sind gleich
  • Wenn wir solche Darstellungen als Ergebnis "kombinieren", erhalten wir eine Entsprechung der Eckpunkte des ersten und zweiten Graphen.

Ein Beispiel . Graph A = {1-> 2, 1-> 6, 4-> 5, 5-> 1, 3-> 3}. Graph B = {3-> 4, 3-> 5, 1-> 2, 2-> 3, 6-> 6}
Pfade A ( maximale nicht verzweigte Pfade von A ): 1-> 2, 1-> 6, 4-> 5-> 1, 3-> 3 Pfade B
( maximale nicht verzweigte Pfade von B ): 3-> 4, 3-> 5, 1-> 2-> 3, 6-> 6 Vertex-Matching
: 1 ( A): 3 (B), 2 (A): 4 (B), 6 (A): 5 (B), 4 (A): 1 (B), 5 (A): 2 (B), 3 ( A): 6 (B).

Somit kann das Problem der Überprüfung des Isomorphismus zweier Graphen gelöst werden, indem solche Pfade gefunden werden, die einander entsprechen, und dann die Gleichheit der Adjazenzmatrizen überprüft wird, die auf der Grundlage ihrer Erhaltung der Reihenfolge der Scheitelpunkte in den erhaltenen Pfadsequenzen konstruiert wurden (jeder Scheitelpunkt wird der Sequenz einmal hinzugefügt). erste "Erwähnung"). In unserem Beispiel werden die folgenden Scheitelpunktreihenfolgen verwendet, um Adjazenzmatrizen zu erstellen:

A : 1, 2, 6, 4, 5, 3
B : 3, 4, 5, 1, 2, 6

Adjazenzmatrix für A für eine gegebene Reihenfolge von Scheitelpunkten:

Bild

Adjazenzmatrix für B für eine gegebene Ordnung von Eckpunkten:

Bild

Die Matrizen sind gleich, daher sind die Graphen A und B isomorph.

Darüber hinaus ist dieser Ansatz (1) sowohl für orientierte als auch für nicht orientierte Graphen anwendbar, (2) er ist für Graphen anwendbar, die mehr als eine verbundene Komponente / starke Verbindung enthalten, (3) er ist jedoch für Graphen anwendbar, die mehrere (mehrere) Kanten und Schleifen enthalten (4) berücksichtigt keine Eckpunkte, für die keine Kanten auffallen.

3. Nun, überprüfte den Isomorphismus von Graphen. Aber was ist mit der Suche nach Untergraphen?


Und hier ist offen gesagt alles viel komplizierter. Hier haben wir die folgende Einschränkung: Basierend auf dem Wesen der Methode können Sie keine, sondern nur "eingeschriebene" Untergraphen finden . Und wir werden den "eingeschriebenen" Untergraphen von Graph A einen solchen Untergraphen nennen, der nur aufgrund von Kanten, die nur auf die Grenzscheitelpunkte seiner (Untergraph) nicht verzweigten Pfade maximaler Länge fallen, auf andere Teile von Graph A "geklebt" werden kann (außerdem kann Graph A enthalten andere angeschlossene Komponenten). Machen Sie sich keine Sorgen, unten finden Sie ein Beispiel, und alles wird klarer.

Darüber hinaus ist es bei der Lösung dieses Problems zusätzlich zur Suche nach der Entsprechung von NB-Pfaden der Graphen A und B in der Länge (wie dies beim obigen Isomorphismustest der Fall war) auch erforderlich, die folgenden möglichen Entsprechungen zwischen ihnen separat zu suchen:

  • Entsprechung von NB-Pfaden - einfache Ketten von Graph B zu NB-Pfaden - einfache Ketten / einfache Zyklen von Graph A. Außerdem können anfänglich solche Pfade in Graph A länger sein - in diesem Fall werden ihre Segmente genommen, deren Länge dem gewünschten Pfad von B entspricht.
  • Entsprechung der NB- "End" -Pfade von Graph B zu beliebigen NB-Pfaden von Graph A (in diesem Fall können die Pfade von Graph A auch länger sein - in diesem Fall werden ihre Segmente genommen, deren Länge dem gewünschten Pfad von Graph B entspricht).

Schauen wir uns ein Beispiel an:

Bild

Bei der Suche nach einem „eingeschriebenen“ isomorphen Teilgraphen von Graph B in Spalte A (siehe Abbildung oben) werden die folgenden Entsprechungen gefunden:

  • innerer Pfad 2-> 3-> 4 von Spalte B: innerer Pfad 2-> 3-> 4 von Spalte A,
  • Endpfade 1-> 2 und 10-> 2 von Spalte B: Endpfad 0-> 2 von Spalte A und ein Fragment des Endpfades 7-> 1-> 2 von Spalte A, nämlich 1-> 2,
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

Als die "eingeschriebenen" Untergraphen von Graph A, die zu Graph B isomorph sind, können die folgenden 5 Optionen gefunden werden:

A1 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 9-> 10}
A2 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 10-> 11}
A3 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 12-> 13}
A4 = {0-> 2, 1-> 2, 2 -> 3, 3-> 4, 4-> 5, 4-> 6, 13-> 14}
A5 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 14-> 12}

Wenn wir jedoch dem Graphen A eine zusätzliche Kante 3-> 8 hinzufügen, erhalten wir den Graphen A '(unten in derselben Abbildung). Und in A 'gibt es keine "eingeschriebenen" Untergraphen mehr, die isomorph zum Graphen B sind. In der Tat: Die Kante 3-> 8 "teilt" den Pfad 2-> 3-> 4 des Graphen A in zwei und daher Kandidatenpfade für den inneren Pfad 2 ->3-> 4 Spalten B werden nicht gefunden.

4. Nun der Algorithmus selbst


Nun können wir zu einer detaillierteren Betrachtung des Suchalgorithmus für die in Spalte A „eingeschriebenen“ Untergraphen übergehen , die zu einer Spalte B isomorph sind.

Der Algorithmus besteht also aus 4 Stufen:

  • Vorverarbeitung
  • Matching
  • Verdünnung,
  • Fazit

Stufe I. Vorverarbeitung


Zu diesem Zeitpunkt finden wir alle NB-Pfade für jedes der Diagramme und bewerten die Faktoren, die den Auswahlraum während der Aufzählung einschränken. Jene. Wir machen folgendes:

  1. Wir finden alle NB-Pfade in Spalte A und fügen sie in ein dynamisches Array (in C ++ - in einen Vektor) PathsA ein
  2. Wir finden alle NB-Pfade in Spalte B und fügen sie in ein dynamisches Array (Vektor) PathsB ein
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

Wir haben also NB-Pfade in beiden Diagrammen und Grenzparameter ab S.P. 3-5.

Stufe II. Kartierung


In diesem Stadium werden wir Kandidaten-NB-Pfade (im Folgenden einfach als "Kandidatenpfade" bezeichnet) aus Spalte A für jeden der NB-Pfade von Spalte B auswählen. Markieren jedes Kandidatenpfads aus Pfaden A für jeden i-ten Pfad Pfade B [i ] wird in ein zweidimensionales dynamisches Array (in C ++ - in einen Vektor von Vektoren) NPaths - bzw. in den i-ten Vektor (i-te Linie) - in Form eines geordneten Dreifaches von Zahlen geschrieben: die Nummer des entsprechenden Pfads in PathsA - die Nummer der Startposition darin - die Länge des Pfads .

Zum Beispiel bedeutet PathsB [2] = {1, 0, 3, 3, 1, 3}, dass PathsB [2] -Pfade 2 Kandidatenpfaden von A zugeordnet sind: von PathsA [1] - den ersten 3 Pfadelementen beginnend bei Null ( initial) und von PathsA [3] - auch 3 Elemente beginnend mit dem ersten (neben dem initial).

Gleichzeitig werden wir Kandidatenpfade in 4 Richtungen suchen (auswählen):

  1. Suchen Sie nach Kandidatenpfaden für alle internen NB-Pfade von Graph B aus PathsB, d. H. diejenigen, deren beide Grenzscheitelpunkte im Graphen B mit mindestens 2 anderen Scheitelpunkten verbunden sind (unabhängig von der Richtung einer solchen Verbindung) und gleichzeitig ist dieser Pfad kein einfacher Zyklus (orientiert - für orientierte Graphen).
  2. Suchen Sie in PathsB nach Kandidatenpfaden für nachfolgende NB-Pfade.
  3. Suche nach Kandidatenpfaden für NB-Pfade - einfache Schleifen von PathsB.
  4. Suchen Sie nach Kandidatenpfaden für NB-Pfade - einfache Pfade aus PathsB.

Bei der Auswahl von Kandidatenpfaden für jeden i-ten Pfad aus Pfad B werden sie verglichen (hier sind einige der zuvor berechneten Begrenzerparameter nützlich):

  • seine Länge und die Länge des Kandidatenpfads (sollte für die Fälle 1 und 3 gleich sein, und für die Fälle 2 und 4 kann der Kandidatenpfad von PathsA auch länger sein),
  • die Grade seiner Grenzscheitelpunkte und die entsprechenden Scheitelpunkte des Kandidatenpfads (für Scheitelpunkte aus dem Kandidatenpfad müssen diese Werte mindestens der Pfad aus Pfad B sein).

Wenn gemäß den Ergebnissen von Stufe II für keinen der Pfade in Pfad B ein einziger Kandidatenpfad aus Pfad A gefunden wurde, wird angenommen, dass A keine "eingeschriebenen" Untergraphen enthält, die isomorph zu Spalte B sind.

Verdünnung


Versuchen wir nun, Grafik A zu „quetschen“. Wir lassen nur die Kanten darin, die in die gefundenen Kandidatenpfade eingegangen sind. Wenn gleichzeitig Graph A im Vergleich zu seinem Ausgangszustand mindestens eine Kante verloren hat, kehren wir zu Stufe I „Vorverarbeitung“ zurück: Die Grade der Eckpunkte von Graph A und dementsprechend die Liste der Kandidatenpfade können reduziert werden, und dementsprechend kann der Suchraum reduziert werden.

Stufe III. Ausdünnen der Liste der Kandidatenpfade


Der Zweck dieses Schritts besteht darin, so viele Kandidaten wie möglich unangemessen zu eliminieren. Dazu führen wir folgende Schritte aus.

  1. Der Ausschluss offensichtlich unangemessener Kandidatenpfade basierend auf den Mindestabständen zwischen den Eckpunkten in Spalte B. Der Kandidatenpfad für jeden Pfad B [i], für den mindestens ein Pfad B [j] kein Kandidatenpfad für den kürzesten gefunden wurde Der Abstand zwischen ihren Grenzscheitelpunkten in Spalte A war kleiner oder gleich dem kürzesten Abstand zwischen den entsprechenden Grenzscheitelpunkten der Pfade Pfade B [i] und Pfade B [j] aus Graph B.
  2. Eine Ausnahme für alle Zyklen von PathsB zu damit verbundenen nichtzyklischen Kandidatenpfaden und umgekehrt.
  3. Die Ausnahme von Kandidatenpfaden ähnlich Abschnitt 1, jedoch nicht nach dem Kriterium des kürzesten Abstands zwischen Grenzscheitelpunkten, sondern nach ihren (Grenzscheitelpunkten) zur gegenseitigen Gleichheit oder Ungleichheit.

Zum Beispiel, wenn:

  • das Startelement von PathsB [i] ist nicht gleich dem Startelement von PathsB [j] und
  • das letzte Element von PathsB [i] ist nicht gleich dem letzten Element von PathsB [j] und
  • das Startelement von PathsB [i] ist gleich dem Endelement von PathsB [j] und
  • das Startelement von PathsB [j] ist nicht gleich dem Endelement von PathsB [i],

der Kandidatenpfad entlang des Pfades B [i], für den mindestens ein Pfad B [j] keine Kandidatenpfade gefunden hat, die die obige Bedingung hinsichtlich der Gleichheit / Ungleichheit ihrer (Kandidatenpfade) Anfang und Ende erfüllen Spitzen.

Das heißt, wir werfen grob gesagt die Kandidatenpfade weg, die offensichtlich nicht in den gewünschten Untergraphen enthalten sind - basierend auf der Entfernung zu allen anderen Kandidatenpfaden (diese Pfade sind schrecklich weit von allen anderen entfernt), basierend auf ihrer Zyklizität / Nichtzyklizität und auch basierend auf der gebotenen Gleichheit / Ungleichheit ihrer Grenzscheitelpunkte mit Grenzscheitelpunkten anderer Kandidatenpfade.

Wenn gemäß den Ergebnissen der Stufe III mindestens 1 Kandidatenpfad aus Pfad A gelöscht wurde, wird - wieder - Spalte A aktualisiert - nur die Kanten, die in den verbleibenden Kandidatenpfaden enthalten sind, verbleiben darin. Und wieder, wenn gleichzeitig Graph A um mindestens eine Kante „an Gewicht verloren“ hat, kehren wir wieder zu Stufe I „Vorverarbeitung“ zurück: Die Grade der Eckpunkte von Graph A und dementsprechend die Liste der Kandidatenpfade können reduziert und dementsprechend reduziert werden Suchraum.

Stufe IV. Fazit


Jede mögliche Kombination aller verbleibenden Kandidatenpfade definiert einen Teilgraphen der Spalte A. Für jeden solchen Teilgraphen wird eine Adjazenzmatrix unter Berücksichtigung der Reihenfolge der Kandidatenpfade auf die gleiche Weise konstruiert, wie die Adjazenzmatrix B00 für Graph B konstruiert wurde, und dann werden diese Adjazenzmatrizen verglichen.

Wenn sie gleich sind, werden die Multiplizitäten der Kanten verglichen (siehe Abschnitt 3 der Vorverarbeitung der Stufe I). Wenn alle diese Bedingungen erfüllt sind, wird der gefundene Teilgraph als isomorph zu Graph B betrachtet und zu der Menge der gefundenen Ergebnisse hinzugefügt.

Während der Stufe IV „Schlussfolgerung“ können verschiedene zusätzliche Überprüfungen verwendet werden, um die Identifizierung und Ablehnung eines unangemessenen Teilgraphen zu beschleunigen.

5. Wie alles verwirrt ist ... Betrachten Sie ein Beispiel des Algorithmus


Ich weiß nichts über dich, aber es wäre für mich ohne ein Beispiel unverständlich. Schauen wir uns ein Beispiel an.

In Abb. Die folgenden Diagramme sind A = {1-> 2, 2-> 5, 5-> 15, 16-> 15, 5-> 5, 5-> 5, 5-> 4, 5-> 6, 7-> 6 , 6-> 8, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 0-> 12, 4-> 13, 13-> 14, 14-> 4 } und B = {1-> 1, 4-> 5, 5-> 1, 1-> 3, 3-> 3, 3-> 2, 2-> 7, 2-> 8, 9-> 10, 10-> 9, 1-> 6, 6-> 11, 11-> 12, 12-> 6}. Unsere Aufgabe ist es, in Grafik A alle zu Grafik B isomorphen „eingeschriebenen“ Untergraphen zu finden. Das Ergebnis ist auch in der Abbildung dargestellt: Die gefundenen Eckpunkte und Kanten von Grafik A sind durch eine dicke Linie hervorgehoben, und die Nummern der entsprechenden Eckpunkte von Grafik B sind in Klammern angegeben (wenn mehrere Optionen vorhanden sind, werden sie durch angezeigt Fraktion).

Bild

Wenn Sie das Suchproblem in Spalte A der "eingeschriebenen" Untergraphen lösen, die isomorph zu Spalte B sind,Wir haben die folgenden Ergebnisse des Algorithmus.

Stufe I.: Alle Aktionen und Berechnungen wurden gemäß p.p. In den Schritten 1 bis 5 dieses Schritts sind die resultierenden Pfade A und Pfade B aufgeführt.

Pfade A:

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

Pfade B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

Stufen II-III. Der Vergleich zeigte, dass es für jeden Pfad von PathsA mindestens einen Kandidatenpfad von PathsB gibt und PathsA durch die Ergebnisse der vorläufigen Ausdünnung verkürzt wurde. Im Stadium der Hauptverdünnung (III) trat keine weitere Reduktion von PathsA auf. Infolgedessen hatten die Pfade A und Pfade B die Form:

Pfade A:

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

Pfade B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

Der endgültige Vergleich der NPaths lautet:
NPaths:

i = 0: 3 0 2
i = 1: 4 0 2
i = 2: 2 0 2
i = 3: 7 0 2 8 0 2
i = 4: 7 0 2 8 0 2
i = 5: 6 0 2
i = 6: 5 0 2
i = 7: 0 0 3
i = 8: 1 0 4
i = 9: 9 0 3

Hier ist die Zeit, um sich daran zu erinnern, dass jedes geordnete Triplett von Zahlen in NPaths [i] den entsprechenden PathsB [i] -Kandidatenpfad definiert von A im Format: die Nummer des entsprechenden Pfades von PathsA - die Startposition des Segments von diesem Pfad - die Länge des Segments. Somit ist es leicht zu überprüfen, ob die Pfade B [0] = {1-> 1} (i = 0: 3 0 2) dem einzigen Pfad von A entsprechen, nämlich dem Segment von Pfaden A [3], beginnend von Anfang an und mit einer Länge von 2.

Stufe IV. Als Ergebnis wurde in Spalte A ein eindeutiger Teilgraph A1 gefunden, der isomorph zu B ist. A1 = {0-> 12, 1-> 2, 2-> 5, 4-> 13, 5-> 4, 5-> 5, 5- > 6, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 13-> 14, 14-> 4}.

5. Was kommt als nächstes?


Und dann ist das im Prinzip alles. Obwohl nicht ganz: Der Autor muss zugeben, dass der Algorithmus noch finalisiert und finalisiert werden kann. Was gibt es hinzuzufügen?

  1. Wenn zusätzliche Merkmale der Eckpunkte der Spalten A und B eingeführt werden (wenn beispielsweise die Verbindungen durch die Graphen chemischer Verbindungen gegeben sind, kann jedem Scheitelpunkt ein numerischer Code zugeordnet werden, der nur einem Atom (Isotop) entspricht), kann der Suchprozess aufgrund der höheren Genauigkeit der Vergleiche gemäß Stufe II beschleunigt werden: zusätzlich Die Bedingung für die Auswahl von Kandidatenpfaden ist die Entsprechung von Scheitelpunktbezeichnungen.
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


Allgemein zu den Problemen:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. Ein Subgraph-Isomorphismus-Algorithmus und seine Anwendung auf biochemische Daten. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13 .
2. Cordella L, Foggia P, Sansone C, Vento M: Ein (Sub-) Graph-Isomorphismus-Algorithmus zum Anpassen großer Graphen. IEEE-Transaktionen zur Musteranalyse und Maschinenintelligenz. 2004, 26 (10): 1367 & ndash; 1372. 10.1109 / TPAMI.2004.75.
3. Ullmann Julian R .: Ein Algorithmus für den Subgraph-Isomorphismus. Zeitschrift der Association for Computing Machinery. 1976, 23: 31 & ndash; 42. 10.1145 / 321921.321925.
4. Ullmann Julian R .: Bitvektoralgorithmen für die Erfüllung binärer Bedingungen und den Subgraph-Isomorphismus. J Exp-Algorithmen. 2011, 15 (1,6): 1,1-1,6. 1,64

Der in einer offizielleren Sprache verfasste Preprint des Autors ist der am meisten auf NB-Pfaden basierende Algorithmus, der auch Informationen über einen Versuch enthält, ihn in C ++ zu implementieren:
5. Chernoukhov SA 2020. Preprints.RU. Überprüfung des Isomorphismus zweier Graphen und Suche nach isomorphen "eingeschriebenen" Teilgraphen: Ein Ansatz, der auf der Analyse maximal erweiterter nicht verzweigter Pfade basiert, um das Problem des (Sub-) Graphenisomorphismus zu lösen. DOI: dx.doi.org/10.24108/preprints-3111977

Nützliche Internetquellen zum Thema:
6. coderoad.ru/17480142/Is-li- einfaches Beispiel für Erklärungsalgorithmus-Ulman
7. issue.life/questions / 8176298 .

More articles:


All Articles