8. Экстремальные задачи теории графов: минимальное остовное дерево, алгоритмы Прима и Краскала.

Определение. Связный граф без циклов называется деревом. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Если задача состоит в том, чтобы найти экстремум (максимум или минимум) определенной функции от этих значений, то её принято называть экстремальной задачей.

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

Определение.Минимальное остовное дерево - остовное дерево минимально возможной длины.

Алгоритм Прима. В графе G=(V, E) рассмотрим U - некоторое подмножество V, такое что U и V-U не пусты. Пусть (u, v) - ребро наименьшей стоимости, одна вершина которого - u принадлежит U, а другая - v принадлежит V-U. Тогда существует некоторое минимальное остовное дерево, содержащее ребро (u, v). Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V-U.

• Положить в U любую вершину (изначально U – пусто).

• До тех пор, пока ( V-U не пусто ): выбираем ребро (u, v) наименьшей стоимости, u из U, v из V-U; добавляем v к U (и убираем из V-U)

Алгоритм Краскала.Идея алгоритма Краскала состоит в том, что искомое остовное дерево «вырастает» из леса, отдельные деревья которого постепенно объединяются и на последнем шаге алгоритма объединяются в одну компоненту связности – остовное дерево. Схема алгоритма такова:

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

• Из оставшихся ребер исходного графа убрать кратчайшее, которое после добавления его к полученному лесу не образует там циклов. Этот этап повторяется до тех пор, пока лес не превратится в остовное дерево исходного графа.