Задача Штейнера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Минимальное дерево Штейнера для точек A, B и C, где S — точка Ферма треугольника ABC.

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

« Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни A, B, C системой дорог таким образом, чтобы их общая протяженность была минимальной.
Было бы естественно обобщить эту проблему на случай n заданных точек A_1, A_2, \ldots, A_n следующим образом: требуется найти в плоскости такую точку P, чтобы сумма расстояний a_1 + a_2 + \ldots + a_n (где a_i обозначает расстояние PA_i) обращалась в минимум. … Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки P. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной.[8]
»

Эта книга завоевала заслуженную популярность, в результате чего и задачу Ферма, и задачу Ярника—Кесслера сейчас принято называть проблемой Штейнера.

Алгоритм решения[править | править вики-текст]

Эффективного (сложность выражается функцией, ограниченной сверху некоторым полиномом от параметра задачи, в данном случае число вершин графа) алгоритма, дающего точное решение проблемы Штейнера, не существует. Приближенное решение дает эффективный алгоритм Краскала[9].

Основные определения[править | править вики-текст]

Приведем несколько современных формулировок проблемы Штейнера. В качестве объемлющего пространства вместо евклидовой плоскости рассмотрим произвольное метрическое пространство.

Минимальные деревья Штейнера[править | править вики-текст]

Пусть (X,\rho) — метрическое пространство и G=(V,E) — граф на X, то есть, V\subset X. Для каждого такого графа определены длины его рёбер e=\{u,v\}\in E как расстояния \rho(u,v) между их вершинами, а также длина \rho(G) самого графа G как сумма длин всех его рёбер.

Если M — конечное подмножество X, а G=(V,E) — связный граф на X, для которого M\subset V, то G называется графом, соединяющим M. При этом граф G, соединяющий M, минимально возможной длины \rho(G) является деревом, которое называется минимальным деревом Штейнера на M. Именно изучению таких деревьев и посвящена одна из версий проблемы Штейнера.

Отметим, что минимальные деревья Штейнера существуют не всегда. Тем не менее, точная нижняя грань величин \rho(G) по всем связным графам, соединяющим M, всегда существует, называется длиной минимального дерева Штейнера на M и обозначается через \operatorname{smt}(M).

Примеры

Если (X,\rho) — стандартная евклидова плоскость, то есть расстояние \rho порождается нормой \|(x,y)\| = \sqrt{x^2+y^2}, то получаем классическую проблему Штейнера, сформулированную Ярником и Кесслером (см. выше).

Если (X,\rho) — манхэттенская плоскость, то есть расстояние \rho порождается нормой \|(x,y)\| = |x|+|y|, то получает прямоугольную проблему Штейнера, одним из приложений которой является проектирование разводок микросхем. Более современные разводки моделируются метрикой, порожденной λ-нормой (единичный круг — правильный 2λ-угольник; в этих терминах манхеттенская норма является 2-нормой).

Если в качестве X берётся сфера (приблизительно моделирующую поверхность Земли), а за \rho(a,b) — длина кратчайшей из двух дуг большой окружности, высекаемой из сферы X плоскостью, проходящей через a, b и центр сферы, то получается разновидность транспортной задачи: требуется соединить заданный набор пунктов (городов, предприятий, абонентов и т. д.) кратчайшей коммуникационной сетью (дорог, трубопроводов, телефонных линий и т. д.), минимизировав затраты на строительство (предполагается, что затраты пропорциональны длине сети).

Если в качестве X берётся множество всех слов над некоторым алфавитом, а в качестве \rho(a,b) — расстояние Левенштейна, то получается вариант проблемы Штейнера, который широко используется в биоинформатике, в частности, для построения эволюционного дерева.

Если в качестве X берётся множество вершин V связного графа G=(V,E), а в качестве \rho — функция расстояния, порожденная некоторой весовой функцией \omega\colon E\to\Bbb R, то получается проблема Штейнера в графах.

Минимальные параметрические сети[править | править вики-текст]

Пусть \partial G — некоторое подмножество множества V вершин графа G=(V,E), содержащее все вершины степени 1 и 2. Пара (G,\partial G) называется графом с границей \partial G. Если G — связный граф, и \varphi\colon\partial G\to X — некоторое отображение в метрическое пространство (X,\rho), то каждое отображение \Gamma\colon G\to X, ограничение которого на \partial G совпадает с \varphi, называется сетью типа (G,\partial G) с границей \varphi в метрическом пространстве (X,\rho). Ограничение сети \Gamma на вершины и ребра графа G называются соответственно вершинами и ребрами этой сети. Длиной ребра \Gamma\colon\{u,v\}\to X сети \Gamma называется величина \rho\bigl(\Gamma(u),\Gamma(v)\bigr), а длиной \rho(\Gamma) сети \Gamma — сумма длин всех её ребер.

Обозначим через [G,\varphi] множество всех сетей типа (G,\partial G) с границей \varphi. Сеть из [G,\varphi], имеющая наименьшую возможную длину, называется минимальной параметрической сетью типа (G,\partial G) с границей \varphi.

Отметим, что, как и в случае минимальных деревьев Штейнера, минимальная параметрическая сеть существует не всегда. Тем не менее, точная нижняя грань величин \rho(G) по всем сетям из [G,\varphi], всегда существует, называется длиной минимальной параметрической сети и обозначается через \operatorname{mpn}[G,\varphi].

Если M — конечное подмножество X, а \varphi отображает \partial G на все M, то есть \operatorname{im}(\varphi)=M, то говорят, что сеть \Gamma\in[G,\varphi] соединяет M. Легко видеть, что \operatorname{smt}(M)=\inf\operatorname{mpn}[G,\varphi] по всем [G,\varphi], для которых \operatorname{im}(\varphi)=M. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.

Одномерные минимальные заполнения в смысле Громова[править | править вики-текст]

Это естественное обобщение проблемы Штейнера было предложено А. О. Ивановым и А. А. Тужилиным.[10] Пусть M — произвольное конечное множество и G=(V,E) — некоторый связный граф. Будем говорить, что G соединяет M, если M\subset V. Пусть теперь {\mathcal M}=(M,\rho) — конечное псевдометрическое пространство (где, в отличие от метрического пространства, расстояния между разными точками могут быть равны нулю), G=(V,E) — связный граф, соединяющий M, и \omega\colon E\to{\Bbb R}_+ — некоторое отображение в неотрицательные вещественные числа, называемое обычно весовой функцией и порождающее взвешенный граф \mathcal G=(G,\omega). Функция \omega задает на V псевдометрику d_\omega, а именно, расстоянием между вершинами графа \mathcal G назовем наименьший из весов путей, соединяющих эти вершины. Если для любых точек p и q из M выполняется \rho(p,q)\le d_\omega(p,q), то взвешенный граф \mathcal G называется заполнением пространства \mathcal M, а граф G — типом этого заполнения. Число \operatorname{mf}(\mathcal M), равное \inf\omega(\mathcal G) по всем заполнениям \mathcal G пространства \mathcal M, назовем весом минимального заполнения, а заполнение \mathcal G, для которого \omega(\mathcal G)=\operatorname{mf}(\mathcal M), — минимальным заполнением. Основная задача — научиться вычислять \operatorname{mf}(\mathcal M) и описывать минимальные заполнения.

Примечания[править | править вики-текст]

  1. Fermat P. de (1643), Ed. H.Tannery, ed., «"Oeuvres"», vol. 1, Paris 1891, Supplement: Paris 1922, сс. 153, <http://www.archive.org/details/oeuvresdefermat901ferm> 
  2. G. Loria, G. Vassura (1919), «Opere de Evangelista Torriceli», vol. 1, сс. 79-97 
  3. 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.
  4. B. Cavalieri (1647), «Excercitationes Geometricae» 
  5. T. Simpson (1750), «"The Doctrine and Application of Fluxions"» 
  6. F. Heinen (1834), "«Über Systeme von Kräften»", Gymnasium zu Cleve (Essen) 
  7. 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, <https://eudml.org/doc/25703#content> 
  8. 1 2 R. Courant, H. Robbins (1941), «What Is Mathematics?», Oxford University Press 
  9. Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — С. 306-311. — ISBN 5-7038-2886-4.
  10. A. O. Ivanov, A. A. Tuzhilin. «One-dimensional Gromov minimal filling».

Литература[править | править вики-текст]