1
правка
Изменения
Новая страница: «В планарных графах возможно построить [[Остовные деревья: ...»
В [[Укладка графа на плоскости | планарных графах]] возможно построить [[Остовные деревья: определения, лемма о безопасном ребре | остовное дерево]] за <tex>O(n)</tex>, что заметно быстрее, чем алгоритмы, используемые для поиска остовного дерева в общем случае.
Рассмотрим более общую задачу {{---}} построение остовного дерева минимального (максимального) веса в планарном графе, которая также может быть решена за <tex>O(n)</tex>.
== Остовное дерево минимального (максимального) веса в планарном графе ==
Пусть есть граф <tex>G = (V, E)</tex>, где <tex>V</tex> – множество вершин, <tex>E</tex> – множество рёбер. Для произвольной вершины <tex>v</tex> графа <tex>G</tex> обозначим как <tex>\xi _G(v)</tex> множество рёбер графа <tex>G</tex>, инцидентных <tex>v</tex>. Для любого подмножества рёбер <tex>E'\subseteq E</tex> граф <tex>(V, E')</tex> будем называть остовным лесом графа <tex>G</tex>, когда граф ацикличен. Остовный лес является остовным деревом, когда он связен. Вес ребра <tex>e</tex> обозначим как <tex>w(e)</tex>. Вес подмножества рёбер <tex>F</tex> обозначим как <tex>w(F)</tex>, он является суммой весов рёбер, входящих в <tex>F</tex>. Максимальный остовный лес <tex>F</tex> называется остовным лесом минимального (максимального) веса, когда вес <tex>w(F)</tex> минимален (максимален).
Для решения этой задачи, помимо исходного планарного графа <tex>G</tex>, потребуется его [[Двойственный граф планарного графа | двойственный граф]] <tex>G^* = (V^*, E)</tex>, который можно легко построить геометрически по укладке <tex>G</tex> на плоскости<ref>E.L. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976)</ref>.
Если данный граф связен, задача эквивалентна обычной задаче поиска минимального (максимального) по весу остовного дерева. Известно, что подмножество рёбер <tex>T\subseteq E</tex> – максимальный остовный лес <tex>G</tex> тогда и только тогда, когда <tex>E\setminus T</tex> – максимальный остовный лес <tex>G^*</tex>. Таким образом, задача поиска минимального по весу остовного леса графа <tex>G</tex> – по сути то же самое, что задача поиска максимального по весу остовного леса <tex>G^*</tex>.
== Формальное описание алгоритма ==
Итак, имеется планарный граф <tex>G = (V, E)</tex>, его двойственный граф <tex>G^* = (V^*, E)</tex> и веса рёбер <tex>w</tex>, на выходе нужно получить остовный лес минимального веса <tex>T</tex> графа <tex>G</tex> и остовный лес максимального веса <tex>T^*</tex> графа <tex>G^*</tex>.
'''Шаг 0''': Запись графов. <tex>T := \varnothing</tex>; <tex>T^* := \varnothing</tex>.
'''Шаг 1''': Если графы <tex>G</tex> и <tex>G^*</tex> пусты одновременно, выведем <tex>T</tex> и <tex>T^*</tex>.
'''Шаг 2''': Выберем вершину <tex>v</tex> в графе <tex>G</tex> или <tex>G^*</tex>:
Если <tex>v</tex> – изолированная вершина, удалим её и вернёмся к шагу 1;
Если <tex>v</tex> – вершина <tex>G</tex> и в <tex>\xi _G(v)</tex> есть петля, перейдём к шагу 3;
Если v – вершина <tex>G</tex> и в <tex>\xi _G(v)</tex> нет петель, перейдём к шагу 4;
Если <tex>v</tex> – вершина <tex>G^*</tex> и в <tex>\xi _{G^*}(v)</tex> есть петля, перейдём к шагу 5;
Если <tex>v</tex> – вершина <tex>G^*</tex> и в <tex>\xi _{G^*}(v)</tex> нет петель, перейдём к шагу 6;
'''Шаг 3''': Пусть <tex>f</tex> – петля <tex>G</tex>, инцидентная <tex>v</tex>.
<tex>G := G\setminus f</tex>; <tex>G* := G*\setminus f</tex>; <tex>T* := T*\cup \{f\}</tex>.
Вернёмся к шагу 1.
'''Шаг 4''': Найдём ребро <tex>e</tex>, достигающее минимального веса <tex>w(e)</tex> среди рёбер из <tex>\xi _G(v)</tex>.
<tex>G := G/e</tex>; <tex>G^* := G^*\setminus e</tex>; <tex>T := T\cup \{e\}</tex>. (<tex>/</tex> обозначает операцию стягивания ребра)
Вернёмся к шагу 1.
'''Шаг 5''': Пусть <tex>f</tex> – петля <tex>G^*</tex>, инцидентная <tex>v</tex>.
<tex>G := G\setminus f</tex>; <tex>G^* := G^*\setminus f</tex>; <tex>T := T\cup\{f\}</tex>.
Вернёмся к шагу 1.
'''Шаг 6''': Найдём ребро <tex>e</tex>, достигающее максимального веса <tex>w(e)</tex> среди рёбер из <tex>\xi _{G^*}(v)</tex>.
<tex>G\setminus e</tex>; <tex>G^*/e</tex>; <tex>T^*:= T^*\cup\{e\}</tex>.
Вернёмся к шагу 1.
== Корректность и время работы ==
Легко убедиться в том, что на протяжении всех итераций приведённого алгоритма <tex>G^*</tex> является двойственным графом графа <tex>G</tex>, из чего следует корректность этого алгоритма.
На каждой итерации алгоритма происходит удаление ребра или вершины, из этого следует, что количество итераций алгоритма не превосходит <tex>|V| + |V^*| + |E| = O(n)</tex>.
Далее опишем, как добиться того, чтобы каждая итерация осуществлялась за <tex>O(1)</tex>. Для каждой вершины <tex>v</tex> графа <tex>G</tex> обозначим <tex>d_G(v)</tex> степень этой вершины (петли считаются дважды). Из формулы Эйлера следует, что в <tex>G</tex> или <tex>G^*</tex>, где <tex>G</tex> – планарный граф, а <tex>G^*</tex> - двойственный к нему, существует вершина, степень которой меньше четырёх.
На шаге 2 будем выбирать именно такую вершину. Сначала покажем, что каждая интеграция алгоритма выполняется за <tex>O(n)</tex>, предполагая, что нужная вершина на шаге 2 всегда выбирается за константное время, реализацию обсудим позже.
Итак, оба графа хранятся в виде списков смежности. Тогда, очевидно, шаги 1 и 2 выполняются за <tex>O(1)</tex>. Поскольку при такой реализации рёбра удаляются за константное время, шаги 3 и 5 выполняются за <tex>O(1)</tex>. Рассмотрим шаг 4. Поскольку степень вершины не больше четырёх, поиск ребра минимального веса займёт константное время. Стягивание ребра <tex>e = (u, v)</tex> происходит за <tex>O(\min\{d_G(v), d_G(u)\}) = O(3) = O(1)</tex>. Для шага 6 рассуждения аналогичны.
Вернёмся к выбору вершины на шаге 2. Для этого создадим хэш-таблицу, содержащую все вершины степени меньше четырёх. Это позволяет выбрать нужную вершину за <tex>O(1)</tex>, но хэш-таблицу также нужно обновлять. При удалении ребра из графа степени вершин, инцидентных ему, уменьшаются на 1 (или на 2 в случае петли), степени же остальных вершин не меняются. Теперь рассмотрим случай стягивания ребра. Удаляются концы стягиваемого ребра, а получающаяся в результате этого вершина должна быть добавлена в хэш-таблицу, если её степень меньше четырёх. Таким образом, на каждой итерации алгоритма из хэш-таблицы может быть удалено максимум две вершины, а добавлено - максимум четыре, значит, хэш-таблица обновляется за константное время.
Создание хэш-таблицы должно происходить вместе с шагом 0 и осуществляется за <tex>O(|V| + |V^*| + |E|)</tex>.
== Примечания ==
<references/>
== Источники информации ==
[http://www.sciencedirect.com/science/article/pii/0166218X9400095U Sciencedirect {{---}} The minimum spanning tree problem on a planar graph]
Рассмотрим более общую задачу {{---}} построение остовного дерева минимального (максимального) веса в планарном графе, которая также может быть решена за <tex>O(n)</tex>.
== Остовное дерево минимального (максимального) веса в планарном графе ==
Пусть есть граф <tex>G = (V, E)</tex>, где <tex>V</tex> – множество вершин, <tex>E</tex> – множество рёбер. Для произвольной вершины <tex>v</tex> графа <tex>G</tex> обозначим как <tex>\xi _G(v)</tex> множество рёбер графа <tex>G</tex>, инцидентных <tex>v</tex>. Для любого подмножества рёбер <tex>E'\subseteq E</tex> граф <tex>(V, E')</tex> будем называть остовным лесом графа <tex>G</tex>, когда граф ацикличен. Остовный лес является остовным деревом, когда он связен. Вес ребра <tex>e</tex> обозначим как <tex>w(e)</tex>. Вес подмножества рёбер <tex>F</tex> обозначим как <tex>w(F)</tex>, он является суммой весов рёбер, входящих в <tex>F</tex>. Максимальный остовный лес <tex>F</tex> называется остовным лесом минимального (максимального) веса, когда вес <tex>w(F)</tex> минимален (максимален).
Для решения этой задачи, помимо исходного планарного графа <tex>G</tex>, потребуется его [[Двойственный граф планарного графа | двойственный граф]] <tex>G^* = (V^*, E)</tex>, который можно легко построить геометрически по укладке <tex>G</tex> на плоскости<ref>E.L. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976)</ref>.
Если данный граф связен, задача эквивалентна обычной задаче поиска минимального (максимального) по весу остовного дерева. Известно, что подмножество рёбер <tex>T\subseteq E</tex> – максимальный остовный лес <tex>G</tex> тогда и только тогда, когда <tex>E\setminus T</tex> – максимальный остовный лес <tex>G^*</tex>. Таким образом, задача поиска минимального по весу остовного леса графа <tex>G</tex> – по сути то же самое, что задача поиска максимального по весу остовного леса <tex>G^*</tex>.
== Формальное описание алгоритма ==
Итак, имеется планарный граф <tex>G = (V, E)</tex>, его двойственный граф <tex>G^* = (V^*, E)</tex> и веса рёбер <tex>w</tex>, на выходе нужно получить остовный лес минимального веса <tex>T</tex> графа <tex>G</tex> и остовный лес максимального веса <tex>T^*</tex> графа <tex>G^*</tex>.
'''Шаг 0''': Запись графов. <tex>T := \varnothing</tex>; <tex>T^* := \varnothing</tex>.
'''Шаг 1''': Если графы <tex>G</tex> и <tex>G^*</tex> пусты одновременно, выведем <tex>T</tex> и <tex>T^*</tex>.
'''Шаг 2''': Выберем вершину <tex>v</tex> в графе <tex>G</tex> или <tex>G^*</tex>:
Если <tex>v</tex> – изолированная вершина, удалим её и вернёмся к шагу 1;
Если <tex>v</tex> – вершина <tex>G</tex> и в <tex>\xi _G(v)</tex> есть петля, перейдём к шагу 3;
Если v – вершина <tex>G</tex> и в <tex>\xi _G(v)</tex> нет петель, перейдём к шагу 4;
Если <tex>v</tex> – вершина <tex>G^*</tex> и в <tex>\xi _{G^*}(v)</tex> есть петля, перейдём к шагу 5;
Если <tex>v</tex> – вершина <tex>G^*</tex> и в <tex>\xi _{G^*}(v)</tex> нет петель, перейдём к шагу 6;
'''Шаг 3''': Пусть <tex>f</tex> – петля <tex>G</tex>, инцидентная <tex>v</tex>.
<tex>G := G\setminus f</tex>; <tex>G* := G*\setminus f</tex>; <tex>T* := T*\cup \{f\}</tex>.
Вернёмся к шагу 1.
'''Шаг 4''': Найдём ребро <tex>e</tex>, достигающее минимального веса <tex>w(e)</tex> среди рёбер из <tex>\xi _G(v)</tex>.
<tex>G := G/e</tex>; <tex>G^* := G^*\setminus e</tex>; <tex>T := T\cup \{e\}</tex>. (<tex>/</tex> обозначает операцию стягивания ребра)
Вернёмся к шагу 1.
'''Шаг 5''': Пусть <tex>f</tex> – петля <tex>G^*</tex>, инцидентная <tex>v</tex>.
<tex>G := G\setminus f</tex>; <tex>G^* := G^*\setminus f</tex>; <tex>T := T\cup\{f\}</tex>.
Вернёмся к шагу 1.
'''Шаг 6''': Найдём ребро <tex>e</tex>, достигающее максимального веса <tex>w(e)</tex> среди рёбер из <tex>\xi _{G^*}(v)</tex>.
<tex>G\setminus e</tex>; <tex>G^*/e</tex>; <tex>T^*:= T^*\cup\{e\}</tex>.
Вернёмся к шагу 1.
== Корректность и время работы ==
Легко убедиться в том, что на протяжении всех итераций приведённого алгоритма <tex>G^*</tex> является двойственным графом графа <tex>G</tex>, из чего следует корректность этого алгоритма.
На каждой итерации алгоритма происходит удаление ребра или вершины, из этого следует, что количество итераций алгоритма не превосходит <tex>|V| + |V^*| + |E| = O(n)</tex>.
Далее опишем, как добиться того, чтобы каждая итерация осуществлялась за <tex>O(1)</tex>. Для каждой вершины <tex>v</tex> графа <tex>G</tex> обозначим <tex>d_G(v)</tex> степень этой вершины (петли считаются дважды). Из формулы Эйлера следует, что в <tex>G</tex> или <tex>G^*</tex>, где <tex>G</tex> – планарный граф, а <tex>G^*</tex> - двойственный к нему, существует вершина, степень которой меньше четырёх.
На шаге 2 будем выбирать именно такую вершину. Сначала покажем, что каждая интеграция алгоритма выполняется за <tex>O(n)</tex>, предполагая, что нужная вершина на шаге 2 всегда выбирается за константное время, реализацию обсудим позже.
Итак, оба графа хранятся в виде списков смежности. Тогда, очевидно, шаги 1 и 2 выполняются за <tex>O(1)</tex>. Поскольку при такой реализации рёбра удаляются за константное время, шаги 3 и 5 выполняются за <tex>O(1)</tex>. Рассмотрим шаг 4. Поскольку степень вершины не больше четырёх, поиск ребра минимального веса займёт константное время. Стягивание ребра <tex>e = (u, v)</tex> происходит за <tex>O(\min\{d_G(v), d_G(u)\}) = O(3) = O(1)</tex>. Для шага 6 рассуждения аналогичны.
Вернёмся к выбору вершины на шаге 2. Для этого создадим хэш-таблицу, содержащую все вершины степени меньше четырёх. Это позволяет выбрать нужную вершину за <tex>O(1)</tex>, но хэш-таблицу также нужно обновлять. При удалении ребра из графа степени вершин, инцидентных ему, уменьшаются на 1 (или на 2 в случае петли), степени же остальных вершин не меняются. Теперь рассмотрим случай стягивания ребра. Удаляются концы стягиваемого ребра, а получающаяся в результате этого вершина должна быть добавлена в хэш-таблицу, если её степень меньше четырёх. Таким образом, на каждой итерации алгоритма из хэш-таблицы может быть удалено максимум две вершины, а добавлено - максимум четыре, значит, хэш-таблица обновляется за константное время.
Создание хэш-таблицы должно происходить вместе с шагом 0 и осуществляется за <tex>O(|V| + |V^*| + |E|)</tex>.
== Примечания ==
<references/>
== Источники информации ==
[http://www.sciencedirect.com/science/article/pii/0166218X9400095U Sciencedirect {{---}} The minimum spanning tree problem on a planar graph]
