| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях) Проблема Ферма–Штейнера в пространстве компактных подмножеств А. Х. Галстянab, А. О. Ивановabc, А. А. Тужилинab a Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова b Московский центр фундаментальной и прикладной математики c Московский государственный технический университет имени Н. Э. Баумана (национальный исследовательский университет)
Англоязычная версия:
Sbornik: Mathematics, 2021, Volume 212, Issue 1, Pages DOI: https://doi.org/10.1070/SM9343 
Реферативные базы данных:
      § 1. ВведениеГеометрические вариационные задачи об оптимальном соединении привлекают внимание специалистов на протяжении столетий как своей математической красотой и сложностью, так и прикладной значимостью. Если говорить неформальным языком, общая постановка проблемы такова: требуется соединить заданное конечное подмножество $A=\{A_1,\dots,A_n\}$ метрического пространства $(Y,\rho)$ неким оптимальным в смысле общей длины соединения образом (мы предполагаем, что известно, как соединять пары точек в $(Y,\rho)$, поэтому остается выбрать, какие именно точки соединить). Подробный исторический обзор и сводку современных результатов можно найти в книгах [1] или [2], а также в [3]. Впервые подобную задачу поставил, видимо, П. Ферма, предложивший своим ученикам найти такую точку плоскости, что сумма расстояний от нее до трех фиксированных точек минимальна. Таким образом, уже Ферма рассматривал дополнительные вершины, “дорожные развилки”, при минимизации общей длины соединения. Сходные вопросы обсуждались в работах Ж. Д. Жергонна, И. К. Ф. Гаусса и других специалистов, и современная формулировка задачи поиска кратчайшего дерева, соединяющего данное конечное подмножество точек метрического пространства, появилась (для случая плоскости) в работе В. Ярника и М. Кёсслера [4]. Благодаря замечательной книге [5] эта задача стала широко известна как проблема Штейнера. Поиск глобального минимума может быть чрезвычайно труден, и это в полной мере относится к проблеме Штейнера. Здесь сложность возникает благодаря так называемому “комбинаторному взрыву” – очень быстро растущему (с ростом числа $n$ граничных точек) количеству возможных способов соединения между собой исходных и добавленных точек пространства, другими словами – количеству структур деревьев, которые могут соединять данную границу. Чтобы уменьшить комбинаторную сложность, рассматривают другие постановки задачи о минимальном соединении. Одна из возможностей состоит в том, чтобы зафиксировать структуру дерева (так называемая задача о поиске минимального параметрического дерева; см. [1]). Самая простая структура в этом случае – дерево типа звезда, единственная дополнительная вершина $y$ которого соединена с каждой точкой исходного множества $A$. Длина такого дерева, очевидно, равна сумме расстояний от $y$ до всех точек из $A$. Таким образом, возникает задача Ферма–Штейнера: для заданного конечного подмножества $A=\{A_1,\dots,A_n\}$ метрического пространства $(Y,\rho)$ требуется найти все точки $y\in Y$, в которых функция $S_A(y)=\sum_i\rho(y,A_i)$ принимает наименьшее значение. Именно этим обобщением задачи Ферма занимался Я. Штейнер для случая плоскости и трехмерного пространства. Точки из множества $A$ называют граничными, а само множество $A$ – границей или граничным множеством. Через $\Sigma(A)$ мы обозначим множество всех решений задачи Ферма–Штейнера для граничного множества $A$. Сами решения обычно называют точками Ферма–Штейнера или, иногда, геометрическими средними для $A$. Следует отметить, что задача Ферма–Штейнера на плоскости эквивалентна так называемой задаче Вебера с постоянной весовой функцией; см. [6]. Еще одна близкая, но другая задача была поставлена Д. Цисликом, который предложил минимизировать длину всех деревьев, соединяющих данное граничное множество и имеющих не более $k$ дополнительных вершин; см. [2]. Подчеркнем, что при $k=1$ эта задача не эквивалентна задаче Ферма–Штейнера: единственная дополнительная вершина в случае Цислика не обязательно соединяется со всеми граничными вершинами. В общем случае множество решений $\Sigma(A)$ задачи Ферма–Штейнера может оказаться пустым, но для ограниченно компактных метрических пространств1 решение существует для любого непустого граничного множества $A$; см. [7]. В настоящей работе проблема Ферма–Штейнера рассматривается в метрическом пространстве $Y=\mathscr{H}(X)$ непустых замкнутых ограниченных подмножеств метрического пространства $X$, где в качестве метрики на $\mathscr{H}(X)$ берется расстояние Хаусдорфа (см. [8], а также [9] и п. 2.2 ниже). Геометрия пространств $\mathscr{H}(X)$ активно изучается благодаря таким важным приложениям, как распознавание и сравнение образов, построение непрерывных деформаций геометрических объектов друг в друга и др. (см., например, [10], где изучаются кратчайшие кривые в пространствах $\mathscr{H}(X)$, или [11]–[13], где рассматривается более общее расстояние Громова–Хаусдорфа). Проблема Ферма–Штейнера в $\mathscr{H}(X)$ также имеет потенциальные приложения. По сравнению с задачей о поиске точки $x\in X$, на которой достигается минимум суммы расстояний Хаусдорфа до подмножеств $A_i$, входящих в границу $A$, при решении проблемы Ферма–Штейнера в $\mathscr{H}(X)$ минимизация идет по существенно более широкому классу объектов, а именно по всем (а не только по одноточечным) замкнутым ограниченным подмножествам в $X$. Как следствие, минимальное значение может существенно уменьшиться. В этом случае более сложные неодноточечные “развилки” могут дать существенную экономию в стоимости соединения в целом. С другой стороны, каждый элемент $K\in\Sigma(A)$ можно рассматривать как некое “усреднение” исходных граничных множеств $A_i$, что дает возможность строить деформацию любого $A_i$ в любое $A_j$ через общую “усредненную развилку” $K$. Проблема Ферма–Штейнера в $\mathscr{H}(X)$ для ограниченно компактного метрического пространства $X$ рассматривалась в работе [7]. В этом случае $\mathscr{H}(X)$ совпадает с множеством всех компактных подмножеств пространства $X$. Помимо доказательства существования решения для любого непустого конечного граничного множества $A\subset\mathscr{H}(X)$ в работе [7] описана структура множества $\Sigma(A)$ всех решений, которые называются компактами Штейнера. Напомним основные результаты из [7]. Пусть $K\in \Sigma(A)$ – это некоторый компакт Штейнера. Рассмотрим вектор $d(K,A)=(d_H(K,A_1),\dots,d_H(K,a_n))$ расстояний от $K$ до граничных компактов, и пусть $\Omega(A)=\{d(K,A)\colon K\in\Sigma(A)\}$. Для каждого $d\in\Omega(A)$ положим $\Sigma_d(A)=\{K\in\Sigma(A)\colon d(K,A)=d\}$. Таким образом, множество $\Sigma(A)$ непусто и разбито на классы $\Sigma_d(A)$, $d\in \Omega(A)$, соответствующие наборам расстояний $d$ до граничных компактов $A_i\in A$. Каждый класс $\Sigma_d(A)$, как правило, состоит более чем из одного элемента, и эти элементы частично упорядочены по включению. В работе [7] показано, что каждый класс $\Sigma_d(A)$ содержит наибольший элемент (так называемый максимальный компакт Штейнера) и минимальные элементы (называемые минимальными компактами Штейнера), и, более того, компакт $K\subset X$ является компактом Штейнера из класса $\Sigma_d(A)$, если и только если $K$ содержится в наибольшем и содержит один из минимальных компактов Штейнера из $\Sigma_d(A)$. Отметим, что поиск векторов расстояний $d$ – это отдельная и нетривиальная задача; см. замечание 6. Также в [7] построен неожиданный пример симметричного граничного множества $A=\{A_1,A_2,A_3\}\subset \mathscr{H}(\mathbb{R}^2)$, где каждое $A_i$ состоит из двух соседних вершин правильного шестиугольника и $A_i$ получается из $A_j$ поворотом вокруг центра $O$ описанной вокруг этого шестиугольника окружности на угол $\pm 2\pi/3$ (см. § 4). Для этого случая в [7] полностью описаны все компакты Штейнера, а именно оказалось, что имеется три класса $\Sigma_d(A)$, для каждого из которых максимальный компакт Штейнера представляет собой невыпуклый криволинейный четырехугольник, единственный минимальный компакт состоит из двух точек, а компакты одного класса получаются из другого поворотами вокруг точки $O$ на углы $\pm 2\pi/3$. Каждое кратчайшее дерево несимметрично относительно таких поворотов, а длина его меньше $3$; см. точный ответ ниже (теорема 11). В настоящей работе мы продолжаем исследования, начатые в [7]. Рассматривается задача Ферма–Штейнера в пространстве $\mathscr{H}(\mathbb R^m)$ для граничных множеств $A=\{A_1,\dots,A_n\}$, где $A_i$ – попарно не пересекающиеся конечные подмножества $\mathbb R^m$. Основное внимание уделяется изучению свойств компактов Штейнера из фиксированного непустого класса $\Sigma_d(A)$. В работе получен критерий того, когда компакт $K\in\mathscr{H}(\mathbb R^m)$ является минимальным компактом Штейнера (теорема 3), предъявлен алгоритм построения минимальных компактов для заданного вектора $d$ (алгоритм 1), описан ряд геометрических свойств максимального компакта Штейнера (п. 3.3). Опираясь на эти результаты, мы получим оценку на количество точек в минимальном компакте (теоремы 6 и 7). В работе введено понятие так называемого множества сцепки максимального компакта Штейнера с границей $A=\{A_1,\dots,A_n\}$ (определение 3), которое обозначается $\operatorname{HP}(A)$. В терминах множеств сцепки сформулирован критерий единственности минимального компакта (теорема 8) в классе $\Sigma_d(A)$. Показано, что $\operatorname{HP}(A)$ пересекается с каждым минимальным компактом Штейнера из $\Sigma_d(A)$ (утверждение 12). Отметим также, что в настоящей работе получен ряд важных технических результатов, характеризующих расположение компактов Штейнера, например следствие 2 и теорема 10. В § 4 полученные результаты применяются к рассмотренному в работе [7] граничному множеству. Разработанная в данном исследовании техника позволила получить тот же нетривиальный ответ (теорема 11), но существенно более простым и прозрачным образом. § 2. Необходимые определения и предварительные результатыНапомним необходимые понятия из теории графов и метрической геометрии и фиксируем соответствующие обозначения. Более подробные сведения по теории графов можно найти, например, в [14], а по метрической геометрии – в [9] или [15]. 2.1. ГрафыПростым графом называется пара $(V, E)$, состоящая из конечного множества $V$ и некоторого множества $E$ двухэлементных подмножеств $\{u,v\}\subset V$. Элементы из $V$ называют вершинами, а из $E$ – ребрами графа. Если $e=\{u,v\}\in E$, то говорят, что вершины $u$ и $v$ являются соседними или смежными и соединены ребром $e$. Количество вершин графа, смежных с данной вершиной $u$, называется степенью вершины $u$ и обозначается через $\deg u$. Для удобства будем писать $uv$ вместо $\{u,v\}$ и, поскольку далее рассматриваются только простые графы, слово “простой” будем опускать. Чередующаяся последовательность $v_1, e_1, v_2, e_2, \dots, e_l, v_{l+1}$ вершин и ребер графа такая, что $e_i=v_i v_{i+1}$, $1\leqslant i\leqslant l$, называется маршрутом, соединяющим вершины $v_1$ и $v_{l+1}$ или $(v_1, v_{l+1})$-маршрутом. В случае простого графа $(v_1, v_{l+1})$-маршрут можно задать последовательностью $v_1, v_2, \dots, v_{l+1}$ его попарно смежных вершин, а также последовательностью $e_1, e_2, \dots, e_l$ попарно пересекающихся ребер. Путем в графе $G$ называется маршрут, все вершины которого попарно различны. Граф называется связным, если любые две его несовпадающие вершины можно соединить маршрутом (а значит, и путем). Пусть $M$ – произвольное множество; тогда граф $G=(V,E)$, множество вершин которого содержится в $M$, называется графом на множестве $M$. Например, часто рассматривают графы на поверхностях или на метрических пространствах. Пусть $G=(V,E)$ – связный граф, и пусть $A\subset V$. Тогда говорят, что $G$ соединяет $A$; при этом вершины из $A$ называют граничными, само множество $A$ – границей графа, а вершины из $V\setminus A$ называют внутренними. Отметим, что граница графа не определена однозначно и фиксируется в зависимости от конкретной задачи. В качестве примера, который будет использоваться в дальнейшем, рассмотрим так называемую звезду – граф с $n$ вершинами степени $1$, одной вершиной степени $n$ и $n$ ребрами, граница которого по определению состоит из всех его вершин степени $1$. Неотрицательная вещественнозначная функция $\omega\colon E \to \mathbb R_{+}$, заданная на множестве ребер графа $G=(V,E)$, называется весовой функцией, ее значение $\omega(e)$ на ребре $e$ – весом этого ребра $e$, а пара $(G,\omega)$ называется взвешенным графом. Сумма весов всех ребер взвешенного графа $(G,\omega)$ называется весом графа и обозначается через $\omega(G)$. Если $(X,\rho)$ – (псевдо)метрическое пространство и $G=(V,E)$ – произвольный граф на $X$, то на ребрах графа $G$ возникает естественная весовая функция $\omega_\rho$, а именно $\omega_\rho(uv)=\rho(u,v)$, где $uv\in E$. 2.2. Метрика ХаусдорфаПусть $(X,\rho)$ – произвольное метрическое пространство; когда это не вызывает недоразумений, расстояние $\rho (a,b)$ между его произвольными точками $a$ и $b$ будем обозначать через $|ab|$. Расстоянием от точки $p\in X$ до непустого подмножества $A\subset X$ будем называть следующую величину: $|pA|=\inf \{|pa|\colon a\in A\}$. Далее, замкнутой окрестностью $B_r(A)$ радиуса $r$ и открытой окрестностью $U_r(A)$ радиуса $r$ непустого подмножества $A\subset X$ называются соответственно следующие подмножества:
$$
\begin{equation*}
B_r(A)=\{ p\colon |pA| \leqslant r \},\qquad U_r(A)=\{ p\colon |pA| < r\}.
\end{equation*}
\notag
$$
Наконец, сферой радиуса $r$ с центром в $A$ называется множество $S_r(A)=\{ p$: $|pA|=r\}$. В частном случае, когда $A=\{a\}$, для удобства будем писать просто $B_r(a)$, $U_r(a)$ и $S_r(a)$, опуская фигурные скобки. Расстоянием Хаусдорфа между непустыми подмножествами $A$ и $B$ метрического пространства $X$ называется величина
$$
\begin{equation*}
d_H(A,B)=\inf\{r \mid A \subset B_r(B),\, B\subset B_r(A)\}.
\end{equation*}
\notag
$$
Хорошо известно (см., например, [9] или [15]), что расстояние Хаусдорфа задает метрику на семействе $\mathscr{H}(X)$ замкнутых ограниченных подмножеств пространства $X$. Соответствующее метрическое пространство $(\mathscr{H}(X),d_H)$ называется иногда пространством Хаусдорфа. В дальнейшем нам также будет полезно следующее равенство, которое можно рассматривать как эквивалентное определение расстояния Хаусдорфа:
$$
\begin{equation*}
d_H(A,B)=\max\Bigl\{ \sup_{a \in A} |aB|, \,\sup_{b \in B} |bA|\Bigr\}.
\end{equation*}
\notag
$$
Из определения расстояния Хаусдорфа вытекает следующее утверждение (см., например, [15; предложение 5.3]). Утверждение 1. Пусть $A_1, A_2\in \mathscr{H}(X)$ и $d_H(A_1,A_2)=d$. Тогда $A_1\subset B_d(A_2)$ и $A_2\subset B_d(A_1)$. В частности, для любой точки $x\in A_i$ пересечение $A_j\cap B_{d}(x)$ непусто, где $\{i,j\}=\{1,2\}$. 2.3. СоответствияТехника соответствий оказывается весьма полезной при изучении расстояния Хаусдорфа. Напомним, что отношением между множествами $X$ и $Y$ называется произвольное подмножество декартова произведения $X \times Y$. Отношение $R$ между $X$ и $Y$ называется соответствием, если ограничения канонических проекций
$$
\begin{equation*}
\pi_X\colon X \times Y \to X, \qquad \pi_Y\colon X \times Y \to Y
\end{equation*}
\notag
$$
на $R$ – сюръекции. Удобно рассматривать отношение между $X$ и $Y$ как частично определенное многозначное “отображение”, заимствуя при этом соответствующую терминологию. Тогда для каждого отношения $R$, $x\in X$ и $y\in Y$ естественно определяются образ и полный прообраз:
$$
\begin{equation*}
R(x)=\{y\in Y\colon (x,y)\in R\},\qquad R^{-1}(y)=\{x\in X\colon (x,y)\in R\}.
\end{equation*}
\notag
$$
Отношение является соответствием, если образ каждого $x\in X$ и прообраз каждого $y\in Y$ непусты. Отметим также, что соответствия естественным образом упорядочены по включению. Если множества $X$ и $Y$ конечны и не пересекаются, то отношение $R$ между ними удобно задавать с помощью двудольного графа $G_R$ с множеством вершин $X\sqcup Y$, две вершины $x\in X$ и $y\in Y$ которого соединены ребром, если и только если $(x,y)\in R$. Задача. Предположим, что конечное множество $Y$ представлено в виде дизъюнктного объединения непустых множеств $C_1, \dots, C_n$, $\# C_i=p_i$. Требуется определить максимальное возможное количество элементов множества $X$, при котором существует соответствие $R$ между $X$ и $Y$, удовлетворяющее следующему условию 1. Условие 1. Образ $R(x)$ каждого элемента $x\in X$ пересекается с каждым $C_i$, $i=1,\dots,n$, и содержит такой $y\in Y$, что $R^{-1}(y)=\{x\}$. Пусть $R$ – соответствие между $X$ и $Y$, удовлетворяющее условию 1, и $G_R$ – граф этого соответствия. Фиксируем произвольную вершину $x\in X$. Она смежна по крайней мере с одной вершиной $y\in Y$ степени $1$. Среди всех таких вершин выберем одну и будем говорить, что она помечена $x$. Проделаем это для всех вершин $x\in X$. Следующее очевидное наблюдение будет являться ключевым. Лемма 1. Определенная выше разметка является инъекцией из множества $X$ в некоторое подмножество в $Y$, содержащее только вершины степени $1$. В частности, множество $X$ конечно. Теорема 1. Пусть соответствие $R$ между $X$ и $Y=\bigsqcup_{i=1}^n C_i$ удовлетворяет условию 1. Если все $C_i$, кроме, быть может, одного, состоят из одного элемента, то $\#X\leqslant\#Y\,{-}\,n\,{+}\,1$. Если по меньшей мере два множества $C_i$ состоят больше чем из одного элемента, то $\#X\,{\leqslant}\, \#Y\,{-}\,n$. Обе оценки точные, а именно, для каждого $Y=\bigsqcup_{i=1}^n C_i$ найдутся $X$ и соответствие $R$ такие, что соответствующая оценка выполняется в виде равенства. Доказательство. Напомним, что $\#Y=\sum_{i=1}^n p_i$. Рассмотрим двудольный граф $G_R$ соответствия $R$.
Если $C_i$ состоит из одного элемента, то степень соответствующей вершины в графе $G_R$ равна $\#X$. Поэтому если все $C_i$ состоят из одного элемента, то $X$ тоже состоит из одного элемента (иначе степень каждой вершины из $Y$ будет больше $1$, что противоречит условию). Таким образом, в этом случае $\#X=1=\sum_{i=1}^n 1-n+1$, и оценка выполнена в форме равенства. Пусть теперь только одно из $C_i$ состоит более чем из одного элемента, для определенности пусть $p_1>1$. Тогда При $\# X = 1$ оценка $\# X = 1 < p_1$ имеет место по предположению. Если же $X$ содержит больше одного элемента, то все помеченные вершины лежат в $C_1$, так как все остальные имеют степень $\#X>1$, поэтому $\#X\leqslant p_1$ в силу леммы 1, что и требовалось.Покажем, что в случае $p_1 > 1$, $p_2=\dots=p_n=1$ оценка также точна. Для этого достаточно рассмотреть множество $Y=C_1\sqcup\{c_2\}\sqcup\cdots\sqcup\{c_n\}$, где $\# C_1=\#X=p_1$, фиксировать произвольную биекцию $f\colon X\to C_1$ и задать соответствие $R$, положив $R(x)=\{f(x),c_2,\dots,c_n\}$. Пусть теперь имеется не меньше двух $C_i$, для которых $p_i>1$. Если все помеченные вершины попали в одно и то же $C_i$, то $\# X\,{\leqslant}\, p_i\,{\leqslant}\, \sum_{k=1}^n p_k\,{-}\,n$, где последнее неравенство имеет место, так как среди чисел $p_j$, $j\ne i$, по крайней мере одно больше единицы. Если же помеченные вершины попали хотя бы в два разных $C_i$, то в каждом $C_j$, $j=1,\dots,n$, имеется по крайней мере одна непомеченная вершина. Действительно, если вершиной $x\in X$ помечена вершина из $C_i$, то во всех остальных $C_j$, $j\ne i$, есть не помеченные $x$, но смежные с ней вершины. Следовательно, все они не помечены в силу леммы 1. Поэтому если в $C_j$, $j\ne i$, тоже есть помеченная вершина, то в $C_i$ есть непомеченная, что и требовалось. Таким образом, число помеченных точек (равное $\# X$) будет не больше, чем $\sum_{i=1}^n (p_i-1)=\#Y-n$, и искомая оценка имеет место. Покажем, что доказанная оценка точна. Для этого возьмем множество $X$, состоящее из $\#Y-n$ элементов, в каждом множестве $C_i$ выберем по одному элементу $c_i$ и положим $C'_i=C_i\setminus\{c_i\}$ и $Y'=\bigcup C'_i$. Тогда $X$ и $Y'$ состоят из одинакового количества точек. Фиксируем произвольную биекцию и определим соответствие $R$ так: $R(x)=\{f(x),c_1,\dots,c_n\}$. Полученное соответствие $R$ удовлетворяет условию 1.Теорема 1 доказана. Нам также понадобится следующая усиленная версия условия 1. Условие 2. Образ $R(x)$ каждого элемента $x\in X$ пересекается с каждым $C_i$, $i=1,\dots,n$, и содержит такой $y\in Y$, что $R^{-1}(y)=\{x\}$. Кроме того, существуют элемент $x\in X$ и $C_k$ такие, что $R(x)\cap C_k$ состоит не менее чем из двух элементов. Теорема 2. Пусть соответствие $R$ между $X$ и $Y=\bigsqcup_{i=1}^n C_i$ удовлетворяет условию 2. Тогда $\#X\leqslant \#Y - n$, причем данная оценка точна. Доказательство. В ситуации, когда имеется не меньше двух $C_i$, для которых $p_i>1$, утверждение следует из теоремы 1. Предположим, что только $C_k$ состоит более чем из одного элемента. Тогда
$$
\begin{equation*}
\#Y-n=\sum_{i=1}^n p_i-n=p_k+\sum_{i\ne k}1-n=p_k-1\geqslant1,
\end{equation*}
\notag
$$
поэтому при $\# X = 1$ оценка имеет место. Если $\#X\,{>}\,1$, то, как и в доказательстве теоремы 1, все помеченные вершины лежат в $C_k$. Кроме того, $R(x)\cap C_k$ содержит только одну помеченную вершину графа $G_R$, а по условию 2 существует $x$, для которого $R(x)\cap C_k$ состоит, как минимум, из двух элементов, поэтому $\#X\leqslant p_k-1=\#Y-n$.
Покажем, что в случае $p_k > 1$, $C_i=\{c_i\}$ при $i\neq k$ оценка точна. Для этого достаточно взять $X$, состоящее из $p_k-1$ элементов, фиксировать в $C_k$ произвольный элемент $c_k$, фиксировать произвольную биекцию и рассмотреть соответствие $R$, определенное так: $R(x)=\{f(x),c_1,\dots,c_n\}$. Легко проверить, что $R$ удовлетворяет условию 2.Теорема доказана. 2.4. Тривиальная лемма о шарахЛемма 2. Пусть $a_1, a_2, \dots, a_n$ – попарно различные точки некоторого нормированного линейного пространства со строго выпуклой нормой. Тогда если пересечение $C=B_{r_1}(a_1)\cap \cdots \cap B_{r_n}(a_n)$ замкнутых шаров состоит более чем из одной точки, то это пересечение имеет непустую внутренность. Доказательство. Пусть $p$ и $q$ – две произвольные точки из $C$. В силу строгой выпуклости нормы внутренность отрезка $[p,q]$ содержится в каждом открытом шаре $U_{r_i}(a_i)$, поэтому пересечение $U_{r_1}(a_1)\cap \cdots \cap U_{r_n}(a_n)$ открытых шаров непусто, открыто и содержится в $C$, откуда и вытекает требуемое. 2.5. Постановка задачи и компакты ШтейнераВ настоящей работе изучается проблема Ферма–Штейнера в метрическом пространстве $\mathscr{H}(\mathbb R^m)$ всех непустых компактных подмножеств евклидова пространства $\mathbb R^m$ с метрикой Хаусдорфа. Изначально заданный конечный набор точек пространства $\mathscr{H}(\mathbb R^m)$, до которых ищется минимум суммы расстояний Хаусдорфа, мы называем граничным множеством или просто границей, а сами точки – граничными компактами. Данная проблема рассматривается в случае, когда в качестве граничного множества $A\subset\mathscr{H}(\mathbb R^m)$ берется конечный набор $A=\{A_1, \dots, A_n \}$ попарно не пересекающихся конечных подмножеств пространства $\mathbb R^m$. Итак, задача состоит в поиске всех таких элементов $K\in\mathscr{H}(\mathbb R^m)$, которые бы минимизировали функцию $S_A(K)=d_H(A_1,K)+\cdots+d_H(A_n,K)$. В дальнейшем минимальное значение функции $S_A$ обозначается через $S(A)$. Точки из граничного компакта $A_i$ обозначаются через $a_j^i$, а количество точек в нем – через $m_i$. Таким образом, $A_i=\{a_1^i,\dots,a_{m_i}^i\}$. Как известно (см. [7]), в рассматриваемом случае множество решений $\Sigma (A)$ проблемы Ферма–Штейнера непусто. Каждый элемент из $\Sigma (A)$ далее будем называть компактом Штейнера. Пусть фиксирован $K\in \Sigma(A)$. Обозначим величину $d_H(A_i,K)$ через $d_i$ и рассмотрим вектор $d(K)=(d_1,\dots,d_n)$. Множество всех таких векторов для всех $K\in\Sigma(A)$ обозначим через $\Omega (A)$. Пусть $d \in \Omega (A)$. Через $\Sigma_d (A)\subset\Sigma(A)$ обозначим множество всех компактов Штейнера $K$, для которых $d(K)=d$. Множество $\Sigma (A)$ разбивается на непересекающиеся подмножества $\Sigma_d (A)$. В работе [7] изучается структура множеств $\Sigma_d (A)$. Показано, что в $\Sigma_d (A)$ есть единственный наибольший по включению элемент – так называемый максимальный компакт Штейнера $K_d$, причем $K_d=\bigcap_{i=1}^n B_{d_i}(A_i)$, а также каждый компакт Штейнера $K\,{\in}\,\Sigma_d(A)$ содержит некоторый минимальный по включению элемент семейства $\Sigma_d(A)$ – так называемый минимальный компакт Штейнера $K_\lambda$. Более того, компакт $K$ принадлежит $\Sigma_d(A)$ тогда и только тогда, когда $K_\lambda \subset K \subset K_d$ для некоторого минимального $K_\lambda \in \Sigma_d(A)$. § 3. Компакты ШтейнераНа протяжении всего этого параграфа считаем, что $A=\{A_1, \dots, A_n \}\subset \mathscr{H}(\mathbb R^m)$ (где $1<n<\infty$; $\#A_i < \infty$; $A_i\cap A_j=\varnothing$ при $i\neq j$); $\widetilde{A}=\bigsqcup_iA_i$; $d\in \Omega(A)$; $K_d=\bigcap_i B_{d_i}(A_i)$. Для удобства там, где это не вызовет недоразумений, вместо $B_{d_i}(a_j^i)$, $B_{d_i}(A_i)$, $U_{d_i}(a_j^i)$ и $U_{d_i}(A_i)$ будем писать $B_j^i$, $B^i$, $U_j^i$ и $U^i$ соответственно. 3.1. Критерии минимальностиУтверждение 2. Каждый компакт Штейнера $K\in\Sigma_d(A)$ содержит конечный компакт Штейнера $K_f\in\Sigma_d(A)$. В частности, каждый минимальный компакт Штейнера в классе $\Sigma_d(A)$ конечен. Доказательство. Так как $d_H(K,A_i)=d_i$, то для каждой точки $a_j^i\in A$ существует точка $p\in K$ такая, что $|pa_j^i|\leqslant d_i$. Выберем для каждой $a_j^i$ одну такую точку (для разных $a_j^i$ точки могут совпадать); множество всех выбранных точек обозначим через $K_f$. Множество $K_f$, очевидно, является конечным подмножеством $K$, поэтому компактно. Далее, для каждого $i$ выполнены включения $B^i\supset K\supset K_f$ и для каждой точки $a_j^i\in A_i$ существует $p\in K_f$, для которой $|pa_j^i|\leqslant d_i$, поэтому $B_{d_i}(K_f)\supset A_i$ и, значит, $d_H(A_i,K_f)\leqslant d_i$ для всех $i$. Наконец, так как $d\in\Omega(A)$, то $S_A(K)=\sum_{i=1}^n d_i$ – наименьшее значение функции $S_A$. Значит, строгое неравенство $d_H(A_i,K)<d_i$ не может выполняться ни для какого $i$, откуда $d_H(A_i,K_f)= d_i$ для всех $i$, т.е. $K_f\in\Sigma_d(A)$, что и требовалось. Теорема 3. Компакт $K\,{\subset}\,\mathbb R^m$ является минимальным компактом Штейнера в классе $\Sigma_d(A)$ тогда и только тогда, когда одновременно выполняются следующие три условия: Доказательство. Достаточность. Сначала покажем, что компакт $K$, удовлетворяющий условиям теоремы, принадлежит классу $\Sigma_d(A)$.
Так как $K \subseteq K_d$, то $K \subset B^i$ для всех $i$. Из условия (2) вытекает, что для каждой точки $a_j^i\in A_i$ существует $p\in K$, для которой $|pa_j^i|\leqslant d_i$, поэтому $B_{d_i}(K)\supset A_i$, откуда $d_H(A_i,K)\leqslant d_i$. Но $d\in\Omega(A)$, поэтому, как и в доказательстве утверждения 2, $d_H(A_i,K) = d_i$ для всех $i$. Следовательно, $K$ – компакт Штейнера в классе $\Sigma_d (A)$. Покажем теперь, что $K$ является минимальным компактом в своем классе. Предположим противное. Допустим, что есть компакт $K' \in \Sigma_d (A)$ такой, что $K'\ne K$ и $K' \subset K$. Тогда существует такая точка $p\in K$, что $K'\subset K\setminus\{p\}$, и по условию (3) существуют $i \in \{1, \dots , n\}$ и $j \in \{1, \dots , m_i\}$ такие, что $(K' \cap B_j^i)\subset (K\setminus \{p\})\cap B_j^i=\varnothing$, что противоречит утверждению 1. Следовательно, $K$ – минимальный компакт Штейнера. Необходимость. Пусть $K$ произвольный компакт Штейнера из $\Sigma_d(A)$. Тогда $K \subseteq K_d$, так как $K_d$ – наибольший элемент в $\Sigma_d(A)$, и $K\cap B_j^i \neq \varnothing$ для всех $i$ и $j$ согласно утверждению 1, поскольку $d_H(A_i,K)=d_i$. Таким образом, условия (1), (2) выполнены. Пусть теперь $K$ минимальный. Тогда $K$ конечен по утверждению 2, и если условие (3) не выполнено, то найдется точка $p\in K$ такая, что $K\setminus\{p\}$ – компакт, удовлетворяющий условиям (1) и (2). Поэтому, как показано при доказательстве достаточности, $K\setminus\{p\}$ является компактом Штейнера из класса $\Sigma_d(A)$, что противоречит минимальности $K$. Теорема доказана. Определение 1. Пусть $K \in \mathscr{H} (\mathbb R^m)$. Зададим отношение $R(K)\subset K\times \widetilde{A}$ следующим образом: $(p,a_j^i)\in R(K)$, если и только если $|pa_j^i|\leqslant d_i$. Отношение $R(K)$ назовем $d$-каноническим или просто каноническим. Утверждение 3. Пусть $K\subset K_d$ – некоторый непустой компакт. Каноническое отношение $R(K)$ является соответствием тогда и только тогда, когда $K$ – компакт Штейнера в классе $\Sigma_d(A)$. Доказательство. Пусть сначала $R(K)$ – соответствие. Тогда для каждой точки $a_j^i\in \widetilde{A}$ найдется точка $p\in K$ такая, что $(p,a_j^i)\in R(K)$, т.е. $A_i\subset B_{d_i}(K)$. С другой стороны, $K\subset K_d\subset B^i$, поэтому $d_H(A_i,K)\leqslant d_i$. Все эти неравенства могут выполняться только в форме равенства, так как $d\in\Omega(A)$. Поэтому $S_A(K)=\sum_i d_i = S(A)$ и $K$ – компакт Штейнера.
Обратно, если $K\subset K_d\subset B^i$, то для каждой точки $p\in K$ существует точка $a_j^i\,{\in}\,A_i$ такая, что $|pa_j^i|\leqslant d_i$, т.е. $(p,a_j^i)\in R(K)$. С другой стороны, $K$ – компакт Штейнера, поэтому $d_H(K,A_i)=d_i$, откуда $A_i\subset B_{d_i}(K)$, т.е. для каждой $a_j^i\,{\in}\, A_i$ найдется $p\,{\in}\,K$ такая, что $|pa_j^i|\leqslant d_i$, т.е. $(p,a_j^i)\in R(K)$. Значит, $R(K)$ – соответствие. Утверждение доказано. Теорема 4. Пусть $K \in \mathscr{H} (\mathbb R^m)$. Каноническое отношение $R(K)$ является соответствием, удовлетворяющим условию 1, тогда и только тогда, когда $K$ – минимальный компакт Штейнера в классе $\Sigma_d(A)$. Доказательство. Покажем, что $R(K)$ является соответствием, удовлетворяющим условию 1, тогда и только тогда, когда для $K$ справедливы все условия (1)–(3) теоремы 3.
Пусть сначала $R(K)$ – соответствие, удовлетворяющее условию 1. Тогда $K$ конечно по лемме 1, и для любой точки $p\in K$ ее образ $R(p)$ пересекается с каждым $A_i$, значит, $p\in B_j^i$ для подходящего $j$, откуда $K\subset B^i$ для любого $i$, т.е. $K\subset K_d$, и выполнено условие (1) теоремы 3. Далее, так как $R(K)$ – соответствие, то для каждой точки $a_j^i\in \widetilde{A}$ найдется точка $p\in K$ такая, что $(p,a_j^i)\in R$, т.е. $|pa_j^i|\leqslant d_i$, таким образом, выполнено условие (2) теоремы 3. Наконец, $R(p)$ содержит такую точку $a_j^i$, что $R^{-1}(a_j^i)=\{p\}$, поэтому $K\setminus\{p\}$ не пересекается с $B_j^i$, т.е. выполнено условие (3) теоремы 3. Обратно, пусть $K\in\mathscr{H}(\mathbb R^m)$ удовлетворяет условиям (1)–(3) теоремы 3. Так как $K\subset K_d$, то каждая точка $p\in K$ содержится в каждом шаре $B^i$, значит, $|pa_j^i|\leqslant d_i$ для некоторого $j$, поэтому $R(p)$ пересекается с каждым множеством $A_i$. И обратно, пересечение $K\cap B_j^i$ непусто, значит, и $R^{-1}(a_j^i)$ непусто для любых $i$ и $j$. Итак, $R$ – соответствие, образ которого пересекается с каждым $A_i$. Наконец, для каждой точки $p\in K$ найдется $a_j^i\in A_i$ такая, что $K\setminus\{p\}$ не пересекается с $B_j^i$. Последнее означает, что $R^{-1}(a_j^i)=\{p\}$. Поэтому соответствие $R$ удовлетворяет условию 1. Теорема доказана. Замечание 1. Сформулируем условия теоремы 4 на языке двудольного графа $G_R$ отношения $R$. Отношение $R$ является соответствием, если и только если степени всех вершин графа $G_R$ не меньше $1$. Условие 1 равносильно тому, что каждая вершина $x\in K$ смежна по крайней мере с одной вершиной из каждого $A_i$ и по крайней мере одна из смежных с $x$ вершин имеет степень $1$. 3.2. Построение минимального компакта ШтейнераПриведем алгоритм построения минимального компакта в классе $\Sigma_d(A)$. Алгоритм 1. Шаг 1. Пусть $K'\in \Sigma_d(A)$ – произвольный компакт Штейнера и $R'=R(K')$ – каноническое отношение (например, в качестве $K'$ можно взять максимальный компакт $K_d=\bigcap_i B^i$). Шаг 2. Для каждой точки $a_j^i\in \widetilde{A}$ выберем одну точку $p\in K'$ такую, что $(p,a_j^i)\in R'$ (для разных $a_j^i$ выбранные точки могут совпадать); множество выбранных точек обозначим через $K$. Рассмотрим ограничение отношения $R'$ на множество $K\,{\times}\,\widetilde{A}$. Ясно, что в результате получится каноническое отношение $R=R(K)$. Рассмотрим граф $G_R$ этого отношения. Шаг 3. Если в $K$ содержатся точки, являющиеся вершинами графа $G_R$, смежными лишь с вершинами степени больше $1$, то выбираем любую из этих точек и удаляем ее из множества $K$, перестраиваем отношение $R(K)$ и граф $G_R$. Повторяем шаг $3$ до тех пор, пока это возможно. Утверждение 4. Алгоритм 1 корректен, все построенные алгоритмом множества $K$ – компакты Штейнера, а результат работы алгоритма – минимальный компакт Штейнера. Доказательство. Множество $K$, построенное на шаге 2, конечно, на каждой итерации шага 3 количество точек в множестве $K$ уменьшается на $1$. Если множество $K$ состоит из одной точки, то степени всех смежных с ней вершин равны $1$, поэтому алгоритм прекратит работу через конечное число шагов.
Покажем, что построенный в результате работы алгоритма компакт $K$ удовлетворяет условиям теоремы 3. Множество $K$, построенное на шаге 2, конечно, содержится в $K_d$ и для каждой точки $a_j^i\in \widetilde{A}$ содержит такую точку $p\in K\subset K_d$, что $(p,a_j^i)\in R(K_d)$, т.е. $p\in B_j^i\cap K$, поэтому для $K$ выполнены условия (1), (2) теоремы 3. Кроме того, $K$ – компакт Штейнера по утверждению 3. Далее, на каждой итерации шага 3 мы выбрасываем точку, смежную с вершинами степени больше $1$, поэтому сказанное остается верным для всех построенных алгоритмом компактов $K$. Наконец, по окончании работы алгоритма 1 каждая точка компакта $K$ будет смежна по крайней мере с одной вершиной степени $1$, что означает выполнение условия (3) теоремы 3. Поэтому полученное в результате множество $K$ – это минимальный компакт Штейнера из класса $\Sigma_d(A)$. Утверждение доказано. Замечание 2. Если множество $K'$ на шаге 1 алгоритма 1 конечно, то мы можем опустить шаг 2, положив $K=K'$ и ограничившись лишь шагами 1 и 3. В случаях, когда это целесообразно, будем поступать именно так. Утверждение 5. С помощью алгоритма 1 может быть построен любой минимальный компакт Штейнера $K_\lambda \in \Sigma_d(A)$. Доказательство. Заметим, что на шаге 2 в качестве компакта $K$ можно выбрать любой компакт Штейнера из класса $\Sigma_d(A)$. Если выбрать компакт $K_\lambda$, то он не будет перестраиваться на шаге 3. Доказательство закончено. Пример 1. Покажем, что в одном классе $\Sigma_d(A)$ минимальные компакты Штейнера могут содержать разные количества точек. Граница $A$ состоит из двух компактов плоскости Шаг 1: в качестве компакта $K_1$ возьмем трехточечное множество $\{p_1, p_2, p_3\}$, где $p_2\,{\in}\, L_2\,{\setminus}\, L_3$ и $p_3\,{\in}\, L_3\,{\setminus}\, L_2$, а в качестве компакта $K_2$ – двухточечное множество $\{p_1,q\}$, где $q\in L_2\cap L_3$. Из сделанных предположений о взаимном расположении точек $a_i^j$ вытекает, что $d_H(K_i,A_j)=d_j$, поэтому $K_i\in \Sigma_d(A)$. Рассмотрим канонические отношения $R_i$ для компактов $K_i$ и множества $\widetilde{A}=A_1\sqcup A_2$. Согласно замечанию 2 пропускаем шаг 2. Графы отношений $R_1$ и $R_2$ показаны на рис. 1. Замечаем, что в $K_1$ и в $K_2$ для каждой точки есть смежная с ней вершина степени 1 из $\widetilde{A}$. Поэтому согласно шагу 3 работа алгоритма 1 закончена. В силу утверждения 4 оба компакта $K_i$ являются минимальными, причем первый состоит из трех точек, а второй – из двух. 3.3. Некоторые свойства максимального компакта Штейнера Доказательство. Пусть $d_i=0$. Тогда для любого $K\in \Sigma_d(A)$ имеем $d_H(K,A_i)=d_i=0$, следовательно, $K=A_i$, так как $d_H$ – метрика. Поэтому $\Sigma_d(A)=\{A_i\}$. Обратно, если $\Sigma_d(A)=\{A_i\}$, то $d_i=d_H(A_i,A_i)=0$. Доказательство. Пусть некоторый $d_i$ равен нулю. Тогда $\Sigma_d(A)=\{A_i\}$ согласно лемме 3, и поэтому $K_d=A_i$ в силу следствия 1. Это означает, что ни один компакт $A_j$, $j\neq i$, не содержится в $K_d$.
Пусть далее все $d_i$ больше нуля. Допустим противное: все $A_i$ содержатся в $K_d$. Отметим, что расстояние Хаусдорфа между $P$ и $Q$ из $\mathscr{H}(\mathbb R^m)$ можно записать в виде
$$
\begin{equation*}
d_H(P,Q)=\max \bigl\{\inf\{r \mid P \subset B_r(Q)\},\,\inf\{r \mid Q \subset B_r(P)\}\bigr\}.
\end{equation*}
\notag
$$
Тогда для всех $i$
$$
\begin{equation*}
d_i=d_H(A_i,K_d)=\inf\{r \mid K_d \subset B_r(A_i)\}.
\end{equation*}
\notag
$$
Следовательно, для всех $i,j$
$$
\begin{equation*}
\begin{aligned} \, d_H(A_i,A_j) &=\max \bigl\{\inf\{r \mid A_i \subset B_r(A_j)\},\, \inf\{r \mid A_j \subset B_r(A_i)\}\bigr\} \\ &\leqslant \max \bigl\{\inf\{r \mid K_d \subset B_r(A_j)\},\, \inf\{r \mid K_d \subset B_r(A_i)\}\bigr\}= \max \{d_j,d_i\}. \end{aligned}
\end{equation*}
\notag
$$
Пусть $s\in \{1,\dots , n\}$ такой, что $d_s=\min_i {d_i}$. Тогда
$$
\begin{equation*}
\begin{gathered} \, d_H(A_1,A_s)\leqslant \max \{d_1,d_s\}=d_1, \\ \dots \dots \dots \dots \dots \dots \dots \\ d_H(A_s,A_s)=0<d_s \quad\text{(так как $d_i>0$)}, \\ \dots \dots \dots \dots \dots \dots \dots \dots \\ d_H(A_n,A_s)\leqslant \max \{d_n,d_s\}=d_n. \end{gathered}
\end{equation*}
\notag
$$
Следовательно, $S_A(A_s)=\sum_{i=1}^n d_H(A_i,A_s) < \sum_{i=1}^n d_i = S(A)$, противоречие.
Утверждение доказано. Утверждение 7. Компонента связности максимального компакта $K_d$ либо имеет непустую внутренность, либо представляет собой изолированную точку. Доказательство. Напомним, что максимальный компакт
$$
\begin{equation*}
K_d = \bigcap_{i=1}^n B^i=\bigcup_{j_1,\dots,j_n} B_{j_1}^1\cap \dotsb \cap B_{j_n}^n
\end{equation*}
\notag
$$
представляет собой конечное объединение конечных пересечений замкнутых шаров. Каждое такое пересечение выпукло, поэтому связно, и, значит, целиком лежит в компоненте связности компакта $K_d$. Согласно лемме 2 это пересечение или состоит из одной точки, или имеет непустую внутренность, что и требовалось. Доказательство. Действительно, $K_d=\bigcap_i B^i$, в частности $K_d\subset B^i$. Поэтому если $B^i$ несвязно, т.е. представимо в виде объединения непустых непересекающихся замкнутых подмножеств, $B^i=X_1\,{\sqcup}\, X_2$, то $K_d=(K_d\,{\cap}\, X_1)\sqcup(K_d\cap X_2)$. Подмножества $K_d\cap X_k$, $k=1,2$, замкнуты и не пересекаются. Кроме того, $B^i=\bigcup_j B_j^i$, каждый шар $B_j^i$ связен, поэтому целиком лежит в одном из множеств $X_k$. Но $K_d\cap B_j^i$ непусто для любых $i$ и $j$, поэтому множества $K_d\cap X_k$ также непусты. Таким образом, компакт $K_d$ несвязен, противоречие. Теорема 5. Существуют такие $i \in \{1, \dots, n\}$ и $j \in \{1, \dots, m_i\}$, что множество $B_j^i\cap K_d$ состоит из конечного числа точек. Более того, если $B_j^i\cap K_d$ конечно, то $B_j^i\cap K_d\subset\partial K_d$. Доказательство. Предположим, что для любых $i$ и $j$ множество
$$
\begin{equation}
B_j^i\cap K_d = \bigcup_{j_1\in\{1,\dots,m_1\},\dots, j_n\in\{1,\dots,m_n\}}(B_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n)
\end{equation}
\tag{*}
$$
бесконечно, следовательно, для любых $i$, $j$ существует набор $\{k_1, \dots , k_n\}$, для которого пересечение $B_j^i\cap B_{k_1}^1\cap \dots \cap B_{k_n}^n$ содержит бесконечно много точек. Тогда по лемме 2 имеем $U_j^i\cap U_{k_1}^1\cap \dots \cap U_{k_n}^n\neq \varnothing$, в частности все $d_i$ положительны. Если немного уменьшить радиусы, то последнее пересечение останется непустым, т.е. существует такое $\delta=\delta(i,j)>0$, что если $d^{\delta}$ – произвольный вектор с положительными не превосходящими $\delta$ компонентами, то для вектора $d'=(d'_1,\dots,d'_n)=d-d^{\delta}$ выполняется поэтому $K_{d'}\cap B_{d'_i}(a_j^i)\neq \varnothing$. Выбрав наименьшее такое $\delta$, получим, что $K_{d'}\cap B_{d'_i}(a_j^i)\,{\neq}\, \varnothing$ для всех $i$ и $j$. Но тогда $A_i\,{\subset}\, B_{d_i'}(K_{d'})$, а $K_{d'}\,{\subset}\, B_{d_i'}(A_i)$ по определению, поэтому для любого $i$ справедливо неравенство $d_H(A_i,K_{d'})\leqslant d'_i$, следовательно, противоречие. Таким образом, существует шар $B_j^i$, пересекающийся с $K_d$ по конечному множеству точек.
Пусть $p\in B_j^i\cap K_d$ – точка из такого конечного пересечения. Если она внутренняя для $K_d$, то существует открытый шар $U=U_r(p)$, который лежит в $K_d$. Так как центр этого шара лежит в $B_j^i$, то $U\,{\cap}\, B_j^i$ бесконечно, противоречие. Поэтому $p\in\partial K_d$, что и завершает доказательство. Следствие 2. Пусть $K\,{\in}\,\Sigma_d(A)$ – компакт Штейнера. Тогда $K\,{\cap}\,\partial K_d\,{\neq}\,\varnothing$, т.е. каждый компакт Штейнера $K\in \Sigma_d(A)$ выходит на границу соответствующего максимального компакта $K_d$. Доказательство. По утверждению 1 компакт $K$ пересекает каждый шар $B_j^i$. По теореме 5 одно из пересечений $B_j^i\cap K_d$ конечно, и все входящие в него точки являются граничными для $K_d$. Так как $K\subset K_d$, то поэтому $K$ содержит точки из $\partial K_d$. Оказывается, что в общем случае включение $K\subset\partial K_d$ не имеет места даже для минимального компакта $K_\lambda$. Приведем соответствующий пример. Пример 2. Рассмотрим В этом случае максимальный компакт $K_d$ равен $B_1^2\cup \{p\}$, где $\{p\} = B_2^1\cap B_2^2$. В качестве минимального компакта $K_\lambda$ возьмем множество, состоящее из $p$ и произвольной точки $q\in U_1^2$. Граф канонического отношения будет состоять из четырех ребер $a_1^1q$, $a_1^2q$, $a_2^2p$ и $a_2^1p$ (минимальность вытекает, например, из теоремы 3). Заметим, что ни один из таким образом выбранных минимальных компактов не содержится в границе $K_d$. Отметим также, что в данном примере существует континуум минимальных компактов. Доказательство. Так как $A_i = \{a_1^i\}$, то $B^i=B^i_1$ и $K_d = \bigcap_{i=1}^n B_1^i$. Пусть $\# K_d\,{>}\, 1$. По лемме 2 внутренность $K_d$ непуста, поэтому $\# K_d\,{=}\,\infty$. Но согласно теореме 5 существует $k$ такое, что $B_1^k\cap K_d$ конечно. Однако в рассматриваемом случае $B_1^k\cap K_d =B^k\cap K_d= K_d$, поэтому $K_d$ также конечно, противоречие. Утверждение 9. Предположим, что ни один открытый шар $U_j^i$ не содержит изолированных точек максимального компакта $K_d$. Тогда существует $U_j^i$, который не пересекается с $K_d$. Доказательство. Действительно, любое конечное подмножество открытого шара состоит из изолированных точек. Поэтому пересечение $U_j^i\cap K_d$ или пусто, или бесконечно. Но все пересечения бесконечными быть не могут по теореме 5, поэтому существует шар $U_j^i$, не пересекающийся с $K_d$, что и требовалось. Утверждение 10. Пересечение $B_j^i\cap K_d$ конечно тогда и только тогда, когда $(B_j^i\cap K_d)\subset\partial K_d$. Доказательство. Если $B_j^i\cap K_d$ конечно, то оно содержится в $\partial K_d$ по теореме 5. Обратно, пусть все точки из $B_j^i\cap K_d$ граничные для $K_d$. Напомним, что
$$
\begin{equation*}
B_j^i\cap K_d = \bigcup_{j_1\in\{1,\dots,m_1\},\dots, j_n\in\{1,\dots,m_n\}} (B_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n).
\end{equation*}
\notag
$$
По лемме 2 каждое непустое пересечение в правой части или состоит из одной точки, или имеет непустую внутренность. Но так как каждое такое пересечение содержится в $K_d$, то его внутренняя точка является внутренней и для $K_d$, поэтому второй случай невозможен по предположению. Следовательно, $B_j^i\,{\cap}\, K_d$ конечно как конечное объединение конечных множеств. Утверждение 11. Пусть $U_j^i\cap K_d$ пусто; тогда $B_j^i\cap K_d$ конечно и содержится в $\partial K_d$. Доказательство. Действительно, пусть
$$
\begin{equation*}
B_j^i\cap K_d = \bigcup_{j_1\in\{1,\dots,m_1\},\dots, j_n\in\{1,\dots,m_n\}} (B_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n)
\end{equation*}
\notag
$$
бесконечно. Значит, по крайней мере одно из множеств $B_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n$ бесконечно. Но по лемме 2 это множество имеет непустую внутренность, и, значит, множество $U_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n$ также непусто. Но тогда непусто и множество $U_j^i\cap K_d$, противоречие. Таким образом, $B_j^i\cap K_d$ конечно. Остается применить утверждение 10. Доказательство. Пусть $\# B_j^i\cap K_d=\infty$. Тогда
$$
\begin{equation*}
B_j^i\cap K_d = \bigcup_{j_1\in\{1,\dots,m_1\},\dots, j_n\in\{1,\dots,m_n\}} (B_j^i\cap B_{j_1}^1\cap \dots \cap B_{j_n}^n)
\end{equation*}
\notag
$$
– конечное объединение пересечений конечного числа шаров. Поэтому одно из таких пересечений будет бесконечно, следовательно, согласно лемме 2 оно будет иметь непустую внутренность. Значит, $\operatorname{Int} (B_j^i\cap K_d)\neq \varnothing$. 3.4. Оценки количества точек в минимальном компакте ШтейнераТеорема 6. Каждый минимальный компакт $K_\lambda \in \Sigma_d(A)$ является конечным множеством, количество его точек не превосходит $\# \widetilde{A}\,{-}\, n\,{+}\,1$, а в случае, когда имеется больше одного $A_i$, для которого $m_i >1$, оно не превосходит $\# \widetilde{A} -n$. Доказательство. Пусть $R(K_\lambda)$ – каноническое отношение. Так как $K_\lambda$ – минимальный компакт Штейнера, то согласно теореме 4 отношение $R(K_\lambda)$ является соответствием, для которого справедливо условие 1. Осталось применить теорему 1. В самом общем случае оценки в теореме 6 неулучшаемы. А именно, в примере 1 имеем $\# K_2 = 3=(m_1+m_2)-n$, где $m_1=3$, $m_2=2$, $n=2$. Также приведем пример, когда достигается оценка $\# \widetilde{A} - n+1$. Пример 3. Рассмотрим Замечание 3. Отметим, что теорема 1 говорит о точности верхних оценок для произвольных значений $n$ и $m_i$. Но мы не можем гарантировать точность этих оценок в случае, когда отношение $R$ каноническое, а не произвольное, как в теореме 1. Гипотеза 1. Оценки в теореме 6 точны для произвольных $n$ и $m_i$. Замечание 4. Из теоремы 6 следует, что если класс $\Sigma_d(A)$ содержит в себе всего один компакт, то он является конечным, причем количество точек в нем не превосходит соответствующей оценки (в этом случае $K_d=K_\lambda$). Однако из того, что максимальный компакт $K_d$ является конечным, не следует, что класс $\Sigma_d(A)$ содержит в себе всего один элемент. Построим соответствующий пример. Пример 4. Рассмотрим Доказательство. По следствию 3, если все $m_i$ равны $1$, то $\# K_d = 1$, и поэтому условие теоремы не выполняется. Таким образом, без ограничения общности будем предполагать, что хотя бы для одного $i$ мы имеем $m_i>1$.
Пусть $R=R(K_\lambda)$ – каноническое отношение. Так как $K_\lambda$ – минимальный компакт Штейнера, то по теореме 4 отношение $R(K_\lambda)$ является соответствием, удовлетворяющим условию 1. Покажем, что $R$ удовлетворяет условию 2, т.е. существует точка $p\in K_\lambda$ и $A_i$ такие, что $R(p)\cap A_i$ состоит не менее чем из двух точек. Заметим, что
$$
\begin{equation*}
K_d = K_d \cap B^i = K_d \cap \biggl(\bigcup_{j=1}^{m_i}B_j^i\biggr)=\bigcup_{j=1}^{m_i}(K_d\cap B_j^i).
\end{equation*}
\notag
$$
По предположению в $K_d$ нет изолированных точек, значит, по утверждению 9 найдется такая точка $a_j^i$, что $U_j^i\cap K_d = \varnothing$, откуда согласно утверждению 11 следует, что множество $B_j^i\cap K_d$ конечно, поэтому у каждой точки $p\in B_j^i\cap K_d$ существует окрестность $U$ такая, что $U\,{\cap}\,(B_j^i\,{\cap}\, K_d)=\{p\}$. Если $p$ не содержится ни в каком другом множестве $K_d \cap B_k^i$, где $k\neq j$, то, уменьшая $U$, если нужно, так, чтобы она не пересекалась с шарами $B_k^i$, $k\neq j$, получим $U\cap K_d=\{p\}$, т.е. $p$ – изолированная точка в $K_d$, противоречие. Поэтому каждая точка из множества $B_j^i\cap K_d$ лежит еще в некотором замкнутом шаре $B_k^i$, $k\neq j$.
По теореме 3 пересечение $K_\lambda\,{\cap}\, B_j^i$ непусто для любых $i$ и $j$ и, очевидно, содержится в $B_j^i\cap K_d$, поэтому оно содержит точку $p$, лежащую также и в $B_k^i$, $k\neq j$. Отсюда вытекает, что соответствие $R(p)$ содержит $\{a_j^i,a_k^i\}$, что и требовалось. Остается применить теорему 2. Теорема доказана. Замечание 5. Пусть даны границы Как и в теореме 6, оценка в теореме 7 в самом общем случае неулучшаема. Приведем соответствующий пример. Пример 5. Рассмотрим Положим $d=\{d_1,d_2\}$; тогда $K_d = B_1^1$. Пусть $p=B_1^2\cap B_2^1$. Покажем, что $K_\lambda=\{p\}$. Очевидно, $K_\lambda \subset K_d$. Далее, точка $p$ принадлежит всем трем шарам $B_2^1$, $B_1^2$ и $B_1^1$. Наконец, $K_\lambda\setminus\{p\}=\varnothing$, откуда по теореме 3 получаем, что $K_\lambda$ – минимальный компакт в классе $\Sigma_d(A)$. С другой стороны, $m_1=2$, $m_2=1$, $n=2$ и $\# K_\lambda\,{=}\,1\,{=}\,(m_1\,{+}\,m_2)\,{-}\,n$, так что оценка достигается. Отметим, что граница $A$ содержит только один компакт, состоящий более чем из одной точки. Напомним, что теорема 2 также говорит о точности верхней оценки для произвольных значений $n$ и $m_i$. Но мы не можем гарантировать точность этой оценки, когда отношение $R$ имеет специальный вид, а именно когда оно каноническое. Гипотеза 2. Оценка в теореме 7 точна для произвольных $n$ и $m_i$. 3.5. Сцепка максимального компакта с границейОпределение 2. Если $B_j^i\cap K_d$ конечно, то будем называть это множество множеством сцепки максимального компакта $K_d$ с замкнутой окрестностью точки $a_j^i$ и обозначать через $\operatorname{HP}(a_j^i)$ (от английского hooking points – точки сцепки). Каждую точку из $\operatorname{HP}(a_j^i)$ будем называть точкой сцепки. Положим $\operatorname{HP}(a_j^i)=\varnothing$, если $\# (B_j^i\cap K_d) = \infty$, и обозначим через $\operatorname{HP}(A)$ объединение $\bigcup \operatorname{HP}(a_j^i)$ по всем точкам $a_j^i$. Определение 3. Множество $\operatorname{HP}(A)$ будем называть множеством сцепки максимального компакта с границей $A$. Из теоремы 5 получаем следующий результат. Следствие 4. Множество $\operatorname{HP}(A)$ непусто, конечно и содержится в $\partial K_d$. Если максимальный компакт $K_d$ конечен, то $\operatorname{HP}(A)=K_d$. Утверждение 12. Пусть $K_\lambda\,{\in}\,\Sigma_d(A)$. Тогда для всех $i$, $j$ если $\operatorname{HP}(a_j^i)\,{\neq}\,\varnothing$, то справедливо $K_\lambda\cap \operatorname{HP}(a_j^i)\neq \varnothing$. Доказательство. Допустим противное: существуют $i$, $j$ такие, что
$$
\begin{equation*}
\operatorname{HP}(a_j^i)\neq \varnothing, \qquad K_\lambda\cap \operatorname{HP}(a_j^i) = \varnothing.
\end{equation*}
\notag
$$
Так как
$$
\begin{equation*}
\varnothing=K_\lambda\cap \operatorname{HP}(a_j^i)=K_\lambda\cap B_j^i\cap K_d=K_\lambda\cap B_j^i,
\end{equation*}
\notag
$$
то приходим к противоречию с утверждением 1. Напомним, что в общем случае включение $K_\lambda \subset \partial K_d$ места не имеет (см. пример 2). Поэтому в силу следствия 4 не имеет места включение $K_\lambda \subset \operatorname{HP}(A)$. Однако оно справедливо, если $K_\lambda$ – единственный минимальный компакт в своем классе. Теорема 8 (критерий единственности минимального компакта). Минимальный компакт Штейнера $K_\lambda$ – единственный минимальный компакт в $\Sigma_d(A)$ тогда и только тогда, когда для каждой точки $p\in K_\lambda$ существует точка $a_j^i$ такая, что $\operatorname{HP}(a_j^i)=\{p\}$. Доказательство. Необходимость. Пусть $K_\lambda$ – единственный минимальный компакт в $\Sigma_d(A)$. Допустим, что он содержит в себе точку $p$, для которой не существует точки $a_j^i$ такой, что $\operatorname{HP}(a_j^i)=\{p\}$. Это означает, что все шары $B_j^i$, содержащие точку $p\in K_\lambda$, пересекаются с $K_d$ более чем по одной точке.
Рассмотрим каноническое отношение $R(K_\lambda)$ между $K_\lambda$ и $\widetilde{A}$. Согласно теореме 4 отношение $R(K_\lambda)$ – это соответствие, удовлетворяющее условию 1, поэтому существует непустое семейство $S$ точек $a_j^i$ таких, что $R^{-1}(a_j^i)=\{p\}$. Для каждой $a_j^i\in S$ выберем в пересечении $B_j^i\,{\cap}\, K_d$ точку, отличную от $p$ (напомним, что такая точка существует по условию). Множество выбранных точек обозначим через $Q$ и положим $K=(K_\lambda \setminus \{p\})\cup Q$. Рассмотрим каноническое отношение $R(K)$. Отметим, что по построению $K\subset K_d$ и отношение $R(K)$ является соответствием. Поэтому $K$ – компакт Штейнера по утверждению 3. Применим к $K$ алгоритм 1 и получим минимальный компакт Штейнера, который не содержит точку $p$ и, значит, отличен от исходного $K_\lambda$, что противоречит единственности минимального компакта. Достаточность. Пусть для каждой точки $p\in K_\lambda$ существует точка $a_j^i$ такая, что $\operatorname{HP}(a_j^i)=\{p\}$. Допустим, что в $\Sigma_d(A)$ существует еще один минимальный компакт Штейнера $K'$. Тогда существует точка $p\in (K_\lambda\setminus K')$. Но по условию найдется $a_j^i$ такая, что $\operatorname{HP}(a_j^i)=B_j^i\,{\cap}\, K_d=\{p\}$. А это означает, что $B_j^i\,{\cap}\, K'\,{=}\,\varnothing$. Получили противоречие с теоремой 3. Теорема доказана. Утверждение 13. Пусть компоненты вектора $d\in \Omega(A)$ положительны. Если множество сцепки $\operatorname{HP}(a_j^i)$ непусто, то каждая его точка лежит на границе, как минимум, двух шаров $B_{j'}^{i'}$ и $B_{j''}^{i''}$ с центрами, принадлежащими разным граничным компактам. Доказательство. Пусть $\operatorname{HP}(a_j^i)\neq \varnothing$ и все $d_i$ больше нуля. Согласно следствию 4 имеем $\operatorname{HP}(a_j^i)\subset \partial K_d$. Рассмотрим точку $p\in \operatorname{HP}(a_j^i)=B_j^i\cap K_d=B_j^i\cap \partial K_d$. Получаем, что $p\in B_j^i$ и $p\in \partial K_d$. Заметим также, что Следовательно, для $p\in \operatorname{HP}(a_j^i)$ найдется по крайней мере один шар $B_t^k$ такой, что $p\in \partial B_t^k$.
Возьмем произвольное пересечение $B_{j_1}^1\cap \dots \cap B_{j_n}^n$, содержащее $p$, в котором заменим шары $B_{j_k}^k$ и $B_{j_i}^i$ на шары $B_t^k$ и $B_j^i$ соответственно. Допустим, что $p\in \operatorname{HP}(a_j^i)$ лежит во внутренности всех $B_{j_s}^s$, $s\neq k$, участвующих в полученном пересечении. Следовательно, существует открытый шар $U$ с центром $p$ такой, что $U\subset B_{j_s}^s$ для всех $s\neq k$. Вспоминаем, что $p\in \partial B_{j_k}^k$, поэтому пересечение $B_{j_1}^1\,{\cap}\, {\cdots}\,{\cap}\, B_{j_n}^n$ бесконечно. Один из шаров, участвующих в данном пересечении, равен $B_j^i$, следовательно, $\# (B_j^i\cap K_d)=\infty$, т.е. $\# \operatorname{HP}(a_j^i)=\varnothing$, противоречие. Утверждение доказано. Будем говорить, что на точке $p\in \mathbb R^m$ реализуется расстояние $d_i$, если существует $a_j^i\in A_i$ такая, что $|a_j^ip|=d_i$. Из определения расстояния Хаусдорфа, непрерывности функции $f_A(x)=|xA|$ и компактности элементов пространства $\mathscr{H}(\mathbb R^m)$ вытекает следующая лемма. Лемма 5. Пусть $A,\,B\in\mathscr{H}(\mathbb R^m)$ и $d_H(A,B)=d$. Тогда существуют точки $a\in A$ и $b\in B$ такие, что $|ab|=d$. Из леммы 5 следует, что для любых $d_i$ и $K\in \Sigma_d(A)$ существует точка $p\in K$, на которой реализуется $d_i$. Однако справедливо более сильное утверждение. Теорема 9. Каждое $d_i$ реализуется по крайней мере на одной точке из $K_\lambda \cap \operatorname{HP}(A)$ для любого $K_\lambda\in \Sigma_d(A)$. Доказательство. Пусть некоторое $d_i$ не реализуется ни на одной точке из $K_\lambda \cap \operatorname{HP}(A)$. Отметим, что тогда $K_\lambda \cap \operatorname{HP}(A)\subset U^i$. Однако по лемме 5 существует точка $p\in K_\lambda$, на которой $d_i$ реализовано, т.е. существует шар $B_j^i$ такой, что $p\in \partial B_j^i$. Так как $p\notin K_\lambda \cap \operatorname{HP}(A)$, то $p\notin \operatorname{HP}(A)$. Следовательно, $\# B_j^i\,{\cap}\, K_d = \infty$, поэтому $\operatorname{Int} (B_t^i\,{\cap}\, K_d)\neq \varnothing$ по лемме 4. И вообще, в таком случае для любого шара $B_t^k$, если $p\in B_t^k$, то справедливо $\operatorname{Int} (B_t^k\cap K_d)\neq \varnothing$.
Так как $K_\lambda$ – минимальный компакт Штейнера, то согласно условию (3) теоремы 3 существует шар $B_t^k$ такой, что $B_t^k\,{\cap}\, (K_\lambda \setminus \{p\})\,{=}\,\varnothing$. Значит, $B_t^k\,{\cap}\, K_\lambda\,{=}\, \{p\}$ и $\operatorname{Int} (B_t^k\,{\cap}\, K_d) \neq \varnothing$. Перестроим компакт $K_\lambda$: для всех таких шаров $B_t^k$ заменим в $K_\lambda$ точку $p$ на произвольную точку $q\neq p$ (для каждого шара $B_t^k$ точка $q$ может быть своя) из множества $B_t^k\cap K_d$ такую, что если $k=i$, то $q\in \operatorname{Int} (B_t^i\cap K_d)$ и $q\notin \partial B_s^i$ для всех $s$; другими словами, $q\in B_t^i\cap K_d$ и на $q$ не реализуется $d_i$. Проделаем такие действия для всех точек $p\in K_\lambda$, на которых реализовалось расстояние $d_i$. Полученный компакт обозначим через $K$. Замечаем, что $K\,{\subset}\,K_d$, поэтому $K \subset B^k$ для всех $k$, причем $K\subset U^i$ по построению. Так как для всех шаров $B_t^k$ верно $B_t^k\,{\cap}\, K\,{\neq}\, \varnothing$ и $U_t^i\,{\cap}\, K \,{\neq}\, \varnothing$, то $A_k \subset B_{d_k}(K)$ для любого $k$ и $A_i\subset U_{d_i}(K)$. Это означает, что $d_H(A_k,K)\leqslant d_k$ для всех $k$ и $d_H(A_i,K)<d_i$. Поэтому $S_A(K)=\sum_{k} d_H(A_k,K) < \sum_{k} d_k = S(A)$, противоречие. Теорема доказана. Следствие 5. Каждое $d_i$ реализуется по крайней мере на одной точке $p\,{\in} \operatorname{HP}(A)$. Следствие 6. Для каждого минимального компакта $K_\lambda \in \Sigma_d(A)$ и любого номера $i$ существует точка $p\in K_\lambda$ такая, что на ней реализуются по крайней мере два расстояния $d_i$ и $d_k$ $(i\neq k)$. Доказательство. Согласно теореме 9 для любых $K_\lambda\in \Sigma_d(A)$ и номера $i$ существует $p\in K_\lambda \cap \operatorname{HP}(A)$ такая, что $d_i$ реализуется на $p$. Но в силу утверждения 13 на каждой точке из $\operatorname{HP}(A)$ реализуется минимум два различных расстояния. Поэтому найдется такое $k$ $(k\neq i)$, что $d_k$ тоже реализуется на $p$. 3.6. Листья реализации расстоянийПусть дана точка $p\in \mathbb R^m$. Положим $L_i(p)=\{a_j^i\in A_i\colon |a_j^ip|=d_i\}$. Множество $\bigcup_{i=1}^n L_i(p)$ обозначим через $L(p)$. Определение 4. Множество $L_i(p)$ будем называть множеством листьев реализации расстояния $d_i$ на точке $p$, а множество $L(p)$ – множеством листьев точки $p$. Выпуклую оболочку произвольного множества $X$ будем обозначать через $\operatorname{Conv} X$. Лемма 6. Пусть $M$ – замкнутое выпуклое подмножество пространства $\mathbb R^m$ и точка $x\in\mathbb R^m$ лежит вне $M$. Тогда существуют вектор $v\in \mathbb R^m$ и полуинтервал $I=[0,\varepsilon_0)$, где $\varepsilon_0>0$, такие, что для любой $m\in M$ функция $f_m(\varepsilon)$, равная расстоянию от $m$ до $x+\varepsilon v$, строго монотонно убывает на $I$. Доказательство. Действительно, точка $x$ лежит вне замкнутого выпуклого множества $M$, поэтому отделена от него гиперплоскостью. Выберем в качестве $v$ вектор нормали к этой гиперплоскости, направленный в то ограниченное ею полупространство, которое содержит $M$. Тогда для каждой точки $m\in M$ вектор $v$ имеет положительную проекцию на вектор $xm$, откуда и вытекает требуемое. Теорема 10. Пусть $C$ – конечное подмножество пространства $\mathbb R^m$ и $q\in \mathbb R^m$ – точка, не принадлежащая $C$, такие, что: Тогда $P=(C\cup \{q\})\notin \Sigma_d(A)$. Доказательство. Допустим противное: пусть $P=(C\cup \{q\})\in \Sigma_d(A)$. Введем обозначение $I(x)=\bigcap_{B_j^i\ni x} B_j^i$.
Для любой $c\in C$:
Поэтому $\operatorname{Int} I(c)\neq \varnothing$, т.е. $I(c)$ бесконечно для всех $c\in C$ (во втором случае мы воспользовались леммой 2). Если $q\notin \operatorname{Conv} L(q)$, то в силу тех же рассуждений, что и для точек $c\in C$, множество $I(q)$ бесконечно. В силу утверждения 1 для любых $t$, $s$ существует $p\in P$ такая, что $p\in B_t^s$, т.е. $I(p) =(B_t^s\cap I(p))$. Так как $p\in P\subset K_d = \bigcup_{j_1,\dots,j_n}B_{j_1}^1\cap \dots \cap B_{j_n}^n$, то для некоторых $k_1,\dots , k_n$ справедливо
$$
\begin{equation*}
(B_t^s\cap I(p)) \subset \bigl(B_t^s\cap (B_{k_1}^1\cap \dots \cap B_{k_n}^n)\bigr)\subset (B_t^s\cap K_d).
\end{equation*}
\notag
$$
Следовательно, $B_t^s\cap K_d$ бесконечно для любых $t$ и $s$, что противоречит теореме 5. Пусть теперь $q\in \operatorname{Conv} L(q)$, и пусть без ограничения общности на $q$ реализуются расстояния $d_1,\dots, d_k$. Перестроим теперь точку $q$. Обозначим через $f(x)$ длину сети типа звезда с границей $L(q)$ и дополнительной вершиной $x$. Так как $\# L_i(q) \leqslant 1$ для всех $i$, то $f(q)=\sum_{i=1}^k d_i$. По условию $q$ не является точкой Ферма–Штейнера для $L(q)$, поэтому в силу выпуклости вниз функционала длины существуют вектор $v$ и $\varepsilon>0$ такие, что $f(q+v\varepsilon)<f(q)$. Пусть $\varepsilon$ выбрано для всех $i$ и $j$ так, что $q'=(q+v\varepsilon) \in U_j^i$, если $q\in U_j^i$. Такой выбор можно осуществить в силу того, что $i$ и $j$ принимают конечное число значений. Положим $d'_i=|q'a_j^i|$, где $L_i(q)=\{a_j^i\}$, т.е. Пусть $\mathfrak{I}(c)$ – множество всех шаров, участвующих в пересечении $I(c)$, $c\in C$. Перестроим $\mathfrak{I}(c)$: если $i\in \{1,\dots,k\}$, то заменим в $\mathfrak{I}(c)$ шар $B_j^i$ на $B_{d'_i}(a_j^i)$. Положим $I'(c)=\bigcap_{B\in \mathfrak{I}(c)} B$. Как мы показали выше, $\operatorname{Int} I(c) \neq \varnothing$ для всех $c\in C$. Поэтому можно считать $\varepsilon$ подобранным так, что $\operatorname{Int} I'(c) \neq \varnothing$ для всех $c\in C$. Положим $P'=\bigcup_{c\in C} I'(c) \cup \{q'\}$. Замечаем, что
$$
\begin{equation*}
S_A(P')=\sum_{i=1}^k d'_i+\sum_{i=k+1}^n d_i<\sum_{i=1}^n d_i=S_A(P),
\end{equation*}
\notag
$$
противоречие. Теорема доказана. Замечание 6. Мы описали ряд свойств максимального и минимальных компактов Штейнера в предположении, что вектор $d\in \Omega(A)$ нам известен. Поиск таких векторов – отдельная нетривиальная задача. Отметим, что если удается найти хотя бы один компакт Штейнера $K$, то величины $d_i$ можно вычислить как расстояния Хаусдорфа между $K$ и компактами $A_i$. Зная все $d_i$, т.е. вектор $d$, мы можем построить максимальный компакт Штейнера $K_d$ как пересечение соответствующих $B^i$, а также найти все минимальные компакты Штейнера $K_\lambda$ в классе $\Sigma_d(A)$ посредством алгоритма 1. Так как каждый $K\in \Sigma_d(A)$ лежит между $K_d$ и некоторым минимальным компактом $K_\lambda$, т.е. $K_\lambda\subset K\subset K_d$, то нами будет найден весь класс $\Sigma_d(A)$. § 4. О решении проблемы Ферма–Штейнера в одном частном случаеВ этом параграфе мы применим разработанную выше технику для решения проблемы Ферма–Штейнера в конкретном случае (который был впервые предложен А. М. Тропиным в [16] и подробно разобран в работе [7]), получив при этом более простое и прозрачное рассуждение. Мы полагаем здесь $A_i=\{a_i,b_i\}\in \mathscr{H}(\mathbb R^2)$ (рис. 6) и $\widetilde{A}=\bigsqcup_i A_i$. Напомним, что через $S(A)$ мы обозначили минимальное значение функции $S_A$. Нам потребуются следующие леммы. Доказательство. Действительно, пусть $O$ – центр окружности. Тогда $d_H(A,\{O\})=1$, поэтому $S_A(\{O\})=3$ и, значит, $S(A)\leqslant 3$. Лемма 8. Пусть $d\in\Omega(A)$. Если $B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3) \neq \varnothing$ или $B_{d_1}(b_1)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3) \neq \varnothing$, то $S(A) = 3$. Доказательство. Рассмотрим первый случай, второй разбирается точно так же. Вершины $a_1$, $a_2$ и $a_3$ образуют правильный треугольник, точка Торричелли $t$ которого совпадает с центром описанной около него окружности, и $|a_1t|+|a_2t|+|a_3t|=3$. Пусть $x\in B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3)$. Тогда $|a_ix|\leqslant d_i$, $i=1,\,2,\,3$, поэтому
$$
\begin{equation*}
S(A)=d_1+d_2+d_3\geqslant |a_1x|+|a_2x|+|a_3x|\geqslant |a_1t|+|a_2t|+|a_3t|=3.
\end{equation*}
\notag
$$
С другой стороны, $S(A)\leqslant 3$ по лемме 7, значит, $S(A)=3$.
Лемма доказана. Доказательство. Пусть $\# K_\lambda = 1$. Обозначим единственную точку минимального компакта через $x$. Согласно теореме 3 имеем $x\in B_{d_i}(a_i)$ для всех $i$. Следовательно, $B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3) \neq \varnothing$. Осталось применить лемму 8. Согласно оценке из теоремы 6 в рассматриваемом случае $\#A_i=2$, $n=3$, поэтому $\# K_\lambda\leqslant \# \widetilde{A}-n=3$. Предположим, что оценка достигается, т.е. $\# K_\lambda= 3$. Доказательство. Рассмотрим каноническое отношение $R(K_\lambda)$. Так как $K_\lambda$ – минимальный компакт Штейнера, то $R(K_\lambda)$ по теореме 4 является соответствием, удовлетворяющим условиям 1. Обозначим через $\mathfrak{R}$ множество всех соответствий $R$ между $K_\lambda$ и $\widetilde{A}$, которые удовлетворяют условию 1.
Пусть $R\in\mathfrak{R}$ и $G_R$ – двудольный граф этого соответствия. Каждая вершина из $K_\lambda$ смежна с вершинами из каждого $A_i$, поэтому в каждое множество $A_i$ приходит не менее трех ребер графа $G_R$. Далее, каждая вершина из $K_\lambda$ смежна с вершиной степени $1$ из $\widetilde{A}$, причем две такие вершины из $\widetilde{A}$ не могут лежать в одном $A_i$, так как в этом случае в $A_i$ приходят только два ребра графа $G_R$. Поэтому каждое $A_i$ содержит одну вершину степени $1$ и одну вершину степени не меньше $2$. Обозначим через $p_i$ вершину из $K_\lambda$, смежную с вершиной степени $1$ из $A_i$. Граф $G_R$ должен содержать девять ребер, показанных на рис. 7 сплошными линиями, и может также содержать некоторые из трех ребер, показанных рис. 7 пунктиром. В частности, граф любого соответствия $R\in\mathfrak{R}$ содержит подграф $G$, состоящий из девяти ребер, показанных на рис. 7 сплошными линиями, и определенный с точностью до того, какая из точек, $a_i$ или $b_i$, является вершиной степени $1$ в каждом из $A_i$. Пусть в графе $G$ точки $b_i,a_j,a_k$ – вершины степени $1$. Тогда вершина $p_i$ смежна с вершиной $b_i$ степени $1$ и c вершинами $b_j$ и $b_k$ степени $2$. Значит,
$$
\begin{equation*}
p_i\in B_{d_1}(b_1)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3),
\end{equation*}
\notag
$$
и по лемме 8 получаем, что $S(A)=3$. Случай, когда $a_i,b_j,b_k$ – вершины степени $1$ в $G$, полностью аналогичен. Пусть теперь $a_1,a_2$ и $a_3$ – вершины степени $1$ (случай, когда $b_1,b_2$ и $b_3$ – вершины степени $1$, полностью аналогичен). На рис. 8 показан граф соответствия $R(K_\lambda)$ и его подграф $G$. Так как $(p_1,b_2)\in R(K_\lambda)$ и $(p_1,a_2)\notin R(K_\lambda)$, то точка $p_1$ лежит к $b_2$ ближе, чем к $a_2$, т.е. принадлежит открытой полуплоскости, ограниченной серединным перпендикуляром к отрезку $[a_2,b_2]$ и содержащей $b_2$. Далее, $(p_1,b_3)\in R(K_\lambda)$ и $(p_1,a_3)\notin R(K_\lambda)$, поэтому точка $p_1$ лежит строго внутри угла $\Upsilon_1$ между серединными перпендикулярами к отрезкам $[a_3,b_3]$ и $[a_2,b_2]$, содержащего точку $b_2$. Аналогично устанавливаем, что $p_2$ лежит строго внутри угла $\Upsilon_2$ между серединными перпендикулярами к отрезкам $[a_1,b_1]$ и $[a_3,b_3]$, содержащего точку $b_3$, а также $p_3$ находится строго внутри угла $\Upsilon_3$ между серединными перпендикулярами к отрезкам $[a_1,b_1]$ и $[a_2,b_2]$, содержащего точку $b_1$. Изобразим данные сектора и закрасим их области для удобства внутри единичного круга (рис. 9). Рассмотрим точку $p_1$, лежащую внутри угла $\Upsilon_1$. Так как $(p_1, b_3)\in R(K_\lambda)$, то $p_1\,{\in}\, B_{d_3}(b_3)$. Но расстояние от $b_3$ до угла $\Upsilon_1$ достигается в точке $O$ и равно $1$, поэтому $d_3 > 1$. Аналогично, $d_1 > 1$ и $d_2 > 1$. Таким образом, $S(A) = d_1+d_2+d_3>3$, что противоречит лемме 8. Таким образом, этот случай не реализуется. Утверждение 14 доказано. Следующая лемма получается прямым перебором. Лемма 9. Вписанные в окружность треугольники такие, что их вершины лежат в трех разных граничных компактах $A_i$, могут быть лишь двух видов: правильные треугольники и прямоугольные, гипотенуза которых – диаметр окружности. Определение 5. Пусть $p\in K\in \Sigma_d(A)$. Если $|a_j^ip|\leqslant d_i$, то будем говорить, что $p$ соединяется с точкой $a_j^i$. Отметим, что последнее равносильно тому, что $p$ находится с $a_j^i$ в каноническом отношении $R(K)$. Поэтому в дальнейшем эти термины используются как синонимы. Лемма 10. Если для любого $i$ есть точка в $K_\lambda$, соединяющаяся с $b_i$ и с диаметрально противоположной ей $a_j$, то $S(A) = 3$. Доказательство. Согласно условию есть точка $p\in K_\lambda$, соединяющаяся с $a_1$ и с $b_3$, следовательно, $d_1+d_3\geqslant |a_1p|+|pb_3|\geqslant2$. Аналогично, есть точка, соединяющаяся с $a_2$ и с $b_1$, и есть точка, соединяющаяся с $a_3$ и с $b_2$, откуда $d_1\,{+}\,d_2\geqslant 2$ и $d_2+d_3\geqslant 2$ соответственно. Поэтому $2d_1 +2d_2 +2d_3 \geqslant 6$. Следовательно, $S(A)=d_1 + d_2 + d_3 \geqslant 3$, но $S(A)\leqslant 3$ по лемме 7, значит, $S(A)=3$. Лемма 11. Если существует по крайней мере два граничных компакта, все точки которых соединяются с некоторой точкой из $K_\lambda$, то $S(A) = 3$. Доказательство. Допустим противное: точка $p$ из минимального компакта соединяется с точками $a_i,b_i,a_j,b_j$. Но $p$ должна соединяться хотя бы с одной точкой из $A_k$. Следовательно, из вершин, с которыми соединяется данная точка, можно выделить вершины правильного треугольника. Это означает, что или $B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3) \neq \varnothing$, или $B_{d_1}(b_1)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3) \neq \varnothing$, и $S(A)=3$ по лемме 8. Теорема 11. В сделанных предположениях: Доказательство. Напомним, что из теоремы 6 мы уже получили оценку $\# K_\lambda\leqslant3$. Если $\# K_\lambda =1$ или $\# K_\lambda = 3$, то по следствию 7 и утверждению 14 имеем $S(A) = 3$. Осталось рассмотреть случай $\# K_\lambda =2$.
Пусть $K_\lambda = \{x, y\}$. Рассмотрим каноническое отношение $R=R(K_\lambda)$. Так как $K_\lambda$ – минимальный компакт Штейнера, то по теореме 4 отношение $R$ является соответствием, удовлетворяющим условию 1. В частности, каждая точка из $K_\lambda$ состоит в отношении $R$ (или, что то же самое, соединена) по крайней мере с одной точкой из каждого граничного компакта. Согласно лемме 9 три такие точки из разных $A_i$ являются либо вершинами правильного треугольника, либо вершинами прямоугольного треугольника. Если хотя бы один треугольник оказался правильным, то согласно лемме 8 получаем, что $S(A)= 3$. Пусть теперь все треугольники, образованные точками из трех попарно различных компактов, соединенные с одной и той же точкой из $K_\lambda$, прямоугольные. Гипотенузы этих треугольников – диаметры окружности. Следовательно, у каждой точки из $K_\lambda$ найдется пара диаметрально противоположных точек из граничных компактов, с которыми она соединяется. Далее каждую такую пару будем называть диаметром этой точки. Отметим, что пар диаметрально противоположных точек из $\widetilde{A}$ всего три. Если у всех точек $K_\lambda$ в совокупности имеется три различных диаметра, то по лемме 10 получим $S(A)= 3$. Предположим теперь, что диаметров не больше двух. Допустим сначала, что у точек $x$ и $y$ имеется общий диаметр. Покажем, что в этом случае также $S(A)= 3$. Не ограничивая общности, считаем, что $(a_1,b_3)$ – общий диаметр точек $x$ и $y$. Хотя бы одна из точек $x$ и $y$ должна соединяться с $b_1$. Для определенности пусть это точка $x$. Если $x$ соединяется и с $b_2$, то получим, что $x$ соединяется с точками $b_1$, $b_2$ и $b_3$, т.е. $S(A)= 3$ по лемме 8. Иначе точка $x$ соединяется с $a_2$ (напомним, что каждая точка из $K_\lambda$ соединяется с каждым компактом $A_i$). Тогда у точки $x$ есть еще диаметр $(b_1,a_2)$. Итак, точка $x$ соединена с $a_1,b_3,b_1,a_2$. Если $x$ соединяется еще и с $a_3$, то $x$ соединяется с $a_1$, $a_2$ и $a_3$, и тогда снова $S(A)= 3$ по лемме 8. Остается рассмотреть случай, когда $x$ не соединяется ни с $b_2$, ни с $a_3$. Тогда с ними должна соединяться точка $y$. Но в таком случае у точки $y$ есть диаметр $(b_2,a_3)$, и в совокупности получаем три диаметра, что противоречит нашему предположению. Итак, осталось рассмотреть случай, когда каждая из точек $x$, $y$ имеет ровно один диаметр, и эти диаметры разные. Заметим, что любые два диаметра содержат две точки из одного граничного компакта, и две точки из двух других. Не ограничивая общности, считаем, что $(a_1,b_3)$ – диаметр точки $x$ и $(b_1,a_2)$ – диаметр точки $y$ (рис. 10). Тогда $d_1\,{+}\,d_3\,{\geqslant}\, 2$ и $d_1\,{+}\,d_2\,{\geqslant}\, 2$, откуда $d_1\,{+}\,d_2\,{+}\,d_3+d_1\geqslant 4$. С другой стороны, $S(A)=d_1+d_2+d_3\leqslant 3$ по лемме 7, поэтому $d_1\geqslant1$. Далее, так как $d_1+d_3\geqslant 2$ и $d_1+d_2+d_3\leqslant 3$, то $d_2\leqslant1$. Аналогично, так как $d_1+d_2\geqslant 2$ и $d_1+d_2+d_3\leqslant 3$, то $d_3\leqslant1$. Заметим, что если одновременно два расстояния $d_2$ и $d_3$ равны $1$, то (так как $d_1\geqslant1$) имеем $d_1+d_2+d_3\geqslant 3$, следовательно, в этом случае $S(A)=3$. Поэтому далее будем предполагать, что по крайней мере одно из расстояний $d_2$ и $d_3$ строго меньше $1$. Если точка $x$ не соединяется с $a_2$, то $x$ лежит к $b_2$ ближе, чем к $a_2$, т.е. строго внутри полуплоскости, ограниченной серединным перпендикуляром к отрезку $[a_2,b_2]$ (рис. 11). Но тогда $d_3>1$, так как $x$ соединяется с $b_3$, противоречие. Таким образом, $x$ соединяется с $a_2$. Аналогично показывается, что $y$ соединяется с $b_3$. Далее, по лемме 8 точка $y$ не соединяется с $b_2$, а точка $x$ не соединяется с $a_3$ (иначе $S(A)=3$). Тогда $b_2$ соединяется с $x$, а $a_3$ соединяется c $y$. По лемме 11, если $x$ или $y$ соединена еще хотя бы с одной точкой из $A$, то имеем $S(A)=3$. Поэтому в дальнейшем предполагаем, что точка $x$ не соединяется с $b_1$ и $a_3$, а точка $y$ не соединяется с $b_2$ и $a_1$. Итак, точка $x$ соединена с точками $a_1,a_2,b_2$ и $b_3$ и не соединена с двумя оставшимися, поэтому она содержится во множестве
$$
\begin{equation*}
I_x=\bigl(B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3)\bigr)\setminus B_{d_1}(b_1)\setminus B_{d_3}(a_3)
\end{equation*}
\notag
$$
(рис. 12). Так как $B_{d_2}(b_2)\cap B_{d_3}(a_3)=\varnothing$, то
$$
\begin{equation*}
I_x=\bigl(B_{d_1}(a_1)\cap B_{d_2}(a_2)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3)\bigr)\setminus B_{d_1}(b_1).
\end{equation*}
\notag
$$
Аналогично определяется множество
$$
\begin{equation*}
I_y=\bigl(B_{d_1}(b_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3)\cap B_{d_3}(b_3)\bigr)\setminus B_{d_1}(a_1),
\end{equation*}
\notag
$$
в котором расположена точка $y$. Так как $d_1\geqslant1$, то центр $O$ окружности лежит в $B_{d_1}(b_1)$ и, значит, не лежит в $I_x$. Поэтому $I_x\,{\subset}\, B_3(b_3)$ лежит в открытой полуплоскости, ограниченной серединным перпендикуляром к отрезку $[a_2,b_2]$ и содержащей $a_2$, откуда получаем $|a_2x|<|b_2x|\leqslant d_2$. Таким образом,
$$
\begin{equation*}
I_x=\bigl(B_{d_1}(a_1)\cap B_{d_2}(b_2)\cap B_{d_3}(b_3)\bigr)\setminus B_{d_1}(b_1).
\end{equation*}
\notag
$$
Аналогично, для $y$
$$
\begin{equation*}
I_y=\bigl(B_{d_1}(b_1)\cap B_{d_2}(a_2)\cap B_{d_3}(a_3)\bigr)\setminus B_{d_1}(a_1).
\end{equation*}
\notag
$$
Теорема 11 доказана. Лемма 12. Точки $x$ и $y$ не являются точками Ферма–Штейнера для вершин треугольников $a_1b_2b_3$ и $b_1a_2a_3$ соответственно. Доказательство. Для $x$ и $y$ справедливы неравенства Но в силу того, что треугольник $a_1a_2b_3$ равен $a_1b_2b_3$, а $b_1a_2b_3$ равен $b_1a_2a_3$, если $x$ – точка Ферма–Штейнера для вершин $a_1b_2b_3$ и $y$ – точка Ферма–Штейнера для вершин $b_1a_2a_3$, справедливы неравенства противоречие.
Лемма доказана. Лемма 13. На каждой точке минимального компакта $K_\lambda=\{x,y\}$ реализуются все три расстояния $d_1,d_2,d_3$. Доказательство. Как было показано выше, $x\,{\in}\, U_{d_2}(a_2)$ и $y\,{\in}\, U_{d_3}(b_3)$, поэтому $\#L_i(x)\leqslant1$ и $\#L_i(y)\leqslant1$ при всех $i$.
Пусть $\#L(y)=0$. Тогда $\#L(x)=3$ и $y\notin \operatorname{Conv} L(y)=\varnothing$. Точка $x$ не является точкой Ферма–Штейнера для $L(x)$ согласно лемме 12, поэтому $K_\lambda\notin \sum_d(A)$ по теореме 10. Пусть $\#L(y)=1$. Тогда $L(x)$ не может состоять меньше чем из двух точек по лемме 5 и не может состоять из двух точек по следствию 6 и той же лемме 5. Также $L(x)$ не может состоять из трех точек по тем же причинам, что и в случае $\#L(y)=0$. Аналогично для $L(x)$, поэтому $\#L(x)\geqslant 2$ и $\#L(y)\geqslant 2$. Пусть $\#L(y)=2$. Тогда $\operatorname{Conv} L(y)$ – это хорда окружности, и $\operatorname{Conv} L(y)$ – это все точки Ферма–Штейнера для $L(y)$. Отметим, что $[b_2,b_3]$ – единственная хорда, проходящая через $I_x$, с концами которой соединяется точка $x$, а $[a_2,a_3]$ – единственная хорда, проходящая через $I_y$, с концами которой соединяется $y$. Если $y\notin \operatorname{Conv} L(y)$, то $x$ – точка Ферма–Штейнера для $L(x)$, иначе $K_\lambda\notin \sum_d(A)$ по теореме 10. Тогда $\#L(x)=2$ в силу леммы 12. Поэтому $B_{d_2}(b_2)\cap B_{d_3}(b_3)=\{x\}$, т.е. на $x$ реализованы только $d_2$ и $d_3$. Тогда $d_1$ реализуется на $y$ по лемме 5. Ввиду того, что $\#L(y)=2$ и $y\notin \operatorname{Conv} L(y)$, справедливо
$$
\begin{equation*}
U_{d_1}(b_1)\cap U_{d_2}(a_2)\cap U_{d_3}(a_3)\neq \varnothing.
\end{equation*}
\notag
$$
Возьмем точку $y'$ из этого пересечения. Имеем: $K=\{x,y'\}$ – конечное подмножество $K_d$; $B_{d_i}(a_i)\cap K\neq \varnothing$ и $B_{d_i}(b_i)\cap K\neq \varnothing$; $K\cap B_{d_2}(b_2) = \{x\}$ и $K\cap B_{d_3}(a_3) = \{y'\}$. Поэтому $K$ – минимальный компакт Штейнера согласно теореме 3. Замечаем, что ни на одной точке $K$ не реализовано $d_1$, противоречие с леммой 5.
Если $y\in [a_2,a_3]$, то $B_{d_2}(a_2)\cap B_{d_3}(a_3)=\{y\}$. Тогда Значит, $d_1$ реализуется на $x$ по лемме 5, так как $\#L(y)=2$. Поэтому $|b_1y|<d_1$. Рассмотрим точку $x'$ на отрезке $[b_2,b_3]$, которая ближе к $b_2$ относительно $x$. Пусть $d'_1$, $d'_2$ и $d'_3$ – расстояния от $x'$ до $a_1$, $b_2$ и $b_3$ соответственно. Ясно, что $d_1>d'_1$ и $d_2+d_3=d'_2+d'_3$. Положим $B_{d'_2}(a_2)\cap B_{d'_3}(a_3)=\{y'\}$. Заметим, что можно считать точку $x'$ выбранной так, что $|b_1y'|\leqslant d'_1$. Положим $K'=\{x',y'\}$. Тогда
$$
\begin{equation*}
d_H(K',A_2)+d_H(K',A_3)\leqslant d'_2+d'_3=d_2+d_3, \qquad d_H(K',A_1)\leqslant d'_1<d_1.
\end{equation*}
\notag
$$
Поэтому $S_A(K')<S_A(K_\lambda)=S(A)$, противоречие.
Аналогично для $L(x)$, поэтому $\#L(x)= 3$ и $\#L(y)= 3$. Лемма доказана. Следовательно, $x\,{\in}\,\operatorname{Conv} L(x)$ и $y\,{\in}\,\operatorname{Conv} L(y)$, иначе $\{x,y\}$ не является компактом Штейнера по теореме 10. Пусть $d_2<d_3$. Рассмотрим треугольники $b_2xb_3$ и $a_2ya_3$. Тогда $|a_1x|\,{<}\,|b_1y|$ (рис. 13). Но $d_1\,{=}\,|a_1x|\,{=}\,|b_1y|$, противоречие. Аналогично, если $d_3\,{<}\,d_2$. Значит, $d_2=d_3$. Мы имеем следующую ситуацию (рис. 14). Точка $x$ лежит на серединном перпендикуляре $s$ к отрезку $[b_2,b_3]$, а точки $x$ и $y$ симметричны относительно диаметра, являющегося серединным перпендикуляром к отрезку $[a_1,b_1]$. Точка $x$ минимального компакта должна располагаться на $s$ так, чтобы сумма расстояний $|a_1x|+|b_2x|+|b_3x|$ была минимальна. Положим $|Ox|=t$. Тогда по теореме косинусов Отметим, что $t\in(0,1)$. Следовательно, На интервале $(0,1)$ эта функция имеет единственный минимум, который достигается при $t=(\sqrt{5}-\sqrt{4 \sqrt{5}-7})/4=0.210424\dots$ и равен $2.94645\ldots < 3$.Итак, при $\#K_\lambda=2$ минимальное возможное значение $S_A$ достигается на описанной только что конфигурации и меньше, чем $3$. Так как при других возможных значениях $\#K_\lambda$ минимум $S_A$ равен $3$, то построенный компакт $K_\lambda=\{x,y\}$ является абсолютным минимумом функции $S_A$, т.е. компактом Штейнера. Он, очевидно, принадлежит классу $\Sigma_d(A)$, где $d=(d_1,d_2,d_3)$. Два других минимальных компакта получаются поворотами на $2\pi/3$ (конкретный компакт был выбран нами при выборе диаметра точки $x$). Теорема 11 доказана.
Цитирование в формате AMSBIB
\RBibitem{GalIvaTuz21} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|