%magic to do it work

\Section{Динамика на подмножествах. Раскраска графа.}{26 октября}{Лобанов Артём \\ и добрые люди из чата}

\Subsection{Постановка задачи}

    Дан граф на n вершинах. Требуется раскрасить вершины в минимальное количество цветов так, чтобы концы любого ребра имели различные цвета.
    
\Subsection{Решение за $\O(4^n)$}

Назовём множество вершин "хорошим", если не существует ребра, оба конца которого лежат в этом множестве. Заметим, что вершины из хорошего множества всегда можно покрасить в один цвет.
Сначала предподсчитаем для каждого подмножества вершин, является ли оно хорошим. Сделаем это в лоб: переберём все подмножества вершин, переберём все возможные пары вершин из этого подмножества и проверим наличие ребра. Вершин в подмножестве не больше n, подмножеств $2^n$, поэтому алгоритм будет работать за $\O(2^nn^2)$.

Теперь решим исходную задачу. Рассмотрим некотое подмножество вершин A. $dp[A]$ - в какое минимальное число цветов можно раскрасить подграф на вершиинах из A. Давайте выберем, какие вершины из A мы покрасим в первый цвет. Переберём все подмножества вершин и, если текущее (назовём его X) является подмножеством A и $good[X] == true$ (критерий того, граф на вершинах из X можно покрасить в 1 цвет), то прорелаксируем ответ для A значением $dp[A \backslash X] + 1$.

Итоговая асимптотика $\O(2^n \cdot n^2 + 2^n \cdot 2^n) = \O(4^n)$.

\Subsection{Эффективный перебор всех подмножеств заданного множества}

Пусть надо перебрать все непустые подмножества множества A. Сделать это можно следующим кодом:

	\begin{code}
		for (int X = A; X > 0; X = (X - 1) & A) {
		    ...
		}
		
	\end{code}
	
	1) X точно подмножетво A т.к. мы на каждой итерации оставляем только те биты, которые были в A
	
	2) На каждой итерации X уменьшается т.к. из него вычитают 1 и делают \& с А (а эта операция не может увеличить число). Из этого, в частности, следует, что код отработает за конечное время.
	
	3) Заметим, что на каждой итерации мы берём лексикографически максимальное подмножество, меньшее текущего (если сравнивать множества как двоичные записи кодирующих их чисел). Действительно, вычитая единицу мы заменяем последнюю 1 на 0, не трогаем всё что было до неё (следовательно новое подмножество меньше), а все доступные биты (т.е. те, которые были в А) после неё делаем 1 (поэтому среди всех меньших, полученное множество лексикографически максимальное). Тогда раз мы начали с лексикографически максимального и закончили минимальным, то мы переберём все подмножества.
	
	\begin{tabular}{lcl}
	$A$ &=& 10111010011010\\
	$X$ &=& \textcolor{red}{1}0\textcolor{red}{101}0\textcolor{red}{1}00\textcolor{red}{10}0\textcolor{red}{0}0\\
	$X - 1$ &=& \textcolor{red}{1}0\textcolor{red}{101}0\textcolor{red}{1}00\textcolor{blue}{0}\textcolor{green}{1111}\\
	$(X - 1) \& A$&=&\textcolor{red}{1}0\textcolor{red}{101}0\textcolor{red}{1}00\textcolor{blue}{0}\textcolor{green}{1}0\textcolor{green}{1}0\\
	 \end{tabular}
    
    Этот алгоритм позволяет перебирать подмножества за их количество, а не за $2^n$.
    
    Замечание: пустое множество, если оно требуется, придётся разобрать отдельно.
    
\Subsection{Решение за $\O(3^n + 2^nn^2)$}

Давайте теперь при переходе динамики перебирать только подмножества текущего множества. Оценим время работы. Если множество содержало k элементов, то количество его подмножеств $2^k$. Сколько раз мы будем рассматривать множество, содержащее k элементов? $C_n^k$. Тогда суммарное время работы можно оценить как $\sum\limits_{k = 0}^n 2^k \cdot C_n^k = \sum\limits_{k = 0}^n 1^{n - k}2^k \cdot C_n^k = (1 + 2)^n = 3^n$.

С учётом предподсчёта (good[i]) итоговая асимптотика будет $\O(3^n + 2^nn^2)$.

\Subsection{Эффективный подсчёт массива good ($\O(2^n)$)}

Примечнаие: Мы умеем находить за $\O(1)$ младший единичный бит числа, но не умеем находить его номер. Пока мы будем использовать массив index, который по числу будет хранить какой степенью двойки оно является ($index[2^n] = n$). т.к. мы будем использовать только n ячеек этого массива, то можно заменить его на HashMap. В одном из следующих конспектов будет рассказано, как обойтись без этого массива.

Заметим, что можно считать массив good более эффективно: выберем одну конкретную вершину из текущего множества, проверим, что из неё нет рёбер в это множество (если хранить соседей вершиы в таком же виде, как и множества, то это можно делать за 1 - просто проверить что пересечение этих множеств пусто) и проверим, с помощью обращения к уже посчитанной ячейке good, что множество без этой вершины хорошее. Итоговая асимптотика $\O(2^n)$, что позволяет уменьшить асимптотику решения основной задачи до $\O(3^n + 2^n) = \O(3^n)$

\Subsection{Перебор всех максимальных по включению независимых подмножеств}

Вершины степени 0 входят во все максимальные независимые подмножества. Их возьмём сразу.
Выберем вершину v с минимальной степенью. Пусть её степень d. Мы либо возьмём её в ответ (делаем рекурсивный вызов, выкинув её и её соседей из графа => вершин останется n - d - 1), либо возьмём одного из её соседей (степени соседей не меньше d, для каждого делаем рекурсивный вызов без вершины v, без текущего соседа и без его соседей => вершин останется не больше n - d - 1). Итого, если обозначить время работы на компоненте размера n, то $T(n) <= (d + 1)T(n - d - 1)$. 

    Докажем, что $T(n) = O(3^{n/3})$. Докажем по индукции. 
    
    $T(n) <= (d + 1)T(n - d - 1) <= (d + 1) \cdot C \cdot 3^{\frac{n - d - 1}{3}} = C \cdot 3^{\frac{n}{3}} \cdot (d + 1) 3^{-\frac{d+1}{3}} <= C \cdot 3^{\frac{n}{3}}$
    
    Докажем последнее неравенство. Рассмотри функцию $f(x) = x \cdot 3^{-\frac{x}{3}}$.
    
    $f'(x) = (x \cdot 3^{-\frac{x}{3}})' = 3^{-\frac{x}{3} - 1} \cdot (3 - x \ln 3)$
    
    Следовательно $f(x)$ убывает при x больших $\frac{3}{\ln 3}$ (это примерно 2,7).
    
    Заметим, что $1 = f(3) > f(2) > f(1)$. Т.к. после 3 функция убывает, то и все последующие значения меньше 1.


\Subsection{Решение задачи о покраске графа за $\O(2.44^n)$}

Теперь для каждого рассматриемого множества будем перебирать только его максимальные по включению независимые подмножества. Тогда время работы можно оценить как $\sum\limits_{k = 0}^n 1.44^k \cdot C_n^k = \sum\limits_{k = 0}^n 1^{n - k}1.44^k \cdot C_n^k = (1 + 1.44)^n = 2.44^n$. Т.е. асимптотика станет $\O(2.44^n)$.

Замечание: 1.44 на самом деле $\sqrt[3]{3}$, 2.44, соответственно, $\sqrt[3]{3} + 1$
 