Тема 4 Нахождение оптимального остова графа

↑

Стр 1 из 2Следующая ⇒

Тема 4 Нахождение оптимального остова графа

Алгоритмы Прима и Крускала (Краскала)

Жадными (градиентными)называют алгоритмы, действующие по принципу "максимальный выигрыш на каждом шаге".Такая стратегия не всегда ведет к конечному успеху - иногда выгоднее сделать не наилучший, казалось бы, выбор на очередном шаге с тем, чтобы в итоге получить оптимальное решение. Но для некоторых задач применение жадных алгоритмов оказывается оправданным. Одной из самых известных задач такого рода является задача об оптимальном каркасе (остове).

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

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

При этом из экономических соображений требуется, чтобы количество затраченных рельсов было минимально.

(стоимость пути была минимальной)

рис 1. Граф и его остовные деревья

Остовным деревом (каркасом) для связного неориентированного графа  с n вершинами  неориентированное дерево, содержащее все n вершинам и (n-1) ребер графа. Таким образом, остовное дерево связывает все все вершины графа и из каждой вершины графа можно попасть в любую другую.

Если к остовному дереву добавить любую из оставшихся ребер, то возникнет ровно один цикл и он перестанет быть деревом.

В полном графе с n вершинами имеется nn-2 остовных деревьев

Под остовным деревом ориентированного графа понимают такое дерево, в котором, одна из вершин графа связана со всеми остальными

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии