- Задача Штейнера
-
Задача Штейнера состоит в поиске минимального дерева Штейнера — кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Свое название получила в честь Якоба Штейнера (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.