

%magic to do it work

\Section{Раскараска рёбер двудольных графов}{25 марта}{Лобанов Артём}

\Subsection{Вспомним прошлую лекцию}

    На прошлом занятии мы научились красить рёбра двудольного графа путём дополнения его до D-регулярного и разбиения его на D совершенных паросочетаний. Алгоритм работал за $\O(D^2 \cdot |V|^2)$. Сегодня мы научимся разбивать D-регулярный граф на D совершенных паросочетаний за $\O(D|V|^2\log D)$.
    
    Пусть D - чётно. Тогда мы можем выделить эйлеров цикл в каждой компоненте. Рассмотрим одну компоненту. Очевидно, что эйлеров цикл имеет чётную длину т.к. граф был двудольным (нечётный цикл нельзя раскрасить в два цвета). Построим два новых графа: в первый попадут рёбра эйлерова цикла на чётных позициях, во второй - на нечётных. Заметим, что степень каждой вершины уменьшилась ровно в два раза. Почему? Рассмотрим два последовательных ребра цикла. Пусть их общая вершина v. Раньше они давали вклад в её степень 2, а теперь одно из них имеет чётный номер и даёт вклад 1 в её степень в первом графе, а второе - нечётный номер и вклад 1 во втором графе. Через каждую вершину цикл пройдёт $\frac{D}{2}$ раз. Тогда если изначально у нас был D-регулярный граф, то в итоге мы получим два  $\frac{D}{2}$-регулярных графа.
    
    Представим, что D-степень двойки. Тогда за $\O(\log D)$ итераций мы получили бы D \linebreak 1-регулярных графов, а 1-регулярные графы - это как раз искомые совершенные паросочетания.
    
    Но мир настолько несовершенен, что далеко не все числа являются степенями двойки. Поэтому прежде чем перейти от D-регулярных графов к $\frac{D}{2}$ регулярным иногда придётся делать одно отщепление совершенного паросочетания, как в прошлом алгоритме. Итак, пусть $T(k)$ - полное время работы алгоритма если граф уже разбит на k-регулярные. Тогда $T(k) = D|V|^2 + T(\frac{k}{2})$, где $D|V|^2$ - верхняя оценка на время отщепления совершенных паросочетаний у подграфов нечётной регулярности (временем на поиск эйлерова цикла можно пренебречь). Почему $D|V|^2$? Отщепление совершенного паросочетания происходит за $\O(VE_i)$, тогда в сумме это займёт $\sum VE_i = V \sum E_i = VE$, а $E = \O(DV)$. Тогда $T(k) = D|V|^2 \log k$. А значит время работы алгоритма $\O(D|V|^2 \log D)$ т.е. $\O(|V|^3 \log V)$ в худшем случае.
    
\Subsection{Паросочетание, покрывающее вершины степени D}

    \begin{Lm}
      В двудольном графе существует паросочетание, покрывающее все вершины максимальной степени.
    \end{Lm}
    
    Действительно, вспомним алгоритм раскраски рёбер с предыдущей лекции. Пусть изначльно максимальная степень была равна D. Проделаем одну итерацию. Оставим теперь только изначальные рёбра и вершины. Очевидно, степень всех вершин неувеличилась. После удаления некоторого паросочетания (пересечение удалённого совершенного паросочетания и множества изначальных рёбер графа) максимальная степень вершин в графе не больше $D - 1$ => удалённое паросочетание покрывало все вершины степени D. А значит, такое паросочетание существует. Лемма доказана.

\Subsection{Покраска рёбер за $\O(E^2)$}

    Алгоритм прост - найдём паросочетание из леммы, удалим его и перейдём к меньшему графу. Т.к. максимальная степень вершин в графе от этого строго уменьшится, то не позже чем через D итераций мы получим пустой граф.
    
    Пусть $A$ - вершины первой доли, имеющие максимальную степень, $B$ - вершины второй доли, имеющие максимальную степень. Сначала последовательно запустим dfs-ы из Куна из каждой вершины A и покроим паросочетанием все интересующие нас вершины из первой доли.
    
    Почему это сработает? Заметим, что все покрытые вершины первой доли лежат в $A$. Пока мы ещё не добавили ни одного ребра в паросочетание, это утверждение верно. Дальше по индукции. Пусть мы нашли чередующийся путь. Начало найденного пути лежит в A по алгоритму. Все остальные вершины из A в пути были покрыты паросочетанием и на предыдущей итерации => и теперь утверждение верно. Докажем теперь, что если $a$ лежит в A и ещё не покрыто паросочетанием, то существует нечётный чередующийся путь из $a$. Рассмотрим симметрическую разность $M$ (текущего паросочетания) и $P$ (паросочетания из леммы). Вершина $a$ имеет в ней степень 1 т.к. покрыта $P$, но не покрыта $M$. Значит она - начало некоторого чередующегося пути. Чем он может оканчиваться? Если вершиной из второй доли, то мы нашли чередующийся нечётный путь из $a$. Победа. Пусть он заканчивается в вершине первой доли (а значит мы пришли в неё по ребру из M). Но тогда она лежит в A (т.к. покрыта $M$) => она должна быть покрыта и P => она не может быть концом пути т.к. её степень в симметрической разности чётна. Значит, такая ситуация невозможна. Уф.
    
    Итак, мы покрыли паросочетанием все интересующие нас вершины первой доли. Теперь займёмся вершиными второй доли. Модифицируем dfs из Куна: теперь он заканчивается (и инвертирует рёбра на найденном пути) не только если нашёл нечётный чередующийся путь (т.е пришёл в свободную вершину), но и если пришёл в вершину той же доли, из которой стартовал, но которая не лежит в B. Докажем, что какой-то из этих путей (чётный, с концом в неинтересной вершине, или нечётный) всегда найдётся при запуске из непокрытой вершины $b$ из B.
    
    Рассмотрим симметрическую разность $M$ (текущего паросочетания) и $P$ (паросочетания из леммы). Вершина $b$ имеет в ней степень 1 т.к. покрыта $P$, но не покрыта $M$. Значит она - начало некоторого чередующегося пути. Чем он может оканчиваться? Если вершиной из первой доли, то мы нашли чередующийся нечётный путь из $b$. Победа. Пусть он заканчивается в вершине второй доли. Если последняя вершина не интересная (не лежит в B), то опять же победа. Иначе она должна быть покрыта P, а т.к. мы пришли в неё по ребру из M, то её степень 2 => она не может быть концом пути. Уф.
    
    Тогда вызвав модифицированный dfs из Куна из каждой непокрытой вершины B, мы посторим паросочетание покрывающее A и B => искомое.
    
    Оценим время работы. Пусть на i-ой итерации мы удалили паросочетание размера $M_i$. Тогда все итерации займут не больше $\sum EM_i = E \cdot \sum M_i = E \cdot E = E^2$. 
    
        
    
    
    
    
\Section{Вершинные покраски}{25 марта}{Лобанов Артём}

\Subsection{Теорема Брукса}
    \begin{Thm}
      Вершины связного графа, в котором все вершины имеют не больше D соседей, можно раскрасить всего в D цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется D + 1 цвет.
    \end{Thm}
    
    Мы не будем доказывать эту теорему. Заметим только, что оценка сверху в D + 1 цвет очевидна. Действительно, давайте красить вершины в произвольном порядке. При покраске очередной вершины рассмотрим всех её покрашеных соседей и найдём цвет, которым ещё никто не покрашен. Т.к. соседей не больше D, а цветов D + 1, то свободный цвет всегда найдётся.
    
\Subsection{Алгоритм покраски вершин}

    На практике хорошо применим простой рекурсивный алгоритм: удалим вершину v минимальной степени, решим задачу для меньшего графа, вернём v в граф и покрасим в mex ($mex(X)$ - минимальное число из $N_0$, не встречающееся в $X$) цветов соседей. Для улучшения работы среди всех вершин минимальной степени рекомендуется выбирать случайную. Время работы зависит от структуры данных, которая используется для поиска вершины минимальной степени. Если использовать обыкновенную кучу, то время работы будет $\O(E \log V)$. Существует вариант реализации, работающий за $\O(E)$
    
\Subsection{Интересный факт про планарые графы}
    \begin{Lm}
      В любом планарном графе существует вершина степени не больше 5.
    \end{Lm}
    Примем лемму без доказательства. 

\Subsection{Покраска планарного графа в 6 цветов}

    Благодаря последней лемме, описанный выше рекурсивный алгоритм покраски будет использовать не больше 6 цветов т.к. при покраске v у неё будет не больше 5 соседей.

\newpage
    
\Subsection{Покраска планарного графа в 5 цветов}

    Модифицируем алгоритм из пункта 2, чтобы красить планарный граф в 5 цветов. Если степень вершины v при покраске оказалась меньше 5 или цвета каких-то соседей совпали, то их mex и так будет меньше 5 (цвета нумеруются с 0). Рассмотрим плохой случай.
    \vspace*{-1em}
        \begin{center}
            \includegraphics[scale=1]{lobanov/vertex_coloring.png}
        \end{center}
    \vspace*{-1em}
    
    Разноцветные соседи - это грустно. Давайте попробуем перекрасить кого-нибудь. Пусть этим "кто-нибудь" ~ будет вершина 1 с рисунка. И перекрасим мы ей в цвет вершины 3. Но у вершины 1 могли быть соседи цвета вершины. Жаль. Придётся иx перекрасить в цвет вершины 1. Таким образом, нам придётся перекрасить всю компоненту связности из вершин красного и синего цвета (по рисунку), в которой лежит первая вершина. Если при этом не перекрасилась вершина 3, то победа - можем покрасить v в красный. Иначе существет красно-синий путь из вершины 1 в вершину 3. Придётся смириться с этим. Но не будем терять надежду - попробуем перекрасить вершину 2 в цвет вершины 4. Но вдруг у нас не получится? Тогда будет существовать жёлто-зелёный путь из вершины 2 в вершину 4. Но это не возможно, т.к. граф планарный, а вершина 2 окружена красно-синим путём. Таким образом, не больше чем 2 dfs-ами мы можем решить проблему и покрасить v в один из 5 цветов. 
    
    Очевидно получается оценка на время работы в $\O(VE)$, но на практике алгоритм работает намного быстрее.
    
    
    
    
