Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Комбинаторные алгоритмы: множества, графы, коды

ЗАДАНИЕ 6 Построение минимального остова

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

Формулировка задачи

Пусть задан связный взвешенный граф G = (V,E), V - {vb ..., v„}, п > 1, Е= {е{, ..., ет}, т > 1, на множестве ребер которого определена весовая функция. Эта функция приписывает каждому ребру е - {vj, у,} е Е графа вещественное число w(e) = Wy- вес ребра е. Требуется из конечного (возможно, очень большого) числа остовных деревьев заданного графа найти одно, у которого сумма весов входящих в него ребер минимальна. Это дерево называют минимальным остовом, а саму задачу - задачей о минимальном остове. Решение данной задачи для связного графа всегда существует и, возможно, не единственное.

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

Для решения задачи о минимальном остове имеются несколько эффективных алгоритмов. Рассмотрим два из них: алгоритм Дж. Крас- кала (1956 г.), алгоритм Р. Прима (1957 г.).

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы