| Математический сборник |
|
|
|
|
|
Плоские локально минимальные деревья с границей на окружности И. Н. Михайлов Механико-математический факультет, Московский государственный университет имени М. В. Ломоносова
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 5, Pages DOI: https://doi.org/10.4213/sm10002e 
Реферативные базы данных:
     § 1. ВведениеИзвестная проблема Штейнера заключается в том, что необходимо найти кратчайшую сеть, связывающую конечное множество точек, называемых граничными, в некотором объемлющем метрическом пространстве. Эта задача интересна прежде всего своими многочисленными приложениями, в частности, в случае обычной евклидовой плоскости у нее есть естественная транспортная интерпретация. Локальная структура кратчайших сетей известна во многих классах метрических пространств. Например, на произвольном римановом многообразии (см. [1], [2]) ребра таких сетей являются геодезическими и сходятся в вершинах под углами не меньше чем $2\pi/3$. В частности, степени всех вершин не превосходят $3$. Также без ограничения общности можно считать, что такие сети не содержат неграничных вершин степени $2$, так как геодезические в них сходятся под углом $\pi$ и такие точки можно исключить из множества вершин, склеивая входящие в них геодезические в одну, что оставит сеть кратчайшей и не изменит ее как подмножество многообразия. Более того, разрезая произвольное кратчайшее дерево по граничным вершинам степеней, больших $1$, можно свести изучение проблемы Штейнера на римановых многообразиях к рассмотрению полных сетей Штейнера, т.е. тех сетей, у которых множество граничных вершин совпадает с множеством вершин степени $1$, а все неграничные вершины имеют степень $3$. Задача построения кратчайшей сети, затягивающей данное множество точек, даже в дискретном случае, когда делается предположение о том, что все точки граничного множества и строящейся сети имеют целые координаты, $\mathrm{NP}$-трудна (см. [3]) и допускает полиномиальный алгоритм решения только при известной топологии сети. Таким образом, задача описания всех кратчайших сетей, затягивающих данное множество точек, в общем случае оказывается очень сложной. Естественным расширением класса кратчайших сетей является класс локально кратчайших сетей, являющихся кратчайшими в окрестности каждой своей точки. Тем самым это в точности те сети, у которых локальная структура такая же, как и у кратчайших сетей. В случае обычной евклидовой плоскости локально кратчайшими сетями будут являться всевозможные плоские графы, у которых неграничные вершины имеют степень $3$, граничные – не больше $3$, а ребра являются отрезками и сходятся в вершинах под углами не меньше чем $2\pi/3$ (см. [4], [5]). В работах А. О. Иванова и А. А. Тужилина (см. [1], [2]) было дано полное описание плоских деревьев Штейнера, имеющих выпуклую локально минимальную реализацию, т.е. плоских деревьев, планарно эквивалентных некоторому полному дереву Штейнера, затягивающему вершины выпуклого многоугольника. Помимо деревьев с выпуклыми границами, в работах А. О. Иванова и А. А. Тужилина изучались также деревья с правильными (см. [6]–[8]) и квазиправильными (см. [9]) границами, граничные вершины которых лежат в вершинах правильного многоугольника и на последовательных дугах окружности, описанной около правильного многоугольника соответственно. В настоящей работе рассматриваются плоские деревья, имеющие круглую минимальную реализацию, а именно планарно эквивалентные некоторому полному дереву Штейнера, затягивающему вершины выпуклого вписанного многоугольника. Приведен широкий класс деревьев, имеющих выпуклую минимальную реализацию, но не имеющих круглой минимальной реализации. БлагодарностиАвтор благодарит научного руководителя А. А. Тужилина за постановку задачи и постоянное внимание к работе, а также А. В. Бегунца и С. В. Шапошникова за привлечение к научной работе и помощь в поиске подходящей темы. § 2. Основные определения и предварительные результатыПриведем основные определения и утверждения; подробности см. в [1], [2]. Плоский граф называется плоским деревом, если соответствующий ему комбинаторный граф является деревом. Отметим, что при изучении вариационных задач у каждого дерева выделено конечное подможество вершин, называемых граничными, причем остальные вершины называются внутренними. Ребра, инцидентные хотя бы одной граничной вершине, будем также называть граничными. Полное дерево Штейнера – это плоское дерево, у которого степени всех вершин равны $1$ или $3$, причем вершины степени $1$ образуют множество граничных вершин, а ребра являются отрезками. Будем называть полное дерево Штейнера локально минимальным, если во всех его вершинах степени $3$ ребра сходятся под углами $2\pi/3$. Будем говорить, что полное дерево Штейнера имеет выпуклую локально минимальную реализацию, если существует планарно эквивалентное ему локально минимальное полное дерево Штейнера, у которого все граничные вершины лежат в вершинах некоторого выпуклого многоугольника. Будем говорить, что полное дерево Штейнера имеет круглую минимальную реализацию, если оно имеет выпуклую локально минимальную реализацию, в которой граничные вершины лежат на некоторой окружности. Путь $\gamma$ в плоском дереве $G$ назовем ориентированным, если на его вершинах фиксирован один из двух естественных порядков. Аналогично определим ориентированные ломаные. Отметим, что ребра ориентированной ломаной можно рассматривать как обычные векторы на плоскости. Через $(e_1, e_2)$ будем обозначать последовательность ребер единственного ориентированного пути в полном дереве Штейнера $G$, первое ребро которого совпадает с $e_1$, а последнее с $e_2$. Иногда нам будет удобно рассматривать ребро $e$ из $(e_1, e_2)$ как неориентированное ребро исходного графа, в таком случае это будет ясно из контекста. По аналогии через $(v_1, v_2)$ будем обозначать последовательность вершин единственного ориентированного пути в полном дереве Штейнера $G$, первая и последняя вершины которого – это $v_1$ и $v_2$ соответственно. Зафиксируем на плоскости стандартную ориентацию. Рассмотрим произвольный ориентированный путь $\gamma$ в полном дереве Штейнера $G$. Каждой паре двух последовательных ребер $e_1$, $e_2$ этого пути сопоставим число $+1$, если базис из $e_1$ и $e_2$ положительно ориентирован, и сопоставим число $-1$ в противном случае. Сумму таких чисел по всем парам последовательных ребер пути $\gamma$ назовем числом вращения $\gamma$ и будем обозначать через $\operatorname{tw}(\gamma)$ (и соответственно $\operatorname{tw}(e_1, e_2)$, $\operatorname{tw}(v_1, v_2)$, если первое и последнее ребра пути $\gamma$ – это $e_1$ и $e_2$ или первая и последняя вершины $\gamma$ – это $v_1$ и $v_2$ соответственно). Максимум чисел вращения $\operatorname{tw}(\gamma)$ по всем ориентированным путям $\gamma$ в $G$ будем называть числом вращения $G$ и обозначать через $\operatorname{tw}(G)$. Рассмотрим произвольную ориентированную ломаную $X_1X_2\dots X_n$. Углом $\angle (X_iX_{i+1}, X_{i+1}X_{i+2})$ между последовательными ребрами $X_iX_{i+1}$, $X_{i+1}X_{i+2}$ этой ломаной будем называть угол между векторами $\overrightarrow{X_iX_{i+1}}$, $\overrightarrow{X_{i+1}X_{i+2}}$, взятый со знаком плюс, если $\operatorname{tw}(X_iX_{i+1}, X_{i+1}X_{i+2})=1$, и со знаком минус в противном случае. Угол поворота $\operatorname{rot}(X_1X_2\dots X_n)$ вдоль ломаной $X_1X_2\dots X_n$ определим как сумму $\sum_{i=1}^{n-2}\angle (X_iX_{i+1},\,X_{i+1}X_{i+2})$. Отметим, что в том случае, когда $G$ – локально минимальное полное дерево Штейнера, угол между любыми двумя последовательными ребрами произвольного ориентированного пути $\gamma$ равен $\pm\pi/3$, т.е. выполнено равенство $\operatorname{tw}(\gamma)= \operatorname{rot}(\gamma)/(\pi/3)$. Отметим два элементарных свойства числа вращения:
Приведем теперь два ключевых, хорошо известных предложения о полных локально минимальных деревьях. Предложение 1. Если все вершины степени $1$ у полного локально минимального дерева Штейнера $G$ лежат на границе выпуклого многоугольника, то число вращения $G$ не превосходит $5$. Предложение 2. Каждое полное локально минимальное дерево Штейнера лежит в выпуклой оболочке множества своих граничных вершин. Также имеют место следующие два несложных утверждения, которыми мы будем пользоваться в дальнейшем. Утверждение 1. Если $G$ – полное дерево Штейнера и $\operatorname{tw}(G) \leqslant k$, а также ребра $e$ и $f$ этого дерева таковы, что $\operatorname{tw}(e, f)=k$, то ребра $e$ и $f$ граничные. Утверждение 2. Пусть в полном дереве Штейнера с числом вращения $\operatorname{tw}(G)=5$ выполнено $\operatorname{tw}(e, e')=(-1)^k\,5$, где $k\in\mathbb{Z}$, $f$ и $f'$ – второе и предпоследнее ребра последовательности $(e, e')$, а $g$ и $g'$ – ребра, смежные с парами ребер $e$, $f$ и $e'$, $f'$ соответственно и не совпадающие с ними. Тогда $ \operatorname{tw}(e, f)=\operatorname{tw}(g', f')=\operatorname{tw}(e', g')=(-1)^k$, а также $\operatorname{tw}(e', f')=\operatorname{tw}(g, f)=\operatorname{tw}(e, g)= (-1)^{k+1}$. И наконец, мы будем пользоваться следующим хорошо известным фактом. Утверждение 3. Полный угол поворота вдоль замкнутой несамопересекающейся ломаной равен $\pm2\pi$ в зависимости от направления ее обхода. § 3. Основной результатТеперь сформулируем и докажем наш основной результат. Теорема. Предположим, что в полном дереве Штейнера $G$ найдется путь $\gamma=v_1 e_1 \dots v_2 \dots v_3 \dots e_4 v_4$, где $v_1$, $v_2$, $v_3$, $v_4$ – различные вершины $G$, а $e_1$, $e_4$ – некоторые ребра $G$. Обозначим через $e_2$ и $e_3$ ребра дерева $G$, инцидентные $v_2$ и $v_3$ соответственно и не принадлежащие $\gamma$. Предположим, что: Тогда дерево $G$ не имеет круглой минимальной реализации. Доказательство. Предположим, что у дерева $G$, удовлетворяющего условию теоремы, существует круглая минимальная реализация, и для удобства будем считать, что $G$ совпадает с этой минимальной реализацией.
Поскольку круглая минимальная реализация является выпуклой, из предложения 1 и утверждения 1 немедленно следует, что все ребра $e_1$, $e_2$, $e_3$, $e_4$ граничные в $G$. Доказательство. Предположим противное. Пусть тогда $f$ – предпоследнее ребро последовательности $(e_1, e_2)$, а $f'$ – второе ребро последовательности $(e_2, e_3)$. Поскольку мы предположили, что $\operatorname{tw}(e_1, e_2)=-5$, то $\operatorname{tw}(f, e_2)=-1$ по утверждению 2, а значит, $\operatorname{tw}(e_2, f)=-\operatorname{tw}(f, e_2)=1$. Но в силу предположения (2) теоремы $\operatorname{tw}(e_2, f')\geqslant 0$, т.е. $\operatorname{tw}(e_2, f')=1$, поскольку эти два ребра смежны. Значит, $\operatorname{tw}(e_2, f')=\operatorname{tw}(e_2, f)=1$, откуда следует, что $f$ совпадает с $f'$, а это противоречит тому, что $f'$, $f$ – последовательные ребра пути $\gamma$.
Лемма доказана. Доказательство. Предположим, что это не так и $\operatorname{tw}(e_3, e_4)=5$ (рис. 1). Пусть $f$ – предпоследнее ребро последовательности $(e_1, e_2)$, $f'$ – второе ребро последовательности $(e_2, e_3)$, $e$ – предпоследнее ребро последовательности $(e_2, e_3)$, а $e'$ – второе ребро последовательности $(e_3, e_4)$.
Из утверждения 2 следуют равенства
$$
\begin{equation*}
\begin{gathered} \, \operatorname{tw}(f, e_2)=1, \qquad \operatorname{tw}(f, f')=-1, \qquad \operatorname{tw}(e_2, f')=1, \\ \operatorname{tw}(e_3, e')= 1, \qquad \operatorname{tw}(e, e')=-1, \qquad \operatorname{tw}(e_3, e)=-1. \end{gathered}
\end{equation*}
\notag
$$
Также
$$
\begin{equation*}
\operatorname{tw}(f', e)=\operatorname{tw}(e_2, e)-\operatorname{tw}(e_2, f')= \operatorname{tw}(e_2, e)-1\geqslant 0-1=-1.
\end{equation*}
\notag
$$
Причем если выполнено равенство $\operatorname{tw}(f', e)=-1$, то
$$
\begin{equation*}
\operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, f')+\operatorname{tw}(f', e)+\operatorname{tw}(e, e_3)=1-1+1=1,
\end{equation*}
\notag
$$
что противоречит предположению теоремы. Значит, $\operatorname{tw}(f', e)\geqslant 0$. Но тогда
$$
\begin{equation*}
\begin{aligned} \, \operatorname{tw}(e_1, e_4) &=\operatorname{tw}(e_1, f)+\operatorname{tw}(f, f')+ \operatorname{tw}(f', e)+\operatorname{tw}(e, e')+\operatorname{tw}(e', e_4) \\ &=4-1+ \operatorname{tw}(f', e)-1+4=6+\operatorname{tw}(f', e) \geqslant 6, \end{aligned}
\end{equation*}
\notag
$$
что по предложению 1 противоречит выпуклости рассматриваемой реализации. Лемма доказана. Лемма 3. Для любого ребра последовательности $(e_2, e_3)$, за исключением $e_3$, выполнены неравенства $2 \geqslant \operatorname{tw}(e_2, e) \geqslant 0$. Доказательство. Второе неравенство выполнено по предположению теоремы. Докажем первое. Предположим, что найдется ребро $h$ последовательности $(e_2, e_3)$, не совпадающее с $e_3$ и такое, что $\operatorname{tw}(e_2, h)=3$. Тогда $h$ не является граничным, а значит, для одного из смежных с ним ребер $g$ выполнено равенство $\operatorname{tw}(e_2, g)=4$. Но тогда $\operatorname{tw}(e_1, g)=6$, что по предложению 1 противоречит выпуклости рассматриваемой реализации.
Лемма доказана. Доказательство. Из леммы 3 следует, что $\operatorname{tw}(e_2, e_3) \in \{-1, 0, 1, 2, 3\}$. Из предположения (2) теоремы следует, что $\operatorname{tw}(e_2, e_3) \neq 1$ и $\operatorname{tw}(e_2, e_3)\neq -1$.
Пусть $e'$ – второе ребро последовательности $(e_3, e_4)$, а $e$ – предпоследнее ребро последовательности $(e_2, e_3)$. Поскольку $\operatorname{tw}(e_3, e_4)=-5$, то тогда по утверждению 2 верно равенство $\operatorname{tw}(e_3, e)=1$. Но тогда, используя оценку $\operatorname{tw}(e_2, e)\leqslant 2$ из леммы 3, получаем
$$
\begin{equation*}
\operatorname{tw}(e_2, e_3)=\operatorname{tw}(e_2, e)+\operatorname{tw}(e, e_3)= \operatorname{tw}(e_2, e)-1 \leqslant 2-1=1.
\end{equation*}
\notag
$$
Значит, $\operatorname{tw}(e_2, e_3)$ равно $0$.
Лемма доказана. Лемма 5. Пусть $P_1P_2\dots P_n$ – выпуклый многоугольник. Тогда все углы между последовательными ребрами ломаной $P_1P_2\dots P_nP_1P_2$ одного знака. Доказательство. Без ограничения общности предположим, что угол между $P_1P_2$ и $P_2P_3$ положительный, а между $P_2P_3$ и $P_3P_4$ отрицательный. Заметим, что в таком случае $P_4$ и $P_1$ лежат по разные стороны от прямой $P_2P_3$. Получаем противоречие с тем, что многоугольник $P_1P_2\dots P_k$ выпуклый.
Лемма доказана. Лемма 6. Пусть $B$ – произвольный круг на плоскости, $\partial B$ – граница круга $B$, $X_1X_2\dots X_n$ – несамопересекающаяся ломаная $\gamma$, лежащая в $B$, такая, что $\gamma\cap\partial B=\{X_1, X_n\}$, причем $\operatorname{rot}(\gamma)= 5\pi/3$. Тогда лучи $X_2X_1$ и $X_{n-1}X_n$ пересекаются вне $B$ под углом $2\pi/3$. Доказательство. Докажем, что в дуги $X_1X_n$ окружности $\partial B$ можно вписать такие ломаные $X_nP_1P_2\dots P_kX_1$ и $X_nQ_1Q_2\dots Q_lX_1$, что каждая из них пересекается с ломаной $\gamma$ лишь по вершинам $X_1$ и $X_n$.
Для подмножеств $A$ и $B$ метрического пространства через $\rho(A,B)$ обозначим инфимум расстояний между произвольными точками $a\in A$, $b\in B$, т.е. $\rho(A,B)= \inf\{|ab|\colon a\in A,\,b\in B\}$. Построим круги с центрами в точках $X_1$, $X_n$ радиусов, меньших соответственно $\rho(X_1, \gamma\setminus[X_1X_2))$ и $\rho(X_n, \gamma\setminus[X_nX_{n-1}))$. Выберем точки $Q'$, $P'$ и $Q_1$, $P_1$ так, чтобы они лежали в первом и втором кругах соответственно и лежали на $\partial B$ в том порядке, в котором должны лежать на $\partial B$ вершины $Q_k$, $P_l$, $Q_1$, $P_1$ ломаных, которые мы строим. После этого достаточно лишь вписать в дуги $\smallsmile\! P_1P'$ и $\smallsmile\! Q_1Q'$ ломаные с концами в вершинах этих дуг так, чтобы они не пересекались с ломаной $\gamma$. Построим такую ломаную для дуги $\smallsmile\! P_1P'$. Поскольку $\smallsmile\! P_1P'$ и $\gamma$ – непересекающиеся компакты, то расстояние $d$ между этими множествами положительно. Разобьем дугу $\smallsmile\! P_1P'$ на дуги длины меньше $d$. Понятно, что вершины этих дуг в порядке от $P_1$ к $P'$ являются вершинами искомой ломаной. Рассмотрим многоугольники $X_1X_2\dots X_nP_1\dots P_k$ и $X_1X_2\dots X_nQ_1\dots Q_l$, ориентируя их границы в соответствии с порядком записи вершин, в которых они перечислены. Тогда из построения ломаных следует, что границы $X_1X_2\dots X_nP_1\dots P_k$ и $X_1X_2\dots X_nQ_1\dots Q_l$ имеют противоположные ориентации. В силу утверждения 3 ровно для одного из этих многоугольников полный угол поворота вдоль его границы равен $2\pi$. Без ограничения общности будем считать, что это многоугольник $X_1X_2\dots X_nP_1\dots P_k$. Обозначим углы между последовательными ребрами ориентированной ломаной $X_{n-1}X_nP_1 \dots P_kX_1X_2$ через $\alpha,\psi_1,\dots,\psi_k,\beta$ соответственно. В силу того, что $\operatorname{rot}(X_1X_2\dots X_nP_1\dots P_kX_1X_2)=2\pi$ и $\operatorname{rot}(\gamma)=5\pi/3$, верно равенство $\alpha+\psi_1+\dots+\psi_k+ \beta=\pi/3$. Применяя лемму 5 к выпуклому многоугольнику $X_nP_1\dots P_kX_1$, получаем, что все углы $\psi_1,\dots,\psi_k$ одного знака. Из построения ломаной $X_nP_1\dots P_kX_1$ следует, что $P_2$ не лежит на дуге $\smallsmile\!X_nP_1$, не содержащей $X_1$. Значит, точка $P_2$ лежит в той же полуплоскости относительно прямой $X_nP_1$, что и $X_{n-1}$. Отсюда следует, что углы $\alpha$ и $\psi_1$ одного знака. Аналогично, $\beta$ и $\psi_k$ одного знака. Таким образом, все углы $\alpha,\psi_1,\dots,\psi_k,\beta$ одного знака, а значит, в силу полученного выше равенства они неотрицательны. Подсчитаем сумму углов многоугольника $X_nP_1\dots P_kX_1$ двумя способами. С одной стороны, сумма его углов равна $\pi k$. С другой стороны, она равна
$$
\begin{equation*}
\angle X_1X_nP_1+(\pi -\psi_1)+\dots+(\pi-\psi_k)+\angle P_kX_1X_n.
\end{equation*}
\notag
$$
Значит,
$$
\begin{equation*}
\pi k=\pi k-(\psi_1+\dots+ \psi_k)+\angle X_1X_nP_1+\angle P_kX_1X_n.
\end{equation*}
\notag
$$
То есть
$$
\begin{equation*}
\angle X_1X_nP_1+\angle P_kX_1X_n= \psi_1+\dots+\psi_k.
\end{equation*}
\notag
$$
Поскольку $\alpha,\beta\geqslant 0$, выполнены равенства
$$
\begin{equation*}
\angle X_2X_1X_n=\pi-\beta-\angle P_kX_1X_n, \qquad \angle X_1X_nX_{n-1}=\pi-\alpha-\angle X_1X_nP_1.
\end{equation*}
\notag
$$
Но тогда
$$
\begin{equation*}
\begin{aligned} \, \angle X_2X_1X_n+\angle X_1X_nX_{n-1} &=(\pi-\beta-\angle P_kX_1X_n)+(\pi-\alpha-\angle X_1X_nP_1) \\ &=2\pi-(\alpha+\beta+\psi_1+\dots+\psi_k)=2\pi-\frac{\pi}{3}=\frac{5\pi}{3}, \end{aligned}
\end{equation*}
\notag
$$
откуда следует, что лучи $X_2X_1$ и $X_{n-1}X_n$ пересекаются под углом $2\pi/3$, что и требовалось доказать.
Лемма 6 доказана. Вернемся к доказательству теоремы. Пусть $B$ – круг, на границе которого лежат граничные вершины $G$, а вершины ребер $e_2$, $e_3$, не совпадающие с $v_2$, $v_3$, – это $w_2$ и $w_3$ соответственно (рис. 2). Применяя лемму 6 к ломаной $(v_1,w_2)$, получаем, что лучи, начинающиеся в $v_1$ и $w_2$, параллельные соответственно ребрам $e_1$ и $e_2$, но не содержащие их, пересекаются вне круга $B$ в некоторой точке $R$ под углом $2\pi/3$. Но тогда бо́льшая дуга, высекаемая сторонами угла $\angle v_1Rw_2$ на $\partial B$, не меньше $4\pi/3$. Аналогично, применяя лемму 6 к ломаной $(w_3,v_4)$, получаем, что лучи, начинающиеся в $w_3$ и $v_4$, параллельные соответственно ребрам $e_3$ и $e_4$, но не содержащие их, пересекаются вне круга $B$ в некоторой точке $S$ под углом $2\pi/3$, а бо́льшая дуга, высекаемая на $\partial B$ сторонами угла $\angle w_3Sv_4$, не меньше $4\pi/3$. Из леммы 4 следует, что $e_2\parallel e_3$, значит, прямые $Rv_2$ и $Sv_3$ параллельны. Пусть $f'$ – второе ребро последовательности $(e_2,e_3)$, а $w$ – вершина этого ребра, отличная от $v_2$. Поскольку $\operatorname{tw}(e_1,e_2)=5$, то $\operatorname{tw}(e_1,f')=3$. Значит, вектор $\overrightarrow{v_1R}$ сонаправлен с вектором $\overrightarrow{v_2w}$. Отсюда следует, что $w$ лежит с $v_1$ в разных полуплоскостях относительно прямой $v_2R$. Из леммы 3 следует, что все ориентированные ребра последовательности $(e_2,e_3)$ имеют такие направления, что проекция каждого из них на луч с началом на прямой $v_2R$, перпендикулярный ей, идущий в полуплоскость, в которой лежит $w$, неотрицательна. Значит, все вершины ребер последовательности $(e_2,e_3)$, за исключением $w_2$ и $v_2$, лежат с $v_1$ в разных полуплоскостях относительно прямой $v_2R$. В частности, это верно для $v_3$. Из лемм 1, 2 и 4 следует, что векторы $\overrightarrow{v_1R}$ и $\overrightarrow{Sv_4}$ сонаправлены. Поскольку $v_1$ и $v_3$ лежат в разных полуплоскостях относительно прямой $v_2R$, то продолжение луча $v_1R$ за точку $R$ пересекает прямую $Sv_3$. Но отсюда следует, что луч $Sv_4$ не пересекает прямую $v_2R$, т.е. внутренности углов $\angle v_1Rv_2$ и $\angle v_3Sv_4$ не пересекаются. Откуда следует, что дуги, высекаемые этими углами на $\partial B$, тоже не пересекаются. Но тогда длина окружности $\partial B$ не меньше суммы длин двух бо́льших дуг, высекаемых сторонами этих углов на $\partial B$, т.е. не меньше $2\cdot4\pi/3 > 2\pi$ – противоречие. Теорема доказана. Отметим, что от условия $\operatorname{tw}(e_2, e_3)\neq 1$ отказаться нельзя. Рассмотрим дерево $T$, приведенное на рис. 3. В нем выполнены равенства $\operatorname{tw}(e_1,e_2)=\operatorname{tw}(e_3,e_4)=5$ и $\operatorname{tw}(e_2,e_3)=1$. Докажем, что оно имеет круглую минимальную реализацию. Обозначим через $l_1$, $l_2$ прямые, содержащие граничные вершины $T$ так, что на $l_2$ лежит семь граничных вершин (на рис. 3 прямая $l_2$ лежит справа). Проведем окружность $\omega$, содержащую внутри себя все вершины $T$, кроме граничных вершин, лежащих на $l_2$ (штриховая линия на рис. 3). Объявим точки пересечения $\omega$ с граничными ребрами $T$ новыми граничными вершинами. Продлевая граничные ребра дерева $T$ с вершинами на $l_1$ до пересечения с $\omega$ и тоже объявляя полученные точки пересечения с $\omega$ новыми граничными вершинами, получим новое дерево $T'$, планарно эквивалентное $T$, все граничные вершины которого лежат на $\omega$. Значит, дерево $T$ действительно имеет круглую минимальную реализацию. § 4. ЗаключениеВ дальнейшем с использованием техники паркетов, развитой в работах [1], [2], [6], автор надеется получить полную классификацию деревьев, имеющих круглую минимальную реализацию. 
Цитирование в формате AMSBIB
\RBibitem{Mik24} |
|
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|