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

Question

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

Answer 1

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

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