Учебники

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

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

пример

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

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

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

пример

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

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

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

Алгоритм

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

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

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

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

проблема

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

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

Решение

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

Край Пара вершин Крайний вес
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

Kruskal Adding Vertex EdgeKruskal Добавление вершинного края 1Kruskal Adding Vertex Edge 2

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

проблема

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

чопорный

Решение

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

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

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