Рассматривается задача поиска оптимальной связывающей сети, обеспечивающей заданный набор связей между вершинами некоторого множества. Критерий оптимизации – суммарные затраты вершин сети, зависящие от входящих и исходящих из вершины потоков. Формулируется общая модель, подробно исследуется случай аддитивных функций затрат, для которых затраты вершины сети складываются из затрат, зависящих от степени вершины, и затрат, зависящих от протекающего через вершину потока. Вычисление нижней оценки затрат оптимальной сети сводится к вычислению нижних оценок отдельно для первого и второго слагаемого функции затрат. Оптимальные сети находятся для случая, когда затраты вершины зависят от ее степени. Для функции затрат, зависящей от протекающего потока предлагаются нижние оценки с использованием результатов спектральной теории графов.
