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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Мінімальне дерево Штейнера для точок A, B і C, де S — точка Ферма трикутника ABC.
Steiner 4 points.svg

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

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

Основні визначення[ред.ред. код]

Наведемо кілька сучасних формулювань проблеми Штейнера. В якості осяжного простору замість евклідової площини розглянемо довільний метричний простір.

Мінімальні дерева Штейнера[ред.ред. код]

Нехай  (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. Таким чином, загальна задача Штейнера зводиться до вивчення мінімальних параметричних мереж та вибору з них найкоротших.

Одновимірні мінімальні заповнення в сенсі Громова[ред.ред. код]

Це природне узагальнення проблеми Штейнера було запропоновано А. О. Івановим і А. А. Тужиліним.[9] Нехай 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, ред., "Oeuvres", 1, Paris 1891, Supplement: Paris 1922, сторінки 153, http://www.archive.org/details/oeuvresdefermat901ferm 
  2. G. Loria, G. Vassura (1919), Opere de Evangelista Torriceli, 1, сторінки 79-97 
  3. J. Krarup, S. Vajda On Torricelli's geometrical solution to a problem of Fermat // IMA J. Math. Appl. Bus. Indust., 8 (1997) (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, http://www.pdf.dml.cz/bitstream/handle/10338.dmlcz/122548/CasPestMatFys_063-1934-8_1.pdf 
  8. а б R. Courant, H. Robbins (1941), What Is Mathematics?, Oxford University Press 
  9. A. O. Ivanov, A. A. Tuzhilin One-dimensional Gromov minimal filling.

Література[ред.ред. код]