Лес Штейнера: различия между версиями

Построение дерева Штейнера представляет собой фундаментальную задачу проектирования сетей. Говоря неформально, цель заключается в установлении соединений между парами вершин данной сети по минимальной стоимости. Это обобщение широко известной задачи построения дерева Штейнера. К примеру, предположим, что телекоммуникационная компания получает от своих клиентов запросы на коммуникации. Каждому клиенту требуется соединение между двумя вершинами в данной сети. Задача компании заключается в построении сетевой инфраструктуры с минимальной стоимостью, удовлетворяющей всем запросам на коммуникации.