Поиск дерева минимального веса

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

В планарных графах возможно построить остовное дерево за [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] на плоскости [1] .

Если данный граф связен, задача эквивалентна обычной задаче поиска минимального (максимального) по весу остовного дерева. Известно, что подмножество рёбер [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 _(v)[/math] есть петля, перейдём к шагу 5;

Если [math]v[/math] – вершина [math]G^*[/math] и в [math]\xi _(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 \[/math] .

Шаг 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 \[/math] . ( [math]/[/math] обозначает операцию стягивания ребра)

Шаг 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\[/math] .

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

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

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

Легко убедиться в том, что на протяжении всех итераций приведённого алгоритма [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\) = O(3) = O(1)[/math] . Для шага 6 рассуждения аналогичны.

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

Примечания

1. ↑ E.L. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976)

Источник

Алгоритм Краскала, Прима для нахождения минимального остовного дерева

Алгоритмы нахождения MST применимы в различных областях, начиная от кластеризации данных до построения компьютерных, транспортных сетей.
Я надеюсь, что вы после прочтения данной статьи, примерно понимали, как работают жадные алгоритмы нахождения MST.

Формальная постановка задачи

Имеется следующий неориентированный взвешенный граф. Назовем остовным деревом подграф, содержащий все вершины исходного графа, который является деревом. И задача состоит в том, чтобы найти такое остовное дерево, сумма рёбер которого минимальна.

Неформальная постановка задачи

Представьте исходный граф без рёбер, теперь вам нужно как-то соединить все вершины между собой, чтобы можно было бы попасть из любой вершины в другую, не имея при этом циклов в получившемся графе с минимально возможной суммой весов включенных рёбер.

Алгоритм Краскала

Механизм, по которому работает данный алгоритм, очень прост. На входе имеется пустой подграф, который и будем достраивать до потенциального минимального остовного дерева. Будем рассматривать только связные графы, в другом случае при применении алгоритма Краскала мы будем получать не минимальное остовное дерево, а просто остовной лес.

• Вначале мы производим сортировку рёбер по неубыванию по их весам.
• Добавляем i-ое ребро в наш подграф только в том случае, если данное ребро соединяет две разные компоненты связности, одним из которых является наш подграф. То есть, на каждом шаге добавляется минимальное по весу ребро, один конец которого содержится в нашем подграфе, а другой — еще нет.
• Алгоритм завершит свою работу после того, как множество вершин нашего подграфа совпадет с множеством вершин исходного графа.

Данный алгоритм называется жадным из-за того, что мы на каждом шаге пытаемся найти оптимальный вариант, который приведет к оптимальному решению в целом.

Разбор конкретного примера по шагам

Из представленного сверху графа, выпишем все его ребра в отсортированном порядке:

1) D B; w = 2
2) D C; w = 6
3) A B; w = 7
4) A C; w = 8
5) C E; w = 9
6) D F; w = 9
7) F E; w = 10
8) B C; w = 11
9) D E; w = 11

И начнем по списку добавлять эти ребра в наш остов:

При добавлении в наше остовное дерево ребра A C, как вы можете заметить, образовывается цикл, поэтому мы просто пропускаем данное ребро.

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

Проводим проверку с помощью встроенного алгоритма для нахождения MST на graphonline, и видим, что подграфы идентичны.
И да, из-за того, что при равенстве весов рёбер мы можем выбрать любое из них, конечные подграфы, являющиеся минимальными остовными деревьями, могут различаться с точностью до некоторых рёбер.

Суммарный вес искомого MST равен 33.

Реализация

Реализовать представленный алгоритм проще всего с помощью СНМ(система непересекающихся отрезков).

Вначале, как мы уже раннее говорили, необходимо отсортировать ребра по неубыванию по их весам. Далее с помощью вызовов функции make_set() мы каждую вершину можем поместить в свое собственное дерево, то есть, создаем некоторое множество подграфов. Дальше итерируемся по всем ребрам в отсортированном порядке и смотрим, принадлежат ли инцидентные вершины текущего ребра разным подграфам с помощью функции find_set() или нет, если оба конца лежат в разных компонентах, то объединяем два разных подграфа в один с помощью функции union_sets().

В итоге асимптотическая сложность данного алгоритма сводится к:

, где:
sort() —
make_set()-
find_set —
union_sets —

vector parent, rank; void make_set(int v) < parent[v] = v; rank[v] = 0; >int find_set(int v) < if (v == parent[v]) return v; return parent[v] = find_set(parent[v]); >void union_sets(int a, int b) < a = find_set(a); b = find_set(b); if (a != b) < if (rank[a] < rank[b]) swap(a, b); parent[b] = a; if (rank[a] == rank[b]) rank[a]++; >> struct Edge < int u, v, weight; bool operator<(Edge const& other) < return weight < other.weight; >>; int n; vector edges; int cost = 0; vector result; parent.resize(n); rank.resize(n); for (int i = 0; i < n; i++) make_set(i); sort(edges.begin(), edges.end()); for (Edge e : edges) < if (find_set(e.u) != find_set(e.v)) < cost += e.weight; result.push_back(e); union_sets(e.u, e.v); >>

Алгоритм Прима

Суть самого алгоритма Прима тоже сводится к жадному перебору рёбер, но уже из определенного множества. На входе так же имеется пустой подграф, который и будем достраивать до потенциального минимального остовного дерева.

• Изначально наш подграф состоит из одной любой вершины исходного графа.
• Затем из рёбер инцидентных этой вершине, выбирается такое минимальное ребро, которое связала бы две абсолютно разные компоненты связности, одной из которых и является наш подграф. То есть, как только у нас появляется возможность добавить новую вершину в наш подграф, мы тут же включаем ее по минимальмально возможному весу.
• Продолжаем выполнять предыдущий шаг до тех пор, пока не найдем искомое MST.

Разбор конкретного примера

Выбираем чисто случайно вершину E, далее рассмотрим все ребра исходящие из нее, включаем в наше остовное дерево ребро C E; w = 9, так как данное ребро имеет минимальный вес из всех рёбер инцидентных множеству вершин нашего подграфа. Имеем следующее:

Теперь выборка производится из рёбер:
D C; w = 6
A C; w = 8
F E; w = 10
B C; w = 11
D E; w = 11

То есть, в данный момент, мы знаем только о двух вершинах, соответственно, знаем о всех ребрах, исходящих из них. Про связи между другими вершинами, которые не включены в наш подграф, мы ничего не знаем, поэтому они на этом шаге не рассматриваются.

Добавляем в наш подграф ребро D C и по аналогии добаляем ребро D B . Получаем следующее:

Давайте добьем наш подграф до минимального остовного дерева. Вы, наверное, уже догадались о том, по каким ребрам мы будем связывать наши оставшиеся вершины:
A и F.

Проводим последние штрихи и получили тот же самый подграф в качестве минимального остовного дерева. Но как мы раннее говорили, сам подграф ничего не решает, главное тут — множество рёбер, которые включены в наше остовное дерево.

Суммарный вес искомого MST равен 33.

Источник