Мне просто интересно, как, например, для строк, где у нас есть расстояние Левенштейна (или расстояние редактирования) между двумя строками, есть ли что-то подобное для графов?
Я имею в виду скалярную меру, которая идентифицирует число атомных операций (node и вставка/удаление краев), чтобы преобразовать граф G1 в график G2.
Я думаю, что расстояние редактирования графа - это мера, которую вы искали.
Расстояние редактирования графика измеряет минимальное количество операций редактирования графа для преобразования одного графика в другой, а разрешенные операции редактирования графа включают в себя:
Однако вычисление расстояния редактирования графика между двумя графиками NP-hard. Наиболее эффективным алгоритмом для вычисления этого является алгоритм, основанный на A *, и существуют другие субоптимальные алгоритмы.
Вы должны посмотреть на статью Обзор расстояния редактирования графа
Для общего графика это NP-полная проблема, как упоминалось в их ответе. Но для древовидного графика существуют хорошо известные полиномиальные алгоритмы. Может быть, самым известным из них является алгоритм "Чжан Шаша", который был опубликован в 1989 году.
Примечание:
Расстояние Левенштейна (или расстояние редактирования) находится между двумя строками
Но на графике вы должны искать между по крайней мере N! положение, в котором вы находите Identity каждого ребра и вершины. Вы можете легко сравнить два графика по уникальному индексу, но Главный вопрос - определить идентификацию для каждой вершины и края. Этот вопрос (найти тождество для каждой вершины и ребра на двух графиках, которые они могут преобразовать) очень сложно и называется проблемой изоморфизма (NP-Complete). Вы можете искать график изоморфизма.