Минимальный каркас. Схема алгоритма построения минимальных каркасов.


Задача отыскания минимального каркаса (кратчайшего остова) – классическая задача теории графов. Методы решения этой задачи послужили основой многих других важных результатов (исследование алгоритма Краскала привели к созданию теории "жадных" алгоритмов).

Пусть G(V,E) – граф. Остов (каркас) – остовной подграф, являющийся деревом. Несвязный граф не имеет остова, связный граф может иметь много остовов. Если задать длины ребер, то можно поставить задачу нахождения кратчайшего остова, или минимального каркаса.

Пример: Пример практической интерпретации задачи нахождения кратчайшего остова. Пусть задано множество аэродромов, и нужно определить минимальный по сумме расстояний набор авиарейсов, который позволил бы перелетать с любого аэродрома на любой другой аэродром. Решение задачи – кратчайший остов полного графа расстояний между аэродромами.

Граф расстояний между аэродромами и дерево кратчайших путей из вершины v1.

Кратчайшие остовы для графа G(V,E)

Рассмотрим схему алгоритма построения кратчайшего остова. Пусть Т – множество непересекающихся деревьев, являющихся подграфами графа G. Вначале Т состоит из отдельных вершин графа G, в конце Т содержит единственный элемент – кратчайший остов графа G.Схема алгоритма.

Вход: граф G(V,E), заданный матрицей длин ребер С.

Выход: кратчайший остов Т.

Т:=V

while в Т больше одного элемента do

взять любое поддерево из Т

найти к нему ближайшее

соединить эти деревья в Т

End while

Тема 17. Циклы и коциклы. Эйлеровы циклы. Гамильтоновы циклы. Теорема Дирака. Раскраска графов. Хроматическое число. Планарные графы. Укладка графов. Алгоритм раскрашивания.



Дата добавления: 2021-07-22; просмотров: 382;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.