Definition 5 (Editing Distance):
Definition 6 (Elementary graph edit operations \(e\)):
Ein Graph Edit Operator ist eine der folgenden 6 Operationen:
  1. Knoten einfügen,
  2. Knoten entfernen,
  3. Knoten ersetzen,
  4. Kanten einfügen,
  5. Kanten entfernen,
  6. Kanten ersetzen.
Definition 6 (The cost function of an edit operation \(e_{i}\)):
Der Einfachheit halber ist die Kostenfunktion \(c\) auf der Menge der Operationen \(e_{i}\)\(c(e_{i})\) nicht-negativ: \(0 \le c(e_{i})\) und Element der Reellen Zahlen: \(c(e_{i}) \in \mathbb{R}\). Der Einfachheit halber sind hier alle 6 Operationen gleichermaßen kostenintensiv.
Definition 6 (The set of edit paths for a Graph  \(G\)):