Ebook: Экстремальные задачи на графах и алгоритмы их решения

Задача Штейнера: Есть несколько точек на плоскости, которые нужно связать системой дорог наименьшей суммарной длины таким образом, чтобы по этим дорогам можно было из каждой точки добраться в любую другую. Число точек конечно. Интерес к задаче Штейнера вызван тем, что эта задача, а также различные ее обобщения служат математической моделью многих задач прикладного характера. В книге рассматривается задача Штейнера о нахождении вершины метрического графа, минимизирующей сумму взвешенных расстояний до остальных вершин графа. Приводятся алгоритмы решения соответствующих задач. Хотя для задачи Штейнера были найдены экспоненциальные алгоритмы (например, алгоритм Мелзака), ни одного полиномиального алгоритма найти для неё не удалось. И шансы на то, что эффективный алгоритм будет когда-нибудь найден, очень малы. Книга рассчитана на специалистов по прикладной математике и может быть полезной для студентов и аспирантов той же специальности.