Математическая модель вычисления покрывающего дерева сети

Для произвольной заданной сети строится минимальное покрывающее дерево, учитывающее ин тенсивность обмена данными для каждой пары узлов исходной сети. Тем самым решается про блема выбора оптимального маршрута для обмена данными между каждой парой вершин за данного графа сети; решается задача выбора минимальных по стоимости провайдеров, обеспе чивающего связь между узлами сети. Для этого сеть передачи данных представляется в виде нео риентированного графа, для которого строится покрывающее дерево, обеспечивающее мини мальные затраты на весь проходящий по сети трафик. Количество переданной информации в единицу времени между каждой парой узлов сети задаётся матрицей интенсивностей обмена данными. Граф сети задаётся матрицей смежности. Стоимость прохождения единицы информа ции по каждому из рёбер графа сети представляет собой матрицу весов. Для решения постав ленной задачи разработан алгоритм и соответствующий программный продукт, строящий по крывающее дерево, которое позволяет передавать заранее заданные объёмы информации меж ду всеми пользователями сети, при этом суммарная стоимость трафика будет минимальной. По мимо построенного покрывающего дерева алгоритм даёт также возможную минимальную стои мость передачи заданного объёма данных между всеми узлами сети. Алгоритм позволяет пост роить минимальное покрывающее дерево (покрывающее дерево минимального веса), однако для такой цели можно использовать уже имеющиеся алгоритмы, такие как, например, алгоритм Прима или Краскала. Однако с помощью указанных алгоритмов возможно построить лишь ми нимальное по весу покрывающее дерево. В отличие от них предложенный в работе алгоритм строит дерево с учётом нагрузок на рёбра и вершины исходного графа сети и, вычисляя общую стоимость всего проходящего по сети трафика, минимизирует её.