Минимальный каркас. Схема алгоритма построения минимальных каркасов.
Задача отыскания минимального каркаса (кратчайшего остова) – классическая задача теории графов. Методы решения этой задачи послужили основой многих других важных результатов (исследование алгоритма Краскала привели к созданию теории "жадных" алгоритмов).
Пусть G(V,E) – граф. Остов (каркас) – остовной подграф, являющийся деревом. Несвязный граф не имеет остова, связный граф может иметь много остовов. Если задать длины ребер, то можно поставить задачу нахождения кратчайшего остова, или минимального каркаса.
Пример: Пример практической интерпретации задачи нахождения кратчайшего остова. Пусть задано множество аэродромов, и нужно определить минимальный по сумме расстояний набор авиарейсов, который позволил бы перелетать с любого аэродрома на любой другой аэродром. Решение задачи – кратчайший остов полного графа расстояний между аэродромами.
Граф расстояний между аэродромами и дерево кратчайших путей из вершины v1.
Кратчайшие остовы для графа G(V,E)
Рассмотрим схему алгоритма построения кратчайшего остова. Пусть Т – множество непересекающихся деревьев, являющихся подграфами графа G. Вначале Т состоит из отдельных вершин графа G, в конце Т содержит единственный элемент – кратчайший остов графа G.Схема алгоритма.
Вход: граф G(V,E), заданный матрицей длин ребер С.
Выход: кратчайший остов Т.
Т:=V
while в Т больше одного элемента do
взять любое поддерево из Т
найти к нему ближайшее
соединить эти деревья в Т