Простой способ определить, является ли данный граф подграфом какого-либо другого графа?

Question

Я ищу алгоритм, позволяющий проверить, является ли данный граф подграфом другого данного графа.

У меня есть несколько условий, чтобы сделать эту NP-полную задачу более осуществимой.

• Графы имеют примерно <20 вершин.
• Графики DAG.
• Все вершины не имеют уникальных меток, и соответствующие вершины в основном графе и подграфе должны иметь одинаковую метку.Я не знаю, правильно ли я использую терминологию (потому что я не проходил курс теории графов...).Это будет что-то вроде:

Линейный граф A--B является подграфом A--B--A, но A--A не является подграфом A--B--A.

Любые предложения хороши.Кстати, это не вопрос домашнего задания.:D

Answer 1

Если этикетки уникальны, для графика размера N, Существуют O(N^2) края, предполагая, что между каждой парой вершин нет самостоятельных петлей или нескольких краев. Давайте использовать E по количеству краев.

Если вы хлежаете ребра на родительском графике, вы можете пройти через края подграфа, проверить, находится ли каждый из них в хэш -таблице (и в правильном количестве, при желании). Вы делаете это один раз для каждого края, поэтому O(E).

Назовем график G (с N вершины) и возможный подграф G_1 (с M вершины), и вы хотите найти G_1 is in G.

Поскольку этикетки не уникальны, вы можете с динамическим программированием, вместо того, чтобы построить подзадачи, вместо того, чтобы иметь O(2^N) подзадачи, по одной для каждого подграфа, у вас есть O(M 2^N) Подпроекты - одна для каждой вершины в G_1 (с M вершины) с каждым из возможных подграфов.

G_1 is in G = isSubgraph( 0, empty bitmask)

и штаты настроены как таковые:

isSubgraph( index, bitmask ) =
   for all vertex in G
       if G[vertex] is not used (check bitmask)
          and G[vertex]'s label is equal to G_1[index]'s label
          and isSubgraph( index + 1, (add vertex to bitmask) )
               return true
   return false

с базовым случаем index = M, и вы можете проверить на равенство края, учитывая битмаски (и неявное отображение метки). В качестве альтернативы, вы также можете провести проверку в операторе IF - просто проверьте, что данное текущее index, текущий подграф G_1[0..index] равно G[bitmask] (с тем же неявным отображением метки) перед повторным.

За N = 20, это должно быть достаточно быстро.

(Добавьте свое меморандум, или вы можете переписать это, используя дни DP).

Answer 2

Хорошо, я должен задать очевидный вопрос. 1. У вас есть двадцать вершин. Сначала пройдите каждый график, алфавитный порядок среди братьев и сестер, чтобы получить строки. 2. Один график представляет собой подграф другой IFF одна строка в другой.

Итак, что еще скрывается в спецификации проблемы, чтобы сделать это невозможным?

Answer 3

Вы можете рассматривать это как проблему выравнивания.По сути, вы хотите создать инъективное отображение. а который отображает каждую вершину в V_1 в вершину в V_2.Карта выравнивания а можно оценить следующим образом:

s(a) = \sum_{(v,w) \in E_1} \sigma(v, w, a(v), a(w)),

где \sigma(v, w, a(v), a(w)) = 1, если (a(v), a(w)) \in E_2, в противном случае оно равно 0.

Я думаю, что это можно сформулировать в виде целочисленной линейной программы.