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

Question

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

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

Answer 1

Примечание:

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

Вы должны смотреть на бумаге A survey of graph edit distance