Задача - штейнер
Cтраница 2
 |
Пять контактов цепи.| Кратчайшее связывающее дерево Ь ( Т 7 5 6 5 23.| Дерево Штейнера, 2 точки Штейнера, ЦТ 19. [16] |
Она формулируется следующим образом. Для заданных п точек плоскости построить соединяющее их кратчайшее связывающее дерево с п п точками ( вершинами), общая суммарная длина соединений которого минимальна. Построенное таким образом дерево называется деревом Штейнера, дополнительные вершины - точками Штейнера. Задача Штейнера, как известно, является NP-полной. Для п 3 известно точное решение задачи. Для п 4 существует ряд эффективных алгоритмов. [17]
Страницы: 1 2