Остовное дерево в планарном графе

В планарных графах возможно построить остовное дерево за [math]O(n)[/math], что заметно быстрее, чем алгоритмы, используемые для поиска остовного дерева в общем случае. Рассмотрим более общую задачу — построение остовного дерева минимального (максимального) веса в планарном графе, которая также может быть решена за [math]O(n)[/math].

Остовное дерево минимального (максимального) веса в планарном графе

Пусть есть граф [math]G = (V, E)[/math], где [math]V[/math] – множество вершин, [math]E[/math] – множество рёбер. Для произвольной вершины [math]v[/math] графа [math]G[/math] обозначим как [math]\xi _G(v)[/math] множество рёбер графа [math]G[/math], инцидентных [math]v[/math]. Для любого подмножества рёбер [math]E'\subseteq E[/math] граф [math](V, E')[/math] будем называть остовным лесом графа [math]G[/math], когда граф ацикличен. Остовный лес является остовным деревом, когда он связен. Вес ребра [math]e[/math] обозначим как [math]w(e)[/math]. Вес подмножества рёбер [math]F[/math] обозначим как [math]w(F)[/math], он является суммой весов рёбер, входящих в [math]F[/math]. Максимальный остовный лес [math]F[/math] называется остовным лесом минимального (максимального) веса, когда вес [math]w(F)[/math] минимален (максимален). Для решения этой задачи, помимо исходного планарного графа [math]G[/math], потребуется его двойственный граф [math]G^* = (V^*, E)[/math], который можно легко построить геометрически по укладке [math]G[/math] на плоскости.

Если данный граф связен, задача эквивалентна обычной задаче поиска минимального (максимального) по весу остовного дерева. Известно, что подмножество рёбер [math]T\subseteq E[/math] – максимальный остовный лес [math]G[/math] тогда и только тогда, когда [math]E\setminus T[/math] – максимальный остовный лес [math]G^*[/math]. Таким образом, задача поиска минимального по весу остовного леса графа [math]G[/math] – по сути то же самое, что задача поиска максимального по весу остовного леса [math]G^*[/math].

Формальное описание алгоритма

Итак, имеется планарный граф [math]G = (V, E)[/math], его двойственный граф [math]G^* = (V^*, E)[/math] и веса рёбер [math]w[/math], на выходе нужно получить остовный лес минимального веса [math]T[/math] графа [math]G[/math] и остовный лес максимального веса [math]T^*[/math] графа [math]G^*[/math].

Шаг 0: Запись графов. [math]T := \varnothing[/math]; [math]T^* := \varnothing[/math].

Шаг 1: Если графы [math]G[/math] и [math]G^*[/math] пусты одновременно, выведем [math]T[/math] и [math]T^*[/math].

Шаг 2: Выберем вершину [math]v[/math] в графе [math]G[/math] или [math]G^*[/math]:

Если [math]v[/math] – изолированная вершина, удалим её и вернёмся к шагу 1;

Если [math]v[/math] – вершина [math]G[/math] и в [math]\xi _G(v)[/math] есть петля, перейдём к шагу 3;

Если v – вершина [math]G[/math] и в [math]\xi _G(v)[/math] нет петель, перейдём к шагу 4;

Если [math]v[/math] – вершина [math]G^*[/math] и в [math]\xi _{G^*}(v)[/math] есть петля, перейдём к шагу 5;

Если [math]v[/math] – вершина [math]G^*[/math] и в [math]\xi _{G^*}(v)[/math] нет петель, перейдём к шагу 6;

Шаг 3: Пусть [math]f[/math] – петля [math]G[/math], инцидентная [math]v[/math].

[math]G := G\setminus f[/math]; [math]G* := G*\setminus f[/math]; [math]T* := T*\cup \{f\}[/math].

Вернёмся к шагу 1.

Шаг 4: Найдём ребро [math]e[/math], достигающее минимального веса [math]w(e)[/math] среди рёбер из [math]\xi _G(v)[/math].

[math]G := G/e[/math]; [math]G^* := G^*\setminus e[/math]; [math]T := T\cup \{e\}[/math]. ([math]/[/math] обозначает операцию стягивания ребра)

Вернёмся к шагу 1.

Шаг 5: Пусть [math]f[/math] – петля [math]G^*[/math], инцидентная [math]v[/math].

[math]G := G\setminus f[/math]; [math]G^* := G^*\setminus f[/math]; [math]T := T\cup\{f\}[/math].

Вернёмся к шагу 1.

Шаг 6: Найдём ребро [math]e[/math], достигающее максимального веса [math]w(e)[/math] среди рёбер из [math]\xi _{G^*}(v)[/math].

[math]G\setminus e[/math]; [math]G^*/e[/math]; [math]T^*:= T^*\cup\{e\}[/math].

Вернёмся к шагу 1.

Корректность и время работы

Легко убедиться в том, что на протяжении всех итераций приведённого алгоритма [math]G^*[/math] является двойственным графом графа [math]G[/math], из чего следует корректность этого алгоритма.

На каждой итерации алгоритма происходит удаление ребра или вершины, из этого следует, что количество итераций алгоритма не превосходит [math]|V| + |V^*| + |E| = O(n)[/math].

Далее опишем, как добиться того, чтобы каждая итерация осуществлялась за [math]O(1)[/math]. Для каждой вершины [math]v[/math] графа [math]G[/math] обозначим [math]d_G(v)[/math] степень этой вершины (петли считаются дважды). Из формулы Эйлера следует, что в [math]G[/math] или [math]G^*[/math], где [math]G[/math] – планарный граф, а [math]G^*[/math] - двойственный к нему, существует вершина, степень которой меньше четырёх.

На шаге 2 будем выбирать именно такую вершину. Сначала покажем, что каждая интеграция алгоритма выполняется за [math]O(n)[/math], предполагая, что нужная вершина на шаге 2 всегда выбирается за константное время, реализацию обсудим позже.

Итак, оба графа хранятся в виде списков смежности. Тогда, очевидно, шаги 1 и 2 выполняются за [math]O(1)[/math]. Поскольку при такой реализации рёбра удаляются за константное время, шаги 3 и 5 выполняются за [math]O(1)[/math]. Рассмотрим шаг 4. Поскольку степень вершины не больше четырёх, поиск ребра минимального веса займёт константное время. Стягивание ребра [math]e = (u, v)[/math] происходит за [math]O(\min\{d_G(v), d_G(u)\}) = O(3) = O(1)[/math]. Для шага 6 рассуждения аналогичны.

Вернёмся к выбору вершины на шаге 2. Для этого создадим хэш-таблицу, содержащую все вершины степени меньше четырёх. Это позволяет выбрать нужную вершину за [math]O(1)[/math], но хэш-таблицу также нужно обновлять. При удалении ребра из графа степени вершин, инцидентных ему, уменьшаются на 1 (или на 2 в случае петли), степени же остальных вершин не меняются. Теперь рассмотрим случай стягивания ребра. Удаляются концы стягиваемого ребра, а получающаяся в результате этого вершина должна быть добавлена в хэш-таблицу, если её степень меньше четырёх. Таким образом, на каждой итерации алгоритма из хэш-таблицы может быть удалено максимум две вершины, а добавлено - максимум четыре, значит, хэш-таблица обновляется за константное время. Создание хэш-таблицы должно происходить вместе с шагом 0 и осуществляется за [math]O(|V| + |V^*| + |E|)[/math].

Источники информации

Sciencedirect — The minimum spanning tree problem on a planar graph