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

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

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

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

Історія

Історія цієї задачі сягає часу П'єра Ферма (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], в якій автори написали наступне:

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

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

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

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

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

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

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

Нехай ${\displaystyle (X,\rho )}$ — метричний простір і ${\displaystyle G=(V,E)}$ — граф на X, тобто, ${\displaystyle V\subset X}$. Для кожного такого графу визначені довжини його ребер ${\displaystyle e=\{u,v\}\in E}$, як відстані ${\displaystyle \rho (u,v)}$ між їх вершинами, а також довжина ${\displaystyle \rho (G)}$ самого графу ${\displaystyle G}$, як сума довжин всіх його ребер.

Якщо ${\displaystyle M}$ — скінченна підмножина ${\displaystyle X}$, а ${\displaystyle G=(V,E)}$ — зв'язний граф на ${\displaystyle X}$, для якого ${\displaystyle M\subset V}$, то ${\displaystyle G}$ називається графом, що з'єднує ${\displaystyle M}$. При цьому граф ${\displaystyle G}$, що з'єднує ${\displaystyle M}$, мінімально можливої довжини ${\displaystyle \rho (G)}$ є деревом, яке називається мінімальним деревом Штейнера на ${\displaystyle M}$. Саме вивченню таких дерев і присвячена одна з версій проблеми Штейнера.

Зазначимо, що мінімальні дерева Штейнера існують не завжди. Проте, точна нижня грань величин ${\displaystyle \rho (G)}$ по всім зв'язним графам, що з'єднує ${\displaystyle M}$, завжди існує, називається довжиною мінімального дерева Штейнера на ${\displaystyle M}$ та позначається через ${\displaystyle \operatorname {smt} (M)}$.

Приклади

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

Якщо ${\displaystyle (X,\rho )}$ — Манхеттенська відстань, тобто відстань ${\displaystyle \rho }$ породжується нормою ${\displaystyle \|(x,y)\|=|x|+|y|}$, то отримуємо прямокутну проблему Штейнера, одним з додатків якої є проектування розводок мікросхем. Більш сучасні розводки моделюються метрикою, породженою λ-нормою (одиничне коло — правильний 2λ-кутник; в цих термінах манхеттенська норма є 2-нормою).

Якщо як ${\displaystyle X}$ береться сфера (яка приблизно моделює поверхню Землі), а за ${\displaystyle \rho (a,b)}$ — довжина найкоротшої з двох дуг великого кола, яка висікається з сфери ${\displaystyle X}$ площиною, що проходить через ${\displaystyle a}$, ${\displaystyle b}$ та центр сфери, то виходить різновид транспортної задачі: потрібно з'єднати заданий набір пунктів (міст, підприємств, абонентів і т. д.) найкоротшою комунікаційною мережею (доріг, трубопроводів, телефонних ліній і т. д.), мінімізувавши витрати на будівництво (передбачається, що витрати пропорційні довжині мережі).

Якщо як ${\displaystyle X}$ береться множина всіх слів над деяким алфавітом, а як ${\displaystyle \rho (a,b)}$ — відстань Левенштейна, то виходить варіант проблеми Штейнера, який широко використовується в біоінформатиці, зокрема, для побудови еволюційного дерева.

Якщо як ${\displaystyle X}$ береться множина вершин ${\displaystyle V}$ зв'язного графу ${\displaystyle G=(V,E)}$, а як ${\displaystyle \rho }$ — функція відстані, породжена деякою ваговою функцією ${\displaystyle \omega \colon E\to \mathbb {R} }$, то виходить проблема Штейнера у графах.

Мінімальні параметричні мережі

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

Позначимо через ${\displaystyle [G,\varphi ]}$ безліч всіх мереж типу ${\displaystyle (G,\partial G)}$ з кордоном ${\displaystyle \varphi }$. Мережа з ${\displaystyle [G,\varphi ]}$, що має найменшу можливу довжину, називається мінімальною параметричною мережею типу ${\displaystyle (G,\partial G)}$ з кордоном ${\displaystyle \varphi }$.

Зазначимо, що, як і у випадку мінімальних дерев Штейнера, мінімальна параметрична мережа існує не завжди. Проте, точна нижня грань величин ${\displaystyle \rho (G)}$ по всіх мережах з ${\displaystyle [G,\varphi ]}$, завжди існує, називається довжиною мінімальної параметричної мережі і позначається через ${\displaystyle \operatorname {mpn} [G,\varphi ]}$.

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

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

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