Definition 5 (Editing Distance):
Definition 6 (Elementary graph edit operations \(e\)):
Ein Graph Edit Operator ist eine der folgenden 6 Operationen:
- Knoten einfügen,
- Knoten entfernen,
- Knoten ersetzen,
- Kanten einfügen,
- Kanten entfernen,
- 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\)):