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

Мінімальне дерево Штейнера для точок A, B і C, де S — точка Ферма трикутника ABC.

Розв'язок для чотирьох точок — дві точки Штейнера S1 і S2

Задача Штейнера (Задача дерева Штейнера) полягає у пошуку мінімального дерева Штейнера — найкоротшої мережі, що з'єднує заданий скінченний набір точок площини. Свою назву отримала на честь Якоба Штейнера (1796–1863).

Історія

Історія цієї задачі сягає часу П'єра Ферма (1601–1665), який, після викладу свого методу дослідження мінімумів та максимумів, написав :

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.

Той же, хто цей метод не оцінив, нехай він вирішить [наступну задачу]: для заданих трьох точок знайти таку четверту, що якщо з неї провести три відрізки в дані точки, то сума цих трьох відрізків дасть найменшу величину.

Ця задача була частково розв'язана Еванджелістою Торрічеллі (1608–1647) і Бонавентурою Кавальєрі (1598–1647), учнями Бенедетто Кастеллі (1577–1644), потім знайдена ними конструкція була модифікована Томасом Сімпсоном (1710–1761) і остаточно уточнена Ф. Гайненом і Жозефом Бертраном (1822–1900). У результаті було отримано геометричну побудову точки S, що називається точкою Ферма (іноді точкою Торрічеллі), яка для трьох заданих точок A, B і C дає мінімально можливу суму довжин відрізків AS, BS, CS.

1934 року В. Ярнік і O. Кесслер сформулювали узагальнення задачі Ферма, замінивши три точки на довільне скінченне число. Їх задача полягає в описі зв'язаних плоских графів найменшої довжини, що проходять через дану скінченну множину точок площини.

1941 року вийшла монографія Ріхарда Куранта і Герберта Роббінса «Що таке математика?», в якій автори написали наступне:

Дуже проста та разом з тим повчальна проблема була вивчена на початку минулого століття знаменитим берлінським геометром Якобом Штейнером. Потрібно з'єднати три села $A$, $B$, $C$ системою доріг таким чином, щоб їх загальна довжина була мінімальною.Було б природно узагальнити цю проблему на випадок $n$ заданих точок $A_{1},A_{2},\ldots ,A_{n}$ таким чином: потрібно знайти в площині таку точку $P$, щоб сума відстаней $a_{1}+a_{2}+\ldots +a_{n}$ (де $a_{i}$ позначає відстань $PA_{i}$) ставала мінімальною... . Ця узагальнена проблема, також вивчена Штейнером, не веде до цікавих результатів. У цьому випадку ми маємо справу з поверхневим узагальненням, подібних якому чимало зустрічається в математичній літературі. Щоб отримати дійсно гідне уваги узагальнення проблеми Штейнера, доводиться відмовитися від пошуків однієї-єдиної точки $P$. Замість того поставимо завданням побудувати «вуличну мережу» або «мережу доріг між даними селами», що має мінімальну загальну довжину.

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

Алгоритм розв'язування

Ефективного (складність виражається функцією, обмеженою зверху деяким поліномом від параметра завдання, в даному випадку число вершин графу) алгоритму, що дає точне рішення проблеми Штейнера, не існує. Наближене рішення дає ефективний алгоритм Крускала.

Основні визначення

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

Мінімальні дерева Штейнера

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

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

Це природне узагальнення проблеми Штейнера було запропоновано А. О. Івановим і А. А. Тужиліним. Нехай $M$ — довільна скінченна множина і $G=(V,E)$ — деякий зв'язний граф. Будемо говорити, що $G$ з'єднує $M$, якщо $M\subset V$. Нехай тепер ${\mathcal {M}}=(M,\rho )$ — скінченний псевдометричний простір (де, на відміну від метричного простору, відстані між різними точками можуть бути рівні нулю), $G=(V,E)$ — зв'язний граф, що з'єднує $M$, і $\omega \colon E\to {\mathbb {R} }_{+}$ — деяке відображення в невід'ємні дійсні числа, як правило зване ваговою функцією і породжує зважений граф ${\mathcal {G}}=(G,\omega )$. Функція $\omega$ задає на $V$ псевдометріку $d_{\omega }$, а саме, відстанню між вершинами графу ${\mathcal {G}}$ назвемо найменшу з ваг шляхів, що з'єднують ці вершини. Якщо для будь-яких точок $p$ та $q$ з $M$ виконується $\rho (p,q)\leq 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}})$ і описувати мінімальні заповнення.

Література

• А. О. Іванов, А. А. Тужилін. Теорія екстремальних мереж. — Москва-Іжевськ : Інститут комп'ютерних досліджень, 2003. — ISBN 5-93972-292-X.
• А. О. Іванов, А. А. Тужилін. Задача Штейнера на площині або плоскі мінімальні мережі // матем. сб.. — 1991. — Т. 182, № 12. — С. 1813-1844.
• Weisstein, Eric W. Steiner Tree(англ.) на сайті Wolfram MathWorld.