Минимальное остовное дерево (MST)

заключается в построении остова минимального веса.

г.)
На n вершинах, пронумерованных числами от 1 до n существует ровно nn-2 различных деревьев (т.е. число остовных деревьев в полном графе) .

А́ртур Кэ́ли (Arthur Cayley) 1821-1895, английский математик в честь которого названа серия теорем, которые называются теоремами Кэли.
Код Прюфера – способ однозначного кодирования n-вершинного помеченного дерева упорядоченной последовательностью из (n-2) номеров его вершин.

Хайнц Прюфер, нем. Ernst Paul Heinz Prüfer, 1996 -1934, Германия

ФПМИ БГУ

В 1918 году Прюфер использовал код для доказательства формулы Кэли о числе остовных деревьев.

(лист - вершина степени 1)
Добавить в код Прюфера номер вершины, смежной с v.
Удалить из дерева вершину v и инцидентное ей ребро.

Код Прюфера:

4

5

3

6

2

1

Код Прюфера –
способ однозначного кодирования n-вершинного помеченного дерева упорядоченной последовательностью из (n-2) номеров его вершин.

ФПМИ БГУ

1

4

5

5

{1, 4, 5, 5}

2, 3, 4, 5}
Просматриваем код Прюфера слева направо.
Пусть v – вершина в коде.
Пусть w - вершина из множества V с минимальным номером, которой нет в коде.
Добавляем ребро {v,w} в дерево.
Удаляем v из кода.
Удаляем w из списка вершин V.
Оставшиеся в V две вершины соединяем ребром и добавляем в дерево.

ФПМИ БГУ

4

5

3

6

2

1

1

4

5

5

Код Прюфера:

v:

1

2

3

4

5

w:

1

4

5

5

6

Восстановленное по коду Прюфера дерево

n-2

Теорема Кэли о числе деревьев
На n вершинах, пронумерованных числами от 1 до n существует ровно nn-2 различных деревьев
(число различных остовных деревьев в полном графе) .

– информатик
Награждён премией Тьюринга

Роберт Клей Прим
Robert Clay Prim
1921 -
США
Научная сфера – математик, информатик (фото 1971 г.)
Доктор философии по математике

1930 год

Войтек Ярник
Vojtěch Jarník
1897 - 1970
Чехословакия
Научная сфера – математическая физика, теория чисел, математический анализ.
Академик

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

Алгоритм Прима (или Ярника, или DJP)

статистик, программист и психометрик Доктор наук

дерево графа G – пустое.
Проcматриваем все рёбра графа G в порядке неубывания их веса:
пусть {v,u} – текущее ребро;
если ребро {v,u} не образует цикла с ранее выбранными в MST рёбрами, то добавляем его к MST;
если ребро {v,u} образует цикл с ранее выбранными рёбрами, то игнорирум его.
4. MST – минимальное остовное дерево графа G.

w{2,4}=1

w{2,3}=1

w{1,2}=2

w{3,4}=1

w{3,5}=3

w{1,3}=2

w{1,5}=3

w{4,5}=4

MST

w(MST)=7

2

1

3

1

добавить в массив все рёбра,
затем отсортировать их, используя, например, сортировку слиянием или быструю сортировку Хоара, которые работают за время O(m log m);
бинарную кучу min_heap
создать кучу из m рёбер – O(m);
пока куча не станет пустой,
удалять из кучи ребро с самым маленьким весом;
т.к. удаление минимального элемента из кучи выполняется за время O(log m), то все удаления будут выполнены за время O(m log m).

ФПМИ БГУ

использовать структуру данных система непересекающихся множеств (DSU).
Одному множеству будут принадлежать вершины, которые в формируемом MST уже соединены некоторой цепью. Изначально имеем n одноэлементных множеств (время создания – O(n)).

ФПМИ БГУ

Если v и u принадлежат разным множествам, то добавляем ребро к MST, а множества, которым принадлежали вершины v и u объединяем в одно множество (поиск и объединение можно выполнить за время O(log n)).

Если вершины v и u принадлежат одному множеству (проверка можно выполнить за время O(log n)), то они в MST соединены цепью и добавление ребра {v,u} приведёт к циклу;

Просматриваем все рёбра графа, для каждого ребра {v,u} проверяем:

попытке добавить очередное ребро к построенной части MST; использование DSU с эвристикой объединения по размеру

O(m log m)

+

ФПМИ БГУ

Dijkstra
1930 – 2002
Нидерланды
Научная сфера – информатик
Награждён премией Тьюринга

Роберт Клей Прим
Robert Clay Prim
1921 -
США
Научная сфера – математик, информатик (фото 1971 г.)
Доктор философии по математике

1930 год

Войтек Ярник
Vojtěch Jarník
1897 - 1970
Чехословакия
Научная сфера – математическая физика, теория чисел, математический анализ.
Академик

в минимальное остовное дерево MST.
Рассмотрим все рёбра графа G у которых ровно один конец которых лежит в MST и выберем из них то, вес которого наименьший. Предположим, что выбрано ребро {v,u}.
Добавляем вершину u вместе с ребром {v,u} в MST.
Если все вершины графа G перенесены в остов, то алгоритм завершает свою работу, а MST – минимальное остовное дерево графа G.
Если не все вершины графа G перенесены в остов, то возвращаемся к шагу 3 алгоритма.

4

1

MST

2

3

5

2

1

3

1

2

3

5

2

1

3

4

1

3

1

2

3

2

1

3

3

4

1

4

2

3

5

3

3

4

4

1

2

3

5

MST

1

5

элементов массива, содержащего кратчайшее ребро, соединяющего вершину с построенной частью MST;

O(n2+m)

1. Реализация DJP
на структуре данных массив

в
остове?

2

ФПМИ БГУ

с меткой – вес наименьшего ребра, которое соединяет вершину v с построенной частью MST;
для каждой вершины поддерживаем её индекс в массиве, на котором реализована бинарная куча;
пока куча не станет пустой, удаляем из кучи вершину w с минимальной меткой, добавляем соответствующее ребро в остов и при необходимости уменьшаем в куче метки вершин, которые смежны с w и ещё не добавлены в остов;

2. Реализация DJP
на структуре данных бинарная куча + модификация ключа

min_heap

с меткой – вес наименьшего ребра, которое соединяет вершину v с построенной частью MST):
O(n)
пересчёты меток вершин (уменьшение ключа):
O(m log n) – БИНАРНАЯ КУЧА
O(m) – КУЧА Фибоначчи (усреднённо)
!!! необходимо поддерживать для каждой вершины её индекс в массиве, на котором реализована бинарная куча;
удаление вершин из кучи:
O(n log n)

Реализация DJP
на структуре данных куча + модификация ключа

O(m log n) + O(n log n) – бинарная куча
O(m) + O(n log n) –куча Фибоначчи (усреднённо)

что w
не находится в MST и только
тогда добавлять

4

2

ФПМИ БГУ

3. Реализация DJP
(приоритетная очередь без модификации ключа)

2

решить оптимально жадным алгоритмом?

«жадным» алгоритмом, а некоторые нет (получается некоторое приближенное решение).

корректно решает задачу о лесе максимального веса.

о минимальном остовном дереве, но в то же время может быть сформулирована как комбинаторная задача оптимизации для системы подмножеств.

Задача о минимальном остовном дереве также решалась «жадным» алгоритмом.
Однако эта задача не может быть сформулирована в терминах системы подмножеств, так как если обозначить через J семейство остовных деревьев некоторого графа, то это семейство не будет являться замкнутым относительно включения (любое подмножество ребер остовного дерева уже не будет являться остовным деревом исходного графа).