Основные определения. Сеть состоит из множества узлов, связанных дугами (или ребрами)

Сеть состоит из множества узлов, связанных дугами (или ребрами). Таким образом, сеть описывается парой множеств , где – множество узлов, а – множество ребер. Например, сеть, показанная на рис. 1, описывается следующим образом.

Рис. 1 – Пример сети

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

Ребро называется направленным, или ориентированным (и в этом случае ребро будем называть дугой), если в одном направлении возможен только положительный поток, а в противоположном — только нулевой. В ориентированной сети все ребра ориентированны.

Путем называется последовательность различных ребер, соединяющих два узла, независимо от направления потока в каждом ребре. Путь формирует цикл, если начальный и конечный узлы совпадают. Например, на рис. 1 ребра (2, 3), (3, 4) и (4, 2) составляют цикл. Ориентированный цикл — это цикл, в котором все дуги ориентированы в определенном направлении.

Связная сеть — такая сеть, у которой любые два узла связаны по крайней мере одним путем. На рис. 1 показан именно такой тип сети. Деревом называется связная сеть, содержащая подмножество узлов исходной сети и не имеющая циклов. Остовное дерево — это дерево, содержащее все узлы сети. На рис. 2 показаны дерево и остовное дерево для сети из рис. 1.

Рис. 2 – Дерево и остовное дерево для сети на рис. 1

38. Алгоритм построения минимального остовного дерева.

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

Опишем процедуру выполнения этого алгоритма.

Обозначим через множество узлов сети и введем новые обозначения:

– множество узлов сети, соединенных алгоритмом после выполнения -й итерации этого алгоритма,

— множество узлов сети, не соединенных с узлами множества после выполнения -й итерации этого алгоритма.

Шаг 0. Полагаем и .

Шаг 1. Выбираем любой узел из множества и определяем , тогда . Полагаем .

Основной шаг . В множестве , выбираем узел , который соединен самой короткой дугой с каким-либо узлом из множества . Узел присоединяется к множеству и удаляется из множества ,. Таким образом, , .

Если множество пусто, то выполнение алгоритма заканчивается. В противном случае полагаем и повторяем последний шаг.