Расстояние редактирования графа — это коэффициент сходства (или несходства) между двумя графами. Концепцию расстояния редактирования графа впервые сформулировали математически Альберто Санфелиу и Кинг-Сан Фу в 1983. Главное приложение расстояния редактирования графа — в , таких как устойчивое распознавание образов в машинном обучении.
Расстояние редактирования графа между двумя графами связано с между строками. При интерпретации строк как связных направленных ациклических графов с максимальной степенью два, классические определения расстояния редактирования, такие как расстояние Левенштейна, расстояние Хэмминга и расстояние Джаро — Винклера, могут интерпретироваться как расстояния редактирования графов между подходящими графами. Подобным образом, расстояние редактирования графа является обобщением расстояния редактирования дерева между деревьями с корнями.
Формальные определения и свойства Математическое определение расстояния редактирования графа зависит от определения графов, для которых расстояние определяется. Например, оно зависит от того, размечены ли и как размечены вершины и рёбра графа, а также от того, является ли граф ориентированным. В общем случае, если дан набор операций редактирования графа (известных также как элементарные операции над графами), расстояние редактирования графа между двумя графами и , записываемое как , можно определить как , где означает набор путей преобразования в (изоморфный графу) , а равна стоимости каждой операции редактирования .
Набор элементарных операций над графом обычно включает:
вставку вершины — в граф вставляется одна новая помеченная вершина. удаление вершины — из графа удаляется одна (зачастую не связанная с другими) вершина. подстановка вершины — изменение метки (или цвета) данной вершины. вставка ребра — в граф вставляется новое цветное ребро между парой вершин. удаление ребра — удаление одного ребра между парой вершин. подстановка ребра — изменение метки (или цвета) данного ребра.
Кроме этого, но более редко, включаются такие операции, как разбиение ребра, при котором вставляется новая вершина в ребро (что приводит к образованию двух рёбер), и стягивание ребра, которое удаляет вершину степени два между рёбрами (одного цвета) с объединением двух рёбер в одно. Хотя такие сложные операции можно определить в терминах более простых преобразований, их использование позволяет лучше параметризовать функцию цены , когда оператор дешевле, чем сумма его составляющих.
Приложения Расстояние редактирования графа находит применение в распознавании рукописного ввода, распознавании отпечатков пальцев и хемоинформатике.
Алгоритмы и сложность Точные алгоритмы вычисления расстояния редактирования графа между парой графов обычно преобразуют проблему в задачу поиска минимального пути преобразований между двумя графами. Вычисление оптимального пути редактирования сводится к поиску пути или задаче о кратчайшем пути, часто реализуемой как алгоритм поиска A*.
Кроме точных алгоритмов, известно много эффективных аппроксимационных алгоритмов.
Несмотря на то, что вышеупомянутые алгоритмы работают на практике иногда хорошо, в общем случае задача вычисления расстояния редактирования графа является NP-полной (доказательство этого доступно в разделе 2 на сайте Zeng et al.) и даже трудна для аппроксимации (формально, она APX-трудна).
Примечания
Литература
Категория:Теория графов Категория:Алгоритмы на графах Категория:Вычислительные задачи теории графов Категория:Меры похожести и расстояния