У меня есть два графика G1 и G2, которые не изоморфны.Мне нужно сделать новый граф G1 'таким, чтобы с минимальными изменениями в G1 он имел узлы как G1, так и G2.Например, предположим, что в G1 есть узел n1 с тремя соединительными узлами n11, n12, n13.Если теперь «соответствующий» узел n2 в G2 имеет 5 узлов n21, n22, n23, n24, n25, то n1 'в G1' также должен иметь пять узлов n11 ', n12', n13 ', n14', n15 '.Первые три скопированы из G1 и двух дополнительных узлов, которые будут иметь значение последнего из трех.Дерево, исходящее из дополнительных узлов, будет либо полностью новым, либо будет содержать несколько дополнительных узлов из G1, которые не имеют эквивалентных узлов в G2 (в некотором смысле не «исчерпаны»).
Проблемы состоят в том, что 1) найти наиболее подходящее начальное число в качестве начальной точки, чтобы начальные виды были как можно более похожими 2) Построить дерево из дополнительных узлов, сохраняя количество добавленных узлов минимальным
Редактировать:
Я попытаюсь объяснить это далее с помощью иллюстрации.Мои знания теории графов очень поверхностны, поэтому извините, если что-то звучит глупо.
Я хочу получить граф, который с минимальным количеством манипуляций с узлами может принять форму одного из двухнеизоморфные исходные графы.
В приведенном выше примере граф G 'может принимать две формы G или H с некоторым количеством перетасовок узлов pf.
1) Чтобы сделать это G, мы сохраняем все оранжевые узлы на своих местах.Пунктирные узлы «сливаются» с соседними узлами.Таким образом, B21 'будет иметь значение A21 и будет в том же положении (растворяя соответствующие ребра).Аналогично произойдет с парами B31'-A31, B14'-A15, B25'-B23, A32'-A22 и A23'-A32.С этой конфигурацией график будет напоминать G полностью, без "торчащих" ребер *
2) Чтобы сделать его изоморфным с H, A11 и A12, примут значения A13, A32 и A32 ', что у A23, A23 ', что из A22.Пунктирные узлы «выйдут» из своих объединенных позиций.
Проблема в том, чтобы найти G '.Возможно, операции с готовым графом не существует, или решение невозможно, но любой указатель для достижения этой цели с любой степенью аппроксимации и эффективности приветствуется.
Примечание: начальные узлы A1 и B1 являются произвольными.Первая половина проблемы заключается в идентификации этих узлов, чтобы представления были максимально похожими.