3.1. Односвязные кратчайшие сети

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

Процесс построения такой сети заключается в следующем. На первом шаге соединяют ребром два узла, находящихся на наименьшем расстоянии друг от друга l_{ij min}. На каждом последующем шаге добавляют ребро, соответствующее наименьшему расстоянию из оставшихся, но так, чтобы не получилось цикла. Если имеется несколько ребер одинаковой длины, то может быть взято любое из них. Процесс продолжается до тех пор, пока все узлы не окажутся соединенными в одно дерево, как это показано, например на рис. 4.

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

В некоторых случаях общая длинна ребер односвязной сети может быть уменьшена, если кроме заданных N пунктов ввести дополнительные узлы. Для треугольника рис. 5а с кратчайшим деревом рис. 5б наименьшая общая длинна ребер L_min будет в случае , когда вновь вводимый узел располагается в точке Ш, называемой точкой Штейнера, в которой все ребра сходятся под углами 120 рис. 5в.

Наибольший эффект получается в случае равностороннего треугольника (рис. 5г), для которого L_min = , где  - длина ребра, и выигрыш составляет  0,866 длины ребер кратчайшего дерева, для которого L = 2a.

Когда конфигурация сети отличается от равностороннего треугольника, введение дополнительного узла (точки Штейнера) дает меньший эффект, т. е. 1  L_min /L   0,866. При трех пунктах точка Штейнера будет в месте пересечения окружностей, описанных вокруг равносторонних треугольников, построенных на двух сторонах исходного треугольника (рис. 5д).

При переходе от кратчайшего дерева (рис. 5б) к сети с точкой Штейнера (рис. 5в) сокращается общая длина ребер, однако из трех путей уменьшается длина только одного ₁₃, в то время как двух других (₁₂ и ₂₃) увеличивается. А это означает, что общая длина каналов  может возрасти. Если число каналов во всех связях одинаково (и₁₂ = и₂₃ = и₁₃), то общая длина каналов сократится пропорционально сокращению длины ребер, а если и₁₂ > и₁₃ и (или) и₂₃ > и₁₃, то общая длина каналов может увеличиться.

Рис. 4 Пример сети с заданным расстоянием (а) и построение дл неё кратчайшего дерева (б) (в скобках указан порядок введения ребер)

Рис. 5 Примеры нахождения точек Штейнера в сети

Для сети с числом пунктов (основных узлов), большим трех, в настоящее время нет однозначного алгоритма получения сети с минимальной длиной ребер при введении новых узлов. При N основных узлах число точек Штейнера может быть не более N-2, но введены они могут быть, разными способами. Можно лишь рекомендовать исходить из кратчайшего дерева. При четырех основных узлах две точки Штейнера находятся на пересечениях окружностей, описанных вокруг равносторонних треугольников, построенных на противоположных ребрах исходного дерева, с линией, соединяющей третьи вершины этих треугольников, как показано на рис. 5е. Для четырех узлов, расположенных в углах квадрата, сеть с точками Штейнера будет иметь длину ребер в 3/(1-1/ )  1,1 раза меньше, чем кратчайшее дерево, причем средняя длина пути уменьшается в 1,16 раза.