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

Нехай ${\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}})}$ і описувати мінімальні заповнення.