Дискретная математика - Spanning Trees

Остовное дерево связного неориентированного графа $ G $ - это дерево, которое минимально включает все вершины $ G $. Граф может иметь много остовных деревьев.

пример

Минимальное связующее дерево

Остовное дерево с присвоенным весом, меньшим или равным весу каждого возможного остовного дерева взвешенного, связного и неориентированного графа $ G $, называется минимальным остовным деревом (MST). Вес остовного дерева - это сумма всех весов, присвоенных каждому краю остовного дерева.

пример

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

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

Алгоритм

Step 1 - Расположите все ребра данного графа $ G (V, E) $ в порядке возрастания в соответствии с их весом.

Step 2 - Выберите наименьшее взвешенное ребро на графике и проверьте, образует ли оно цикл с уже сформированным остовным деревом.

Step 3 - Если цикла нет, включите это ребро в остовное дерево, иначе отбросьте его.

Step 4 - Повторяйте шаги 2 и 3 до тех пор, пока в остовном дереве не останется $ (V-1) $ ребер.

Problem

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

Solution

Из приведенного выше графика мы построим следующую таблицу -

Номер края	Пара вершин	Вес края
E1	(а, б)	20
E2	(а, в)	9
E3	(а, г)	13
E4	(до н.э)	1
E5	(б, д)	4
E6	(б, е)	5
E7	(CD)	2
E8	(г, д)	3
E9	(г, ж)	14

Теперь переставим таблицу в порядке возрастания относительно веса ребра -

Номер края	Пара вершин	Вес края
E4	(до н.э)	1
E7	(CD)	2
E8	(г, д)	3
E5	(б, д)	4
E6	(б, е)	5
E2	(а, в)	9
E3	(а, г)	13
E9	(г, ж)	14
E1	(а, б)	20

Поскольку у нас есть все 5 ребер на последнем рисунке, мы останавливаем алгоритм, и это минимальное остовное дерево, а его общий вес равен $ (1 + 2 + 3 + 5 + 9) = 20 $.

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

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

Алгоритм

Инициализируйте минимальное остовное дерево одной вершиной, случайно выбранной из графа.
Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.
Выберите ребро, которое соединяет дерево с вершиной, еще не входящей в дерево, так, чтобы вес ребра был минимальным и включение ребра не образовывало цикла.
Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.

Problem

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