\Section{Минимальное остовное дерево (MST)}{7 декабря}{Владислав Кочергин}

\Subsection{Определение}

Дан связный неориентированный взвешенный граф. Остовное дерево (spanning tree) - ациклический связный подграф данного графа, содержащий все его вершины. Минимальное остовное дерево (minimum spanning tree, MST) - остовное дерево минимального веса.

\Subsection{Алгоритмы поиска}

\Subsubsection{Алгоритм Краскала}

Отсортируем все рёбра в порядке возрастания весов. Заведём для вершин СНМ. Изначально каждая вершина находится в своей компоненте. Перебираем рёбра: если оба конца ребра находятся в одной компоненте СНМ, то проигнорируем ребро, иначе объединим эти компоненты и добавим ребро в MST.

\begin{code}
dsu s(n);
vector <Edge> mst;
sort(edge.begin(), edge.end(), [](Edge x, Edge y){return x.weight < y.weight;});
for (auto e: edge) {
	if (s.get_parent(e.u) != s.get_parent(e.v)) {
		s.join(e.u, e.v);
		mst.push_back(e);
	}
}
\end{code}

\bfseries Время работы: \mdseries $\mathcal{O}(E\log E)$ - сортировка, $\mathcal{O}(E\log V)$ или $\mathcal{O}(E\alpha(V))$ - операции с СНМ. Отсюда $T = \mathcal{O}(E\log E) = \mathcal{O}(E\log V)$ (т. к. в графах без кратных рёбер $E \le V^2$).

\Subsubsection{Алгоритм Прима}

Изначально MST состоит из одной вершины. Для каждой вершины $v$ поддерживаем ребро минимального веса из построенной части MST в $v$. $d[v]$ и $par[v]$ - соответственно вес ребра и номер другого конца.

1. Добавляем минимальное ребро, выходящее из построенной части MST.

2. Обработаем новую вершину $u$, добавленную только что в MST: для всех ещё не добавленных вершин $v$, смежных с $u$, прорелаксируем $d[v]$ и $par[v]$ ребром $(u, v)$.

3. Возвращаемся в пункт 1, и так до тех пор, пока не добавим все вершины.

Алгоритм Прима очень похож на алгоритм Дейкстры, единственное отличие - релаксация.

\begin{code}
//Dijkstra
if (d[u] + weight(u, v) < d[v]) {d[v] = d[u] + weight(u, v); par[v] = u;}
//Prim
if (weight(u, v) < d[v]) {d[v] = weight(u, v); par[v] = u;}
\end{code}

\bfseries Время работы: \mdseries

Базовая реализация: $\mathcal{O}(V^2 + E)$ (оптимально для полных и почти полных графов).

Для разреженных графов выигрыш по времени даёт использование кучи для быстрого нахождения минимального ребра. Как и в алгоритме Дейкстры, потребуется $\mathcal{O}(V)$ операций ExtractMin и $\mathcal{O}(E)$ операций DecreaseKey.

Двоичная куча: $\mathcal{O}((V + E)\log V)$ (нет смысла использовать, т. к. алгоритм Краскала пишется быстрее и работает не хуже).

Фибоначчиевая куча: $\mathcal{O}(V\log V + E)$.

Radix Heap использовать нельзя, т. к. в отличие от алгоритма Дейкстры, извлекаемые из кучи значения не обязательно возрастают.

\Subsubsection{Алгоритм Борувки}

1. Для каждой вершины найдём минимальное инцидентное ей ребро. Добавим все такие рёбра в MST.

2. Сжимаем компоненты связности добавленных рёбер в одну вершину, избавляемся в сжатом графе от петель и кратных рёбер (мы это умеем делать за $\mathcal{O}(V + E))$.

3. Возвращаемся в пункт 1 и проделываем то же самое на сжатом графе, и так до тех пор, пока в графе больше одной вершины.

Минимизировать в пункте 1 нужно пару <вес ребра, id ребра>, чтобы никакие два ребра не были равными. Иначе могут возникнуть проблемы, к примеру, на полном графе из трёх вершин с одинаковыми весами всех рёбер.

~

\bfseries Время работы: \mdseries

1. $T = \mathcal{O}((V + E)\log V)$

На каждой итерации число вершин уменьшается хотя бы в два раза.

2. $T = \mathcal{O}(V^2)$

Пусть $E = V^2$. Тогда (т. к. мы избавляемся от кратных рёбер) $T = V^2 + (\frac{V}{2})^2 + (\frac{V}{4})^2 + \ldots =\mathcal{O}(V^2)$.

3. $T = \mathcal{O}((V + E)\log \frac{V^2}{E})$

Начиная с некоторого $k$, $(\frac{V}{2^k})^2 \le E$. Рассмотрим шаги алгоритма:

$V \rightarrow \frac{V}{2} \rightarrow \frac{V}{4} \rightarrow \ldots \rightarrow \frac{V}{2^k} \rightarrow \ldots$

До $k$-го шага будет выполнено $\mathcal{O}((V+ E)\log \frac{V^2}{E})$ действий (по утверждению 1).

Начиная с $k$-го шага, будет выполнено $\mathcal{O}(E)$ действий (по утверждению 2).

Отсюда $T = \mathcal{O}((V+ E)\log \frac{V^2}{E})$.

\Subsubsection{Доказательство корректности}

\bfseries Лемма о разрезе: \mdseries

Пусть у нас есть некоторый разрез графа: разбиение вершин на множества $S$ и $V \smallsetminus S$. Ребро проходит через разрез, если его концы лежат в разных множествах. Предположим, что у нас есть некоторое множество $F$ рёбер, не проходящих через разрез, и известно, что $F$ является подмножеством рёбер некоторого MST. Пусть $e$ - минимальное ребро, проходящее через разрез. Тогда множество $F \cup \{e\}$ тоже является подмножеством рёбер некоторого MST.

\bfseries Доказательство: \mdseries

Предположим, что есть MST, не содержащее $e$ и содержащее $F$. Значит, через разрез проходит некоторое ребро $e'$. Добавим к MST ребро $e$, получаем граф с циклом, проходящим через $e$ и $e'$. Удалим $e'$. Получится вновь дерево, причём (т. к. $weight(e) \le weight(e')$) вес полученного дерева не больше веса MST. Отсюда существует MST, содержащее $F \cup \{e\}$. Лемма доказана.

\bfseries Применение леммы о разрезе к доказательству алгоритмов: \mdseries

\bfseries Алгоритм Краскала: \mdseries множество $S$ - компонента СНМ, в которой находится один из концов добавляемого ребра.

\bfseries Алгортим Прима: \mdseries множество $S$ - вершины построенной части MST.

\bfseries Алгоритм Борувки: \mdseries здесь уже сложнее, т. к. мы одновременно добавляем несколько рёбер. Пусть у нас уже добавлены некоторые рёбра. Хотим добавить минимальное ребро, инцидентное некоторой вершине $v$ (назовём его $e$), если оно ещё не добавлено. В качестве множества $S$ рассмотрим множество вершин, из которых по добавленным рёбрам достижима вершина $v$.

Нужно доказать, что $e$ удоволетворяет лемме о разрезе: т. е. является минимальным ребром, проходящим через разрез. Рассмотрим произвольную вершину $u \neq v$ множества $S$ и произвольное ребро $f_0$, инцидентное $u$ и проходящее через разрез. Очевидно, что $f_0$ больше взятого из вершины $u$ ребра (обозначим $f_1$). Очевидно, каждое следующее ребро на пути от $u$ к $v$ по добавленным рёбрам ($f_2, f_3, \ldots$) будет меньше предыдущего (по этой же причине в алгоритме не может получиться цикл). По транзитивности получаем $f_0 < f_1 < f_2 < \ldots < e$, т. е. минимальное ребро, проходящее через разрез - ребро $e$, и по лемме о разрезе мы можем его взять.

\includegraphics[scale=1]{kochergin/boruvka_proof.png}
