Расстояние редактирования графа — это коэффициент сходства (или несходства) между двумя графами . Концепцию расстояния редактирования графа впервые сформулировали математически Альберто Санфелиу и Кинг-Сан Фу в 1983 . Главное приложение расстояния редактирования графа — в , таких как устойчивое распознавание образов в машинном обучении .

Расстояние редактирования графа между двумя графами связано с между строками . При интерпретации сток как связных направленных ациклических графов с максимальной степенью два, классические определения расстояния редактирования, такие как расстояние Левенштейна , расстояние Хэмминга и расстояние Джаро — Винклера , могут интерпретироваться как расстояния редактирования графов между подходящими графами. Подобным образом, расстояние редактирования графа является обобщением расстояния редактирования дерева между деревьями с корнями .

Формальные определения и свойства

Математическое определение расстояния редактирования графа зависит от определения графов, для которых расстояние определяется. Например, оно зависит от того, размечены ли и как размечены вершины и рёбра графа, а также от того, является ли граф ориентированным . В общем случае, если дан набор операций редактирования графа (известных также как элементарные операции над графами ), расстояние редактирования графа между двумя графами ${\displaystyle g_{1}}$ и ${\displaystyle g_{2}}$ , записываемое как ${\displaystyle GED(g_{1},g_{2})}$ , можно определить как

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$ ,

где ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$ означает набор путей преобразования ${\displaystyle g_{1}}$ в ( изоморфный графу) ${\displaystyle g_{2}}$ , а ${\displaystyle c(e)\geqslant 0}$ равна стоимости каждой операции редактирования ${\displaystyle e}$ .

Набор элементарных операций над графом обычно включает:

вставку вершины — в граф вставляется одна новая помеченная вершина.

удаление вершины — из графа удаляется одна (зачастую не связанная с другими) вершина.

подстановка вершины — изменение метки (или цвета) данной вершины.

вставка ребра — в граф вставляется новое цветное ребро между парой вершин.

удаление ребра — удаление одного ребра между парой вершин.

подстановка ребра — изменение метки (или цвета) данного ребра.

Кроме этого, но более редко, включаются такие операции, как разбиение ребра , при котором вставляется новая вершина в ребро (что приводит к образованию двух рёбер), и стягивание ребра , которое удаляет вершину степени два между рёбрами (одного цвета) с объединением двух рёбер в одно. Хотя такие сложные операции можно определить в терминах более простых преобразований, их использование позволяет лучше параметризовать функцию цены ${\displaystyle c}$ , когда оператор дешевле, чем сумма его составляющих.

Приложения

Расстояние редактирования графа находит применение в распознавании рукописного ввода , распознавании отпечатков пальцев и хемоинформатике .

Алгоритмы и сложность

Точные алгоритмы вычисления расстояния редактирования графа между парой графов обычно преобразуют проблему в задачу поиска минимального пути преобразований между двумя графами. Вычисление оптимального пути редактирования сводится к поиску пути или задаче о кратчайшем пути , часто реализуемой как алгоритм поиска A* .

Кроме точных алгоритмов, известно много эффективных аппроксимационных алгоритмов .

Несмотря на то, что вышеупомянутые алгоритмы работают на практике иногда хорошо, в общем случае задача вычисления расстояния редактирования графа является NP-полной (доказательство этого доступно в разделе 2 на сайте ) и даже трудна для аппроксимации (формально, она APX -трудна ).

Примечания

Литература