Есть ли какой-либо алгоритм для вычисления расстояния редактирования между двумя графиками, включая одни и те же узлы?

Question

Во-первых, я знаю, что было много работ по вычислению расстояния редактирования между двумя графиками. Но большинство алгоритмов GED применяются в общем случае.

Теперь, учитывая мой случай, есть две графы G (V1, E1) и G (V2, E2). Vk представляет собой набор узлов, который включает в себя вершину K (K является константой) и Vk удовлетворяет обоим Vk⊆V1 и Vk⊆V2. Я хочу сохранить соответствие между этими двумя графиками при вычислении расстояния редактирования между ними.

Мне интересно, существует ли какой-либо алгоритм для этой ситуации? Если нет, есть ли у кого-нибудь какие-либо советы для меня? спасибо

PS

Предположим, что VI является узлом в Vk. Меня беспокоит то, что vi остается неизменным, когда G1 преобразуется в G2, что означает, что в vi нет операции (например, заменить vi в G1 на u в G2, удалить vi в G1, вставить vi в G2) во время последовательности операций которые преобразуют G1 в G2.

Answer 1

Существует не алгоритм для решения вашей конкретной проблемы, потому что нет прецедента и нет математической формы. Как я решил бы это:

1) В комментариях вы указываете Vk без изменений, но Ek (1) Ek (2), где Ek (i) - ребра между узлами в Vk для Vi. В этом случае вычислить край add/rem/replace, GED (Vk1, Vk2), игнорируя края из Vk1/2

2) вычислить GED (V1-Vk1, V2-Vk2), игнорируя края между Vi-Vki и Vki , Там, где V1-Vk1 является графиком V1, после удаления всех узлов в Vk и все ребра, связанные с Vk

3) вычислить GED (E (V1-VK1 < -> VK1), E (V2-VK2 < -> VK2)), то есть вычислить GED для замены «ребер, связывающих V1-Vk1 и Vk1» с «ребрами, связывающими V2-Vk2 и Vk2».

4) Добавьте 3 GED вместе.