Дискретная математика - связующие деревья

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

пример

График в диапазонеОстовное дерево

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

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

пример

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

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

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

Алгоритм

Шаг 1 - Расположите все ребра данного графа $ G (V, E) $ в неубывающем порядке по весу ребра.

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

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

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

проблема

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

Проблема Крускала

Решение

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

№ края Пара вершин Крайний вес
E1 (а, б) 20
E2 (а, в) 9
E3 (а, г) 13
E4 (До нашей эры) 1
E5 (б, д) 4
E6 (б, е) 5
E7 (компакт диск) 2
E8 (д, е) 3
E9 (д, ж) 14

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

№ края Пара вершин Крайний вес
E4 (До нашей эры) 1
E7 (компакт диск) 2
E8 (д, е) 3
E5 (б, д) 4
E6 (б, е) 5
E2 (а, в) 9
E3 (а, г) 13
E9 (д, ж) 14
E1 (а, б) 20
Kruskal Adding Vertex EdgeKruskal Добавление вершинного края 1Kruskal Adding Vertex Edge 2

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

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

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

Алгоритм

  • Инициализируйте минимальное остовное дерево с одной вершиной, случайно выбранной из графа.

  • Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.

  • Выберите ребро, которое соединяет дерево с вершиной, которой еще нет в дереве, чтобы вес ребра был минимальным, а включение ребра не образовывало цикл.

  • Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.

проблема

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

чопорный

Решение

Здесь мы начинаем с вершины «а» и продолжаем.

prim 'Vertex добавлендобавлен prim 'Vertex c bПрим 'Вертекс д е добавленprim 'Vertex f добавлен

Это минимальное остовное дерево, и его общий вес составляет $ (1 + 2 + 3 + 5 + 9) = 20 $.