Siziyman: Новая страница: «Тут будет черновичок конспекта, который вовремя сдан не был. == Задача о количестве полны...»

2014-01-09T20:13:51Z

Новая страница: «Тут будет черновичок конспекта, который вовремя сдан не был. == Задача о количестве полны...»

Новая страница

Тут будет черновичок конспекта, который вовремя сдан не был.

== Задача о количестве полных подграфов в графе ==

Дан граф <tex>G</tex>, в котором <tex>N</tex> вершин. Требуется подсчитать количество полных подграфов графа <tex>G</tex> (такие подграфы также называются '''кликами''' — ''clique'').

'''1.''' Наивное решение - перебор всех возможных подграфов и проверка для каждого, что он является кликой, сложность - <tex>O(2^N \times N^2)</tex>

'''2.''' Этот алгоритм можно улучшить до <tex>O(2^N)</tex>. Для этого нужно в функции перебора хранить маску вершин, которые мы ещё можем добавить. Поддерживая эту маску, можно добавлять только «нужные» вершины, и тогда не нужно будет в конце проверять подграф на то что он — клика. Добавлять вершину можно за <tex>O(1)</tex>, используя побитовое «и» текущей маски и строчки матрицы смежности добавляемой вершины.

===Решение с meet-in-the-middle===
Разбиваем граф <tex>G</tex> на 2 графа <tex>{G}_1</tex> и <tex>{G}_2</tex> по <tex>N/2</tex> вершин. Находим за <tex>O(2^{N/2})</tex> все клики в каждом из них.

Теперь надо узнать для каждой клики графа <tex>{G}_1</tex> количество клик графа <tex>{G}_2</tex>, таких, что их объединение — клика. Их сумма и есть итоговый ответ.

Для одной клики <tex>K</tex> графа <tex>{G}_1</tex> может быть несколько подходящих клик в <tex>{G}_2</tex>. О клике <tex>K</tex> мы "знаем" только маску вершин графа <tex>{G}_2</tex>, которые ещё можно добавить. Для каждой такой маски в <tex>{G}_2</tex> нужно предподсчитать ответ.
С помощью динамического программирования предподсчитаем для каждой маски вершин графа <tex>{G}_2</tex> количество клик, вершины которой являются подмножеством выбранной маски. Количество состояний - <tex>2^{N/2}</tex>. Количество переходов:<tex>N</tex> . Асимптотика - <tex>O(2^{N/2} \times N)</tex>.

Для каждой клики <tex>K</tex> (в том числе и пустой) графа <tex>{G}_1</tex> прибавим к глобальному ответу предподсчитанное количество клик, которые можно добавить к <tex>K</tex> (В том числе и пустых). Асимптотика: <tex>O(2^{N/2})</tex>.

Псевдокод подсчёта ответа:
for mаsk = 0 to (1 << N)
dp[mask] = 1 + sum( [p[mask & matrix[i] for i = 0 to N if ((mask & ( 1 << i )) > 0))
ans = sum(dp[clique1_mask[i]])

Итоговая сложность: <tex>O(2^{N/2} \times N)</tex>

Участник:Siziyman - История изменений

Siziyman: Новая страница: «Тут будет черновичок конспекта, который вовремя сдан не был. == Задача о количестве полны...»