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

Question

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

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

• Графики имеют около <20 вершин. </li>
• Графики 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

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

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)) \ в E_2, в противном случае оно равно 0.

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

Answer 3

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

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