Изменить расстояние между двумя графиками

Мне просто интересно, как, например, для строк, где у нас есть расстояние Левенштейна (или расстояние редактирования) между двумя строками, есть ли что-то подобное для графов?

Я имею в виду скалярную меру, которая идентифицирует число атомных операций (node и вставка/удаление краев), чтобы преобразовать граф G1 в график G2.

Ответы

Ответ 1

Я думаю, что расстояние редактирования графа - это мера, которую вы искали.

Расстояние редактирования графика измеряет минимальное количество операций редактирования графа для преобразования одного графика в другой, а разрешенные операции редактирования графа включают в себя:

  • Вставить/удалить изолированную вершину
  • Вставить/удалить ребро
  • Изменить метку вершины/ребра (если помечены графы)

Однако вычисление расстояния редактирования графика между двумя графиками NP-hard. Наиболее эффективным алгоритмом для вычисления этого является алгоритм, основанный на A *, и существуют другие субоптимальные алгоритмы.

Ответ 3

Для общего графика это NP-полная проблема, как упоминалось в их ответе. Но для древовидного графика существуют хорошо известные полиномиальные алгоритмы. Может быть, самым известным из них является алгоритм "Чжан Шаша", который был опубликован в 1989 году.

Ответ 4

Примечание:

Расстояние Левенштейна (или расстояние редактирования) находится между двумя строками

Но на графике вы должны искать между по крайней мере N! положение, в котором вы находите Identity каждого ребра и вершины. Вы можете легко сравнить два графика по уникальному индексу, но Главный вопрос - определить идентификацию для каждой вершины и края. Этот вопрос (найти тождество для каждой вершины и ребра на двух графиках, которые они могут преобразовать) очень сложно и называется проблемой изоморфизма (NP-Complete). Вы можете искать график изоморфизма.