Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

3. Алгоритм Крускала:
1) Выбрать в графе G ребро e минимального веса, не принадлежащее множеству E и такое, что его добавление в E не создает цикл в дереве T.
2) Добавить это ребро во множество ребер E.
3) Продолжить, пока имеются ребра, обладающие указанными свойствами.
Пример. Для данного взвешенного графа найти минимальное корневое остовное дерево, используя алгоритм Крускала. Определить высоту построенного дерева.



Алгоритм Крускала. Выбираем ребро с минимальным весом. Это ребро, ( , ) с весом, равным 4.
Пусть вершина будет корнем дерева. Далее выбираем ребра, инцидентные вершинам , и имеющие минимальный вес.
Это ребро ( , ) с весом 5. Затем к вершине присоединяем ребро ( , ) с весом 7.
Далее, добавляем ребро ( , ) с весом 7 и ребро ( , ) с весом 6.
Минимальный вес построенного дерева равен: _min(T)=4+5+7+7+6=29.



4. Алгоритм Прима
Всегда имеется дерево, к которому ребра добавляют до тех пор, пока не получится остовное дерево.
Используя алгоритм Прима, сначала выбираем вершину v₀ графа G, а затем выбираем ребро с наименьшим весом e₁ = {v_{0 ,}v₁}, инцидентное к вершине v₀ и формируем дерево Т₁.
Следующим выбираем ребро с наименьшим весом е₂ такое, что одна вершина ребра принадлежит дереву T₁, а вторая — нет, и добавляем его в дерево, после чего получаем дерево T₂ с двумя ребрами.
Сформировав дерево Т_k формируем дерево Т_k+1, выбирая ребро с минимальным весом e_k+1 такое, что одна его вершина принадлежит дереву Т_k, а другая — нет, и добавляем это ребро в дерево.
Продолжаем процесс до тех пор, пока дерево не будет содержать все вершины графа G.
1) Выбрать вершину v₀ графа G и ребро с наименьшим весом e₁, для которого v₀ – одна из вершин, и сформировать дерево T₁.
2) Для заданного дерева T_k с ребрами e₁, e₂, e₃, …, e_k, если имеется вершина, не принадлежащая T_k, выбрать ребро с наименьшим весом, смежное с ребром дерева T_k и имеющее вершину вне дерева T_k. Добавить в дерево T_k, формируя дерево T_k+1.
3) Продолжить, пока имеются вершины графа G, не принадлежащие дереву.

Построение минимального остовного дерева можно проводить двумя способами:

1) остов графа строится непосредственно на самом графе, выделяя ребра утолщенной линией, которые входят в остовное дерево;
2) строится отдельно корневое дерево, которое будет минимальным остовным деревом. Второй случай используется, если требуется определить высоту построенного дерева.
Пример. Рассмотрим граф.

Начав с вершины а, первым выбираем ребро {а, е}, поскольку оно имеет минимальный вес.
Т. о. дерево T1 состоит из ребра {а, е}.
Теперь выбираем ребро {e,d}, так как это ребро с минимальным весом из тех, что имеют только одну вершину в дереве T1.
Получаем дерево Т2.
Д алее выбираем ребро {d, b}, поскольку это ребро с минимальным весом из тех, что имеют только одну вершину в Т2. Получаем Т3.
Теперь, так как имеется два ребра с одинаковым весом и одной вершиной в Т3, имеем выбор.
П редположим, выбрано ребро {d,c}, поэтому дерево Т4 имеет следующий вид.
Следующим выбираем ребро {е, f}. Это ребро имеет минимальный вес из тех, что имеют только одну вершину в дереве Т4; отсюда Т5
Наконец, выбираем ребро {f,g}. Поскольку это ребро минимального веса из тех, что имеют одну вершину в Т4, а вершина g — последняя из оставшихся вершин, имеем дерево Т6, которое является искомым остовным деревом.

ВЕС МОД 2+2+1+4=9