Подсчет экземпляров подграфа

Question

Скажем, у меня есть большой (несколько тысяч узлов) направленный график грамм и намного меньше (3-5 узла) направленный график грамм. Отказ Я хочу посчитать сколько изоморфизмов грамм находятся в грамм. Отказ Другими словами, я хочу знать, сколько уникальных наборов узлов в грамм совпадение грамм. Отказ Я понимаю, что это пример проблемы изоморфизма субграфа и поэтому NP-Complete. Тем не менее, учитывая, что вы можете предположить, что грамм Маленький, есть ли достаточно эффективный алгоритм для этого?

Answer 1

Хотя график изоморфизма является NP-Complete в целом, проблемы, которые вы сталкиваетесь в реальном мире, часто довольно легко. Достаточно простой грубой силы: пусть M_i быть набором отображений из первых узлов I к узлам Г. Начните с m_0 Содержащие пустую карту и продлите его один узел за раз, отбрасывая любые карты, которые нарушают ограничение x->y IFF. m(x)->m(y).

Вы захотите заказать узлы в G, чтобы многие обрезки происходят рано. Предполагая, что ваши графики довольно редкие, вы захотите заказа, который заканчивается как можно раньше, возможно, DFS из узла высшего класса.