- Задача Штейнера
-
Задача Штейнера состоит в поиске минимального дерева Штейнера — кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (1796—1863).
Содержание
История
История этой задачи восходит ко временам Пьера Ферма (1601—1665), который, после изложения своего метода исследования минимумов и максимумов, написал[1]:
Qui hanc methodum non probaverit, ei proponitur: Datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minima quantitas.
Тот же, кто этот метод не оценил, пусть он решит [следующую задачу]: для заданных трех точек найти такую четвертую, что если из нее провести три отрезка в данные точки, то сумма этих трех отрезков даст наименьшую величину.
Эта задача была частично решена Э. Торричелли [2] [3] (1608—1647) и Б. Кавальери [4] (1598—1647), учениками Б. Кастелли (1577—1644), затем найденная ими конструкция была модифицирована Т. Симпсоном [5] (1710—1761) и окончательно уточнена Ф. Хейненом [6] и Ж. Бертраном (1822-1900). В результате, был получено геометрическое построение точки S, ныне называемой точкой Ферма (иногда точкой Торричелли), которая для трёх заданных точек A, B и C даёт минимально возможную сумму длин отрезков AS, BS, CS.
В 1934 году В. Ярник и O. Кесслер [7] сформулировали обобщение задачи Ферма, заменив три точки на произвольное конечное число. А именно, их задача состоит в описании связных плоских графов наименьшей длины, проходящих через данное конечное множество точек плоскости.
В 1941 году вышла монография Р. Куранта и Г. Роббинса «Что такое математика?»[8], в которой авторы написали следующее:
Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни ,
,
системой дорог таким образом, чтобы их общая протяженность была минимальной.
Было бы естественно обобщить эту проблему на случайзаданных точек
следующим образом: требуется найти в плоскости такую точку
, чтобы сумма расстояний
(где
обозначает расстояние
) обращалась в минимум. … Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки
. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной.[8]
Эта книга завоевала заслуженную популярность, в результате чего и задачу Ферма, и задачу Ярника—Кесслера сейчас принято называть проблемой Штейнера.
Основные определения
Приведем несколько современных формулировок проблемы Штейнера. В качестве объемлющего пространства вместо евклидовой плоскости рассмотрим произвольное метрическое пространство.
Минимальные деревья Штейнера
Пусть
— метрическое пространство и
— граф на X, то есть,
. Для каждого такого графа определены длины его рёбер
как расстояния
между их вершинами, а также длина
самого графа
как сумма длин всех его рёбер.
Если
— конечное подмножество
, а
— связный граф на
, для которого
, то
называется графом, соединяющим
. При этом граф
, соединяющий
, минимально возможной длины
является деревом, которое называется минимальным деревом Штейнера на
. Именно изучению таких деревьев и посвящена одна из версий проблемы Штейнера.
Отметим, что минимальные деревья Штейнера существуют не всегда. Тем не менее, точная нижняя грань величин
по всем связным графам, соединяющим
, всегда существует, называется длиной минимального дерева Штейнера на
и обозначается через
.
- Примеры
Если
— стандартная евклидова плоскость, т.е. расстояние
порождается нормой
, то получаем классическую проблему Штейнера, сформулированную Ярником и Кесслером (см. выше).
Если
— манхэттенская плоскость[убрать шаблон], т.е. расстояние
порождается нормой
, то получает прямоугольную проблему Штейнера, одним из приложений которой является проектирование разводок микросхем. Более современные разводки моделируются метрикой, порожденной λ-нормой (единичный круг — правильный 2λ-угольник; в этих терминах манхеттенская норма является 2-нормой).
Если в качестве
берётся сфера (приблизительно моделирующую поверхность Земли), а за
— длина кратчайшей из двух дуг большой окружности, высекаемой из сферы
плоскостью, проходящей через
,
и центр сферы, то получается разновидность транспортной задачи: требуется соединить заданный набор пунктов (городов, предприятий, абонентов и т.д.) кратчайшей коммуникационной сетью (дорог, трубопроводов, телефонных линий и т.д.), минимизировав затраты на строительство (предполагается, что затраты пропорциональны длине сети).
Если в качестве
берётся множество всех слов над некоторым алфавитом, а в качестве
— расстояние Левенштейна, то получается вариант проблемы Штейнера, который широко используется в биоинформатике, в частности, для построения эволюционного дерева.
Если в качестве
берётся множество вершин
связного графа
, а в качестве
— функция расстояния, порожденная некоторой весовой функцией
, то получается проблема Штейнера в графах.
Минимальные параметрические сети
Пусть
— некоторое подмножество множества
вершин графа
, содержащее все вершины степени 1 и 2. Пара
называется графом с границей
. Если
— связный граф, и
— некоторое отображение в метрическое пространство
, то каждое отображение
, ограничение которого на
совпадает с
, называется сетью типа
с границей
в метрическом пространстве
. Ограничение сети
на вершины и ребра графа
называются соответственно вершинами и ребрами этой сети. Длиной ребра
сети
называется величина
, а длиной
сети
— сумма длин всех ее ребер.
Обозначим через
множество всех сетей типа
с границей
. Сеть из
, имеющая наименьшую возможную длину, называется минимальной параметрической сетью типа
с границей
.
Отметим, что, как и в случае минимальных деревьев Штейнера, минимальная параметрическая сеть существует не всегда. Тем не менее, точная нижняя грань величин
по всем сетям из
, всегда существует, называется длиной минимальной параметрической сети и обозначается через
.
Если
— конечное подмножество
, а
отображает
на все
, т.е.
, то говорят, что сеть
соединяет
. Легко видеть, что
по всем
, для которых
. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.
Одномерные минимальные заполнения в смысле Громова
Это естественное обобщение проблемы Штейнера было предложено А. О. Ивановым и А. А. Тужилиным.[9] Пусть
— произвольное конечное множество и
— некоторый связный граф. Будем говорить, что
соединяет
, если
. Пусть теперь
— конечное псевдометрическое пространство (где, в отличие от метрического пространства, расстояния между разными точками могут быть равны нулю),
— связный граф, соединяющий
, и
— некоторое отображение в неотрицательные вещественные числа, называемое обычно весовой функцией и порождающее взвешенный граф
. Функция
задает на
псевдометрику
, а именно, расстоянием между вершинами графа
назовем наименьший из весов путей, соединяющих эти вершины. Если для любых точек
и
из
выполняется
, то взвешенный граф
называется заполнением пространства
, а граф
— типом этого заполнения. Число
, равное
по всем заполнениям
пространства
, назовем весом минимального заполнения, а заполнение
, для которого
, — минимальным заполнением. Основная задача — научиться вычислять
и описывать минимальные заполнения.
Примечания
- ↑ Fermat P. de (1643), Ed. H.Tannery, ed., «"Oeuvres"», vol. 1, Paris 1891, Supplement: Paris 1922, сс. 153, <http://www.archive.org/details/oeuvresdefermat901ferm>
- ↑ G. Loria, G. Vassura (1919), «Opere de Evangelista Torriceli», vol. 1, сс. 79-97
- ↑ J. Krarup, S. Vajda (1997). «On Torricelli's geometrical solution to a problem of Fermat». IMA J. Math. Appl. Bus. Indust. 8 (3): 215-224. DOI:10.1093/imaman/8.3.215.
- ↑ B. Cavalieri (1647), «Excercitationes Geometricae»
- ↑ T. Simpson (1750), «"The Doctrine and Application of Fluxions"»
- ↑ F. Heinen (1834), "«Über Systeme von Kräften»", Gymnasium zu Cleve (Essen)
- ↑ V. Jarník, O. Kössler (1934), "«O minimálních grafech obsahujících n daných bodu»", Ĉas, Pêstování Mat. (Essen) Т. 63: 223-235, <http://www.pdf.dml.cz/bitstream/handle/10338.dmlcz/122548/CasPestMatFys_063-1934-8_1.pdf>
- ↑ 1 2 R. Courant, H. Robbins (1941), «What Is Mathematics?», Oxford University Press
- ↑ A. O. Ivanov, A. A. Tuzhilin. «One-dimensional Gromov minimal filling».
Литература
- А. О. Иванов, А. А. Тужилин Теория экстремальных сетей. — Москва–Ижевск: Институт компьютерных исследований, 2003. — ISBN 5-93972-292-X
- А. О. Иванов, А. А. Тужилин Задача Штейнера на плоскости или плоские минимальные сети // Матем. сб.. — 1991. — Т. 182. — № 12. — С. 1813–1844.
- Weisstein, Eric W. Steiner Tree (англ.) на сайте Wolfram MathWorld.
Категории:- Комбинаторная геометрия
- Теория графов
- Вариационное исчисление
- Вычислительная геометрия
- NP-полные задачи
Wikimedia Foundation. 2010.