Простой способ определить, является ли данный график подграфом некоторого другого графика?
Я ищу алгоритм, чтобы проверить, является ли данный график подграфом другого данного графика.
У меня есть немного условий сделать этот NP, который полная проблема укусила более выполнимый..
- Графики имеют приблизительно <20 вершин.
- Графики являются DAG.
- Все вершины неисключительно маркированы, и соответствующие вершины в основном графике и подграфе должны иметь ту же маркировку. Я не знаю, использую ли я корректную терминологию (потому что я не взял курс теории графов...). Это будет что-то как:
Линейный график - B является подграфом - B - A, но - A не является подграфом - B - A.
Любые предложения прекрасны. Это не вопрос о домашней работе btw.:D
3 ответа
Если метки уникальны, для графа размером N имеется O (N ^ 2) ребер, при условии, что между каждой парой нет петель или нескольких ребер. вершин. Давайте использовать E для количества ребер.
Если вы хешируете заданные ребра в родительском графе, вы можете пройтись по ребрам подграфа, проверяя, есть ли каждое из них в хэш-таблице (и в правильном количестве, если необходимо). Вы делаете это один раз для каждого ребра, поэтому O (E) .
Назовем граф G (с N вершинами) и возможный подграф G_1 (с M вершин), и вы хочу найти G_1 находится в G .
Поскольку метки не уникальны, вы можете с помощью динамического программирования вместо этого создавать подзадачи как таковые - вместо O (2 ^ N) подзадач, по одной для каждого подграфа, у вас будет O (M 2 ^ N) подзадач - по одной для каждой вершины в G_1 (с M вершинами) с каждым из возможных подграфов.
G_1 находится в G = isSubgraph (0, пустая битовая маска)
, и состояния настроены как таковые:
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 - просто проверьте, что данный текущий индекс , текущий подграф G_1 [0..index] равен G [ битовая маска] (с таким же неявным отображением меток) перед рекурсией.
Для N = 20 этого должно быть достаточно быстро.
(добавьте заметку, или вы можете переписать ее, используя DP снизу вверх).
Хорошо, я должен задать очевидный вопрос. 1. У вас есть двадцать вершин. Пройдитесь по каждому графу в глубину сначала в алфавитном порядке среди братьев и сестер, чтобы получить строки. 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)) \ in E_2, в противном случае это 0.
Я думаю, что это можно сформулировать в виде целочисленной линейной программы.