Edit Abstand zwischen zwei Graphen

Question

Ich frage mich nur, ob für Strings, wo wir die Levenshtein Abstand (oder Abstand bearbeiten) zwischen zwei Strings haben, gibt es etwas ähnliches für Graphen?

Ich meine, ein skalares Maß, das die Anzahl der atomaren Operationen (Einfügen und Löschen von Knoten und Kanten) identifiziert, um ein Diagramm G1 in ein Diagramm G2 zu transformieren.

Answer 1

Hinweis:

Die Levenshtein-Distanz (oder Edit-Distanz) zwischen zwei Strings

Aber in Graph sollten Sie zwischen mindestens N suchen! Position, dass Sie die Identität jeder Kante und jeden Eckpunkts finden. Sie können einfach zwischen zwei Graphen durch eindeutige Index vergleichen, aber Die Hauptfrage ist definieren Identität für jeden Eckpunkt und edge.this Frage (Identität für jeden Eckpunkt und Kante in zwei Graphen finden, die sie zu transformieren) ist sehr schwer und war genanntes Isomorphie-Problem (NP-vollständig). Sie können über Isomorphie Graphen suchen.

Answer 2

Für eine allgemeine Grafik ist es ein NP-vollständiges Problem, wie andere in ihrer Antwort erwähnt haben. Aber für das Baumdiagramm gibt es wohlbekannte Polynomalgorithmen. Mai berühmteste von ihnen ist "Zhang Shasha" -Algorithmus, der im Jahr 1989 veröffentlicht wurde.

Answer 3

Ich denke, Diagramm bearbeiten Abstand ist das Maß, das Sie gesucht haben.

Graph Editierdistanz misst die minimale Anzahl von Graphen Editieroperationen ein Diagramm, um einen anderen zu transformieren und die erlaubten Graph Editieroperationen umfaßt:

• Einfügen/Löschen eine isolierte Ecke
• Einfügen/Löschen eine Kante
• das Etikett eines Scheitels/edge ändern (wenn markiert Graphen)

jedoch den Graphen bearbeiten Abstand zwischen zwei Graphen Computing ist NP-hart. Der effizienteste Algorithmus zur Berechnung ist ein A * -basierter Algorithmus, und es gibt andere suboptimale Algorithmen.

Answer 4

Sie auf dem Papier aussehen sollte A survey of graph edit distance