Статья в сборнике "Математические вопросы кибернетики" №11, Москва, 2002
Авторы:Иванов А.О., Тужилин А.А.
Отношение Штейнера. Современное состояние
Аннотация:
Отношение Штейнера характеризует величину относительной ошибки приближения кратчайшего дерева, соединяющего конечное подмножество точек метрического пространства, минимальным остовным деревом в наихудшем возможном случае. Эта характеристика метрических пространств активно изучается с 60х годов прошлого века. В работе изложены современные (на 2002 год) результаты на эту тему, в том числе, обсуждаются пробелы в доказательстве гипотезы Джилберта—Поллака об отношении Штейнера евклидовой плоскости, представленной Венном и Ду.
Ключевые слова:
проблема Штейнера, отношение Штейнера, кратчайшая сеть, минимальное остовное дерево
