| Математические заметки |
|
|
|
|
|
О количестве наименьших доминирующих множеств в деревьях Д. С. Талецкий Национальный исследовательский университет "Высшая школа экономики" в Нижнем Новгороде
Английская версия:
Mathematical Notes, 2023, Volume 113, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434623030264 
Реферативные базы данных:
  1. ВведениеДоминирующим множеством графа называется такое подмножество его вершин $D$, что любая вершина не из $D$ смежна хотя бы с одной вершиной из $D$. Доминирующее множество называется наименьшим, если оно является наименьшим по мощности. Числом доминирования $\gamma(G)$ графа $G$ называется мощность его наименьшего доминирующего множества. Мы будем использовать сокращения “ДМ” и “НДМ” для терминов “доминирующее множество” и “наименьшее доминирующее множество” соответственно. Известно, что любой граф содержит нечетное количество ДМ [1]. В 2006 г. Брод и Скупиен в статье [2] описали деревья, содержащие максимальное и минимальное количество ДМ в классе всех $n$-вершинных деревьев. Звезда $S_n$ является единственным $n$-вершинным деревом, содержащим максимально возможное количество ДМ. Однако существует экспоненциально много $n$-вершинных деревьев, содержащих минимально возможное количество ДМ. Позднее Вагнер в работе [3] обобщил этот результат на некоторые другие классы графов. В 2022 г. в работе [4] для всех $k \geqslant 2$ была описана структура деревьев, содержащих максимальное и минимальное количество $k$-ДМ (таких подмножеств $D_k$ вершин дерева, что каждая вершина не из $D_k$ смежна хотя бы с $k$ вершинами из $D_k$). На сегодняшний день известно сравнительно мало оценок на количество НДМ в деревьях и лесах. В работе [5] даются три эквивалентных условия, при которых дерево содержит единственное НДМ. Вопрос о том, может ли дерево с числом доминирования $\gamma$ содержать более чем $2^\gamma$ НДМ, оставался открытым до 2017 г., когда в работе [6] Биен привел пример такого дерева. С другой стороны, Альварадо и др. в работе [7] доказали, что лес с числом доминирования $\gamma$ содержит не более чем $2.4606^{\gamma}$ НДМ. В настоящей работе получены новые оценки максимально возможного количества НДМ в $n$-вершинном дереве. Показано, что если максимальная степень $d$ вершин дерева не превосходит 4, то оно содержит не более чем $(\sqrt{2})^n$ НДМ. Интересно, что уже в случае $d=5$ это утверждение неверно. Для любого $n \geqslant 1$ приведен пример дерева $T_n$, содержащего более чем $(1/3) \cdot 1.415^n$ НДМ. Кроме того, доказано, что каждое $n$-вершинное дерево содержит менее $1.4205^n$ НДМ. 2. Некоторые определения и обозначенияКак обычно, множества вершин и ребер простого неориентированного графа $G$ обозначаются через $V(G)$ и $E(G)$ соответственно. Для вершины $v \in V(G)$ через $\operatorname{deg}_G(v)$ обозначается ее степень, а через $N_G[v]$ обозначается замкнутая окрестность, т.е. множество, состоящее из этой вершины и всех смежных с ней вершин. В случае, когда выбор графа $G$ ясен из контекста, мы будем обозначать степень и замкнутую окрестность вершины $v$ через $\operatorname{deg}(v)$ и $N[v]$ соответственно. Через $\Delta(G)$ обозначается максимальная степень вершин графа $G$. Деревом называется связный граф без циклов. Вершина дерева степени 1 называется листом. Назовем вершину предлистовой или предлистом, если она смежна хотя бы с одним листом. Присоединением предлиста степени 2 к вершине $v$ дерева будем называть добавление в это дерево вершин $u_1$, $u_2$ и ребер $u_1u_2$, $u_2v$. Назовем дерево разделимым, если из него можно удалить ребро таким образом, чтобы в полученном лесе количество НДМ осталось прежним, и неразделимым в противном случае. Диаметром $\operatorname{diam}(T)$ дерева $T$ называется максимально возможное расстояние между его вершинами. Простой путь $X=x_1x_2x_3\dots$ дерева $T$ называется диаметральным, если он состоит из $\operatorname{diam}(T)+1$ попарно различных вершин. Очевидно, что концы каждого диаметрального пути дерева являются листьями. Через $\partial_M(G)$ обозначим количество НДМ, которое содержит граф $G$. Обозначим через $\partial^+_M(G,v)$ (соответственно $\partial^-_M(G,v)$) количество НДМ графа $G$, которые содержат (соответственно не содержат) вершину $v$. Назовем вершину $v$ графа $G$ универсальной, если $\partial_M^+(G,v)=\partial_M(G)$, и пустой, если $\partial_M^-(G,v)=\partial_M(G)$. Пусть множество $D$ является некоторым НДМ дерева $T$. Обозначим через $\phi(D)$ множество, полученное заменой в $D$ всех листьев $T$ на смежные с ними предлистья. Легко видеть, что множество $\phi(D)$ определено однозначно и также является НДМ. Обозначим через $W_{a,b}$ дерево, полученное из пути $(v_1,v_2,v_3)$ присоединением $a \geqslant 0$ предлистьев степени 2 к вершине $v_1$ и $b \geqslant 0$ предлистьев степени 2 к вершине $v_3$. Нетрудно проверить, что имеет место равенство
$$
\begin{equation*}
\partial_M(W_{a,b})=\partial^+_M(W_{a,b},v_1)+\partial^+_M(W_{a,b},v_2) +\partial^+_M(W_{a,b},v_3)= 2^a(2^b-1)+2^{a+b}+2^b(2^a-1).
\end{equation*}
\notag
$$
Пусть дерево $T$ содержит поддерево $W_{a,b}$, где $a \geqslant 1$ и $b \geqslant 0$. Назовем это поддерево крайним, если его вершина, смежная с $b$ предлистьями степени 2, является единственной, смежной с другими вершинами $T$ (см. пример на рис. 1). Будем называть эту вершину контактной вершиной крайнего поддерева. Будем говорить, что множество $D$ доминирует вершину $v$ дерева $T$, если Обозначим через $\widehat{\partial}_M(W_{a,b})$ количество множеств мощности $\gamma(W_{a,b})$ поддерева $W_{a,b}$, которые доминируют все его вершины, кроме, быть может, контактной вершины. Нетрудно видеть, что $\widehat{\partial}_M(W_{a,b})=\partial_M(W_{a,b})+2^a$. Очевидно, что имеет место неравенство
$$
\begin{equation*}
\frac{\partial_M(W_{3,b})}{\widehat{\partial}_M(W_{3,b})} \geqslant \frac{\partial_M(W_{3,0})}{\widehat{\partial}_M(W_{3,0})}=\frac{15}{23}.
\end{equation*}
\notag
$$
Назовем $n$-вершинное дерево максимальным, если оно содержит максимально возможное количество НДМ среди всех $n$-вершинных деревьев. Аналогично, назовем $n$-вершинное дерево $k$-максимальным (где $k \geqslant 2$), если оно содержит максимально возможное количество НДМ среди деревьев со степенями всех вершин не более чем $k$. Заметим, что если дерево $T$ не является $\Delta(T)$-максимальным, то оно не является и максимальным, но обратное, вообще говоря, неверно. 3. Предварительные результаты3.1. Универсальные, пустые и предлистовые вершиныЛемма 1. Если в дереве $T$ найдется вершина $v$, смежная хотя бы с двумя листьями $u_1$ и $u_2$, то вершина $v$ универсальна, а листья $u_1$ и $u_2$ пусты. Доказательство. Предположим, что вершина $v$ не универсальна. Тогда найдется НДМ $D$, не включающее в себя $v$. Значит, $u_1,u_2 \in D$. Рассмотрим множество $D'=(D \cup \{v\}) \setminus \{u_1,u_2\}$. Очевидно, что если $D$ является доминирующим в $T$, то $D'$ также является доминирующим, но тогда $D$ не является наименьшим доминирующим, противоречие. Таким образом, вершина $v$ универсальна, следовательно, листья $u_1$ и $u_2$ являются пустыми. Лемма 2. Для любого дерева $T$ и его вершины $v$, которая не является листом или предлистом, имеют место следующие утверждения: 1) если все соседи $v$ являются предлистьями, то вершина $v$ является пустой; 2) если все соседи $v$, кроме вершины $w$, являются предлистьями, а вершина $w$ смежна хотя бы с одним предлистом, то вершина $v$ является пустой. Доказательство. Докажем первое утверждение леммы; второе утверждение доказывается аналогично. Предположим, что вершина $v$ не является пустой; тогда найдется некоторое НДМ $D$, включащее в себя $v$. Рассмотрим множество $\phi(D)$, которое также является НДМ в $T$. Это множество содержит вершину $v$, а также все смежные с ней вершины. Очевидно, что множество $\phi(D) \setminus \{v\}$ также является доминирующим в $T$ и имеет меньшую мощность, чем $D$, противоречие. Значит, вершина $v$ пустая, что и требовалось. Лемма 3. Если дерево $T$ содержит хотя бы одну универсальную или пустую вершину, то найдется лес $F$ такой, что Доказательство. Предположим, что дерево $T$ содержит универсальную вершину $v$. Очевидно, что $\operatorname{deg}(v) \geqslant 2$. Покажем, что в этом случае $v$ смежна по меньшей мере с двумя пустыми вершинами. Пусть это не так и $w_1, w_2, \dots, w_k$ – соседи вершины $v$, причем все они, кроме, быть может, вершины $w_1$, не являются пустыми вершинами. Тогда существует хотя бы одно НДМ $D$, включающее в себя вершину $v$ и вершины $w_2, \dots, w_k$. Очевидно, что множество $D'=(D \setminus \{v\}) \cup \{w_1\}$ также является НДМ, тогда вершина $w_1$ не является пустой, противоречие. Мы доказали, что вершина $v$ смежна хотя бы с двумя пустыми вершинами $w'_1, w'_2, \dots, w'_m$. Удалим из $T$ вершины $w'_2, \dots, w'_m$ и все инцидентные им ребра, обозначим через $F$ получившийся лес. Очевидно, что Кроме того, каждое НДМ дерева $T$ будет НДМ и для леса $F$, откуда $\partial_M(T) \leqslant \partial_M(F)$. Рассмотрим НДМ $D'$ леса $T$, содержащее все вершины множества $N[v] \setminus \{w'_1,\dots,w'_k\}$. Нетрудно видеть, что множество $(D' \setminus \{v\}) \cup \{w'_1\}$ является НДМ для леса $F$, тогда $\partial_M(F) > \partial_M(T)$, что и требовалось. Предположим теперь, что дерево $T$ без универсальных вершин содержит пустую вершину $u$. Поскольку в $T$ нет универсальных вершин, то $u$ смежна хотя бы с двумя непустыми вершинами $u_1, \dots, u_k$. Для каждого $1 \leqslant i \leqslant k$ обозначим через $T_i$ максимальное по включению поддерево, содержащее вершину $u_i$ и не содержащее вершину $u$. Обозначим через $F_0$ максимальный по включению лес, не содержащий вершину $u$ и вершины поддеревьев $T_1,\dots,T_k$. Заметим, что если лес $F_0$ непуст, то в каждой его компоненте связности найдется ровно одна вершина, которая пуста и смежна с $u$ в дереве $T$. Обозначим через $F$ результат удаления вершины $u$ из $T$. Очевидно, что $\Delta(F) \leqslant \Delta(T)$. Легко видеть, что имеет место равенство $\gamma(T)=\gamma(F)$. Действительно, поскольку вершина $u$ пуста в $T$, то $\gamma(T) \geqslant \gamma(F)$. Но если $\gamma(T) > \gamma(F)$, то для любого НДМ $D$ леса $F$ множество $D \cup \{u\}$ является НДМ в $T$ и вершина $u$ непуста, противоречие. Таким образом, имеем Заметим, что при любом $1 \leqslant i \leqslant k$ вершина $u_i$ не является универсальной в $T_i$ (иначе она была бы универсальной в $T$, что невозможно по предположению). Тогда $\prod^{k}_{i=1} \partial_M^-(T_i,u_i) > 0$, откуда $\partial_M(F) > \partial_M(T)$, что и требовалось.Лемма 4. Если в дереве $T$ найдутся смежные предлистовые вершины $v_1$ и $v_2$, то имеет место равенство $\partial_M(T)=\partial_M(T - v_1v_2)$. Доказательство. Обозначим через $N_l[v_1]$ (соответственно $N_l[v_2]$) множество, состоящее из вершины $v_1$ (соответственно $v_2$) и всех смежных с ней листьев. Обозначим через $F$ результат удаления ребра $v_1v_2$ из дерева $T$. Нетрудно видеть, что как в дереве $T$, так и в лесе $F$ каждое НДМ содержит ровно по одной вершине из множеств $N_l[v_1]$ и $N_l[v_2]$; тогда каждое НДМ дерева $T$ будет являться НДМ для леса $F$ и наоборот. Таким образом, $\partial_M(F)=\partial_M(T)$, что и требовалось. Лемма 5. Пусть $T$ – некоторое $n$-вершинное дерево. Если существует $n$-вершинный лес $F$ без изолированных вершин такой, что то дерево $T$ не является $\Delta(T)$-максимальным. Доказательство. Покажем, что если такой лес $F$ существует, то найдется $n$-вершинное дерево $T'$ такое, что $\Delta(T') \leqslant \max(3,\Delta(F))$ и $\partial_M(T') > \partial_M(T)$. Если $F$ является деревом, то положим $T'=F$. Предположим, что $F$ содержит хотя бы две компоненты связности $T_1$ и $T_2$, каждая из которых содержит не менее двух вершин. Заметим, что каждое дерево, состоящее не менее чем из двух вершин, содержит либо предлистовую вершину степени не более 2, либо предлистовую вершину, смежную хотя бы с двумя листьями (подойдут, например, предпоследние вершины некоторого диаметрального пути дерева). Покажем, что в каждом из следующих трех случаев можно соединить компоненты связности $T_1$ и $T_2$ таким образом, чтобы количество НДМ в получившемся дереве $T_{1,2}$ было не меньше, чем в исходном лесе $T_1 \cup T_2$. Случай 1. Каждая из компонент $T_1$ и $T_2$ содержит хотя бы одну предлистовую вершину степени не более 2 (считаем, что путь $P_2$ состоит из двух предлистовых вершин степени 1). Выберем такие предлистовые вершины $u \in V(T_1)$ и $v \in V(T_2)$ и проведем ребро $uv$. По предыдущей лемме, количество НДМ в результате добавления ребра не изменится. При этом, как нетрудно видеть,
$$
\begin{equation*}
\Delta(T_{1,2}) \leqslant \max(3,\Delta(T_1),\Delta(T_2)).
\end{equation*}
\notag
$$
Случай 2. В деревьях $T_1$ и $T_2$ найдутся вершины $u$ и $v$, каждая из которых смежна не менее чем с двумя листьями. Выберем листья $u'$ и $v'$, смежные с вершинами $u$ и $v$ соответственно, и проведем ребро $u'v'$. Очевидно, что $\Delta(T_{1,2})=\max(\Delta(T_1),\Delta(T_2))$. По лемме 2 вершины $u'$ и $v'$ будут пустыми в дереве $T_{1,2}$. Тогда что и требовалось.Случай 3. Одно из поддеревьев (будем считать, что $T_1$) содержит предлист $u$ степени не более 2, а другое поддерево содержит предлист $v$, смежный не менее чем с двумя листьями $v'$ и $v''$. Проведем ребро $uv'$ и покажем, что $\partial_M(T_{1,2}) \geqslant \partial_M(T_1 \cup T_2)$. По лемме 2 вершина $v'$ является пустой в дереве $T_{1,2}$. По лемме 1 вершина $v$ универсальна в лесе $T_1 \cup T_2$, тогда $\partial_M(T_{1,2}) \geqslant \partial_M^+(T_{1,2},v)=\partial_M(T_1 \cup T_2)$, что и требовалось. Таким образом, в результате замены леса $T_1 \cup T_2$ на дерево $T_{1,2}$ мы получили из леса $F$ некоторый лес $F_1$, содержащий на одну компоненту связности меньше, чем $F$, при этом $\partial_M(F_1) \geqslant \partial_M(F)$. Если $F_1$ является деревом, то положим $T'=F_1$, иначе будем повторять это преобразование до тех пор, пока не получим некоторое дерево $F_k$, положим $T'=F_k$. Поскольку $\Delta(F_k) \leqslant \Delta(T)$ и $\partial_M(F_k) > \partial_M(T)$, то условие леммы выполнено. Следствие 1. Для любого $n$-вершинного дерева $T$ имеют место следующие утверждения: 1) если $T$ содержит хотя бы одну универсальную или пустую вершину, то найдется $n'$-вершинное дерево $T'$ такое, что $n' < n$, $\Delta(T') \leqslant \Delta(T)$ и $\partial_M(T')^{1/n'} > \partial_M(T)^{1/n}$; 2) если $T$ разделимо, то найдется $n'$-вершинное дерево $T'$ такое, что $n' < n$, $\Delta(T') \leqslant \Delta(T)$ и $\partial_M(T')^{1/n'} \geqslant \partial_M(T)^{1/n}$. Доказательство. Первое утверждение сразу же вытекает из лемм 3 и 5. Второе утверждение очевидным образом следует из определения разделимого дерева. 3.2. $\mathcal{S}$-разбиение дереваСледующая структурная лемма играет ключевую роль при получении верхних оценок на количество НДМ в 4-максимальных и максимальных деревьях. Лемма 6. Пусть дерево $T$ не содержит пустых вершин. Тогда существует единственное разбиение $\mathcal{S}(T)$ множества $V(T)$ на непересекающиеся подмножества, обладающее следующими свойствами: 1) имеет место равенство $\gamma(T)=|\mathcal{S}(T)|$, при этом любое НДМ дерева $T$ содержит ровно одну вершину из каждого элемента разбиения $\mathcal{S}(T)$; 2) для любого элемента $S' \in \mathcal{S}(T)$ найдется вершина $v' \in V(T)$ такая, что $N[v']=S'$. Доказательство. Докажем утверждение индукцией по количеству вершин $n$. База индукции $n \leqslant 5$ очевидна. Покажем, что если $n \geqslant 6$ и $\operatorname{diam}(T) \leqslant 4$, то утверждение леммы выполнено. Если все нелистовые вершины $T$ являются предлистьями, то каждый предлист смежен ровно с одним листом (иначе в дереве найдутся пустые листья) и каждый элемент $\mathcal{S}(T)$ состоит из предлиста и смежного с ним листа. Легко видеть, что такое разбиение удовлетворяет условию леммы и является единственным. Если же в $T$ найдется вершина $v$, не являющаяся листом или предлистом, то легко видеть, что такая вершина единственна и все ее соседи являются предлистьями. Тогда по лемме 2 вершина $v$ является пустой, что противоречит предположению. Пусть теперь $n \geqslant 6$ и $\operatorname{diam}(T) \geqslant 5$. Обозначим через $X=x_1x_2x_3x_4x_5 \dots$ некоторый диаметральный путь в $T$. Заметим, что $\operatorname{deg}(x_2)=2$, в противном случае вершина $x_2$ смежна хотя бы с двумя листьями, которые по лемме 1 являются пустыми вершинами, что невозможно по условию. В зависимости от значения величин $\operatorname{deg}(x_3)$, $\operatorname{deg}(x_4)$ и $\operatorname{deg}(x_5)$ возможны следующие случаи. Случай 1: $\operatorname{deg}(x_3) \geqslant 3$. В этом случае вершина $x_3$ либо является предлистовой, либо она смежна хотя бы с одной предлистовой вершиной $x'_2$, отличной от $x_2$ и $x_4$. Удалим из $T$ вершины $x_1$ и $x_2$ и обозначим через $T_1$ получившееся дерево. Покажем, что если в $T$ нет пустых вершин, то в $T_1$ также нет пустых вершин. Вариант 1, а: вершина $x_3$ является предлистовой в $T_1$. Тогда для любого НДМ $D$ дерева $T$ множество $D \setminus \{x_1,x_2\}$ является НДМ для дерева $T_1$. Значит, в $T_1$ также нет пустых вершин. Вариант 1, b: вершина $x_3$ не является предлистовой. Тогда она смежна хотя бы с одной предлистовой вершиной $x'_2$, отличной от $x_2$ и $x_4$. Поскольку в $T$ нет пустых вершин и путь $X$ диаметральный, то $\operatorname{deg}(x'_2)=2$. Пусть некоторая вершина $x' \in V(T_1)$, отличная от $x'_1$ и $x'_2$, является пустой в $T_1$ (заметим сразу, что вершина $x'_2$ является предлистовой в $T_1$, поэтому она пустой быть не может). Тогда найдется НДМ $D$ дерева $T$, включающее в себя вершины $x_2$, $x'_2$ и $x'$. Но тогда множество $D \setminus \{x_2\}$ является НДМ для дерева $T_1$ и вершина $x'$ непуста в $T_1$, противоречие. Предположим теперь, что вершина $x'_1$ пуста в $T_1$. Поскольку дерево $T$ не содержит пустых вершин, то для него найдется некоторое НДМ $D_3$, включающее в себя вершину $x_3$. Очевидно, что множество $D_3 \setminus \{x_1,x_2\}$ является НДМ для дерева $T_1$. Если $D_3$ содержит $x'_1$, то $x'_1$ не является пустой в $T_1$, противоречие. Если же $D_3$ не содержит $x'_1$, то множество $(D_3 \cup \{x'_1\}) \setminus \{x'_2\}$ содержит $x'_1$ и является НДМ для $T_1$. Тогда вершина $x'_1$ не пуста в $T_1$ и мы снова получаем противоречие. Таким образом, дерево $T_1$ не содержит пустых вершин, тогда по предположению индукции в $T_1$ найдется единственное разбиение $\mathcal{S}(T_1)$, удовлетворяющее условию леммы. Легко видеть, что разбиение $\mathcal{S}(T)=\mathcal{S}(T_1)\cup \{\{x_1,x_2\}\}$ также удовлетворяет условию леммы и является единственным для $T$, что и требовалось. Случай 2: $\operatorname{deg}(x_3)=2$, $\operatorname{deg}(x_4) \geqslant 3$. Возможны следующие варианты. Вариант 2, a: вершина $x_4$ является предлистом. По лемме 2 вершина $x_3$ является пустой, что противоречит предположению. Вариант 2, b: вершина $x_4$ смежна хотя бы с одной предлистовой вершиной $x'_3$, отличной от вершин $x_3$ и $x_5$. По лемме 2 вершина $x_3$ является пустой, что противоречит предположению. Вариант 2, c: вершина $x_4$ смежна с некоторыми вершинами $w_1, w_2, \dots, w_s$, которые отличны от $x_3$ и $x_5$ и не являются предлистовыми (здесь $s \geqslant 1$). Поскольку путь $X$ является диаметральным и $T$ не содержит пустых вершин, то все соседи вершин $w_1,w_2,\dots,w_s$, отличные от $x_4$, являются предлистьями степени 2. Удалим из $T$ вершины $x_1,x_2,x_3$ и обозначим через $T_2$ получившееся дерево. Покажем, что если в $T$ нет пустых вершин, то в $T_2$ также нет пустых вершин. Пусть это не так и $T_2$ содержит пустую вершину $x'$. Тогда найдется НДМ $D$ дерева $T$, содержащее $x'$. Очевидно, что множество $D'=(D \setminus \{x_1\}) \cup \{x_2\} $ также является НДМ дерева $T$. При этом $D'$ не содержит одновременно вершины $x_3$ и $x_4$. Если $D'$ содержит $x_3$, то рассмотрим множество $D''=(D' \setminus \{x_3\}) \cup \{x_4\}$, иначе положим $D''=D'$. Очевидно, что $D''$ также является НДМ для $T$. Но тогда $D'' \setminus \{x_2\}$ является НДМ для $T_2$ и содержит $x'$, противоречие. Таким образом, дерево $T_2$ не содержит пустых вершин. Тогда по предположению индукции в $T_2$ найдется единственное разбиение $\mathcal{S}(T_2)$, удовлетворяющее условию леммы. Покажем, что
$$
\begin{equation*}
N_{T_2}[x_4]=\{x_4,x_5,w_1,\dots,w_s\} \in \mathcal{S}(T_2).
\end{equation*}
\notag
$$
Напомним, что все соседи вершин $w_1, w_2, \dots, w_s$, отличные от $x_4$, являются предлистьями степени 2. Нетрудно видеть, что каждое НДМ дерева $T_2$ содержит не более одной вершины из множества $N_{T_2}[x_4]$. Действительно, пусть найдется НДМ $D$, содержащее хотя бы две вершины из $N_{T_2}[x_4]$. Тогда множество $(\phi(D) \setminus N_{T_2}[x_4]) \cup \{x_5\}$ также является доминирующим в $T_2$, что противоречит минимальности $D$. Значит, ровно одна из вершин множества $N_{T_2}[x_4]$ входит в каждое НДМ $T_2$; при этом по условию каждая вершина из $N_{T_2}[x_4]$ непустая, что и требовалось. Рассмотрим разбиение
$$
\begin{equation*}
\mathcal{S}(T)=(\mathcal{S}(T_2) \setminus \{N_{T_2}[x_4]\}) \cup \{\{x_1,x_2\}, N_T[x_4]\}.
\end{equation*}
\notag
$$
Очевидно, что данное разбиение является единственным, удовлетворяющим условию леммы для дерева $T$, что и требовалось. Случай 3: $\operatorname{deg}(x_3)=\operatorname{deg}(x_4)=2$, $\operatorname{deg}(x_5) \geqslant 3$. Возможны следующие варианты. Вариант 3, a: вершина $x_5$ является предлистовой. По лемме 2 вершины $x_3$ и $x_4$ являются пустыми, что противоречит условию. Вариант 3, b: найдется вершина $u$, смежная с $x_5$ и с $\operatorname{deg}(u) - 1$ листом. В этом случае $\operatorname{deg}(u)=2$, поскольку в дереве нет пустых вершин. Рассмотрим дерево $T_3$, полученное удалением из $T$ вершины $u$ и смежного с ней листа $u'$. Покажем, что если $T$ не содержит пустых вершин, то $T_3$ их тоже не содержит. Пусть это не так и найдется вершина $v'$, которая пуста в $T_3$ и непуста в $T$. Нетрудно видеть, что как в $T_3$, так и в $T$ каждое НДМ содержит ровно 2 вершины из множества $\mathcal{X}_5=\{x_1,x_2,x_3,x_4,x_5\}$. Предположим, что $x' \notin \mathcal{X}_5$. Тогда найдется НДМ $D'$ дерева $T$, которое содержит вершины $x_2$, $x_5$ и $x'$. Нетрудно видеть, что множество $D' \setminus \{u,u'\}$ будет содержать вершину $x'$ и являться НДМ для дерева $T_3$, противоречие. Пусть теперь найдется вершина $x' \in \mathcal{X}_5$, которая является пустой в $T_3$. Тогда найдется НДМ $D''$ дерева $T$, содержащее вершины $x_6$ и $x'$ (если это не так и каждое НДМ дерева $T$, содержащее $x_6$, не содержит $x'$, то вершина $x'$ является пустой, что невозможно). Нетрудно видеть, что множество $D'' \setminus \{u,u'\}$ содержит $x'$ и является НДМ в $T_3$, противоречие. Таким образом, $T_3$ не содержит пустых вершин и по предположению индукции существует единственное разбиение $\mathcal{S}(T_3)$. Тогда разбиение $\mathcal{S}(T_3) \cup \{\{u,u'\}\}$ будет единственным в $T$, что и требовалось. Вариант 3, c: существует путь $(u_1,u_2,u_3,x_5)$ такой, что вершина $u_1$ является листом, вершина $u_2$ смежна с $\operatorname{deg}(u_2)-1$ листом, а вершина $u_3$ отлична от $x_4$ и $x_6$ и все ее соседи, отличные от $x_5$, являются либо листьями, либо предлистьями. Если вершина $u_3$ предлистовая, то применим рассуждения из варианта 1, a. Покажем, что если $u_3$ не является предлистовой, то она пуста в $T$. Достаточно доказать, что каждое НДМ дерева содержит не более одной вершины из множества $\{x_3,x_4,x_5,u_3\}$. Пусть найдется НДМ $D$, содержащее хотя бы две вершины из этого множества. Нетрудно видеть, что множество $D'=(\phi(D) \setminus\{x_3,x_4,x_5,u_3\}) \cup \{x_5\}$ является НДМ и при этом $|D'| < |\phi(D)|=|D|$, противоречие. С другой стороны, каждое НДМ дерева $T$ должно содержать хотя бы одну вершину из замкнутой окрестности $N[x_4]$, в которую не входит вершина $u_3$. Таким образом, вершина $u_3$ пуста, что противоречит условию леммы. Вариант 3, d: существует путь $(w_1,w_2,w_3,w_4,x_5)$ такой, что вершина $w_4$ отлична от вершин $x_4$ и $x_6$. Если при этом $\max(\operatorname{deg}(w_2), \operatorname{deg}(w_3), \operatorname{deg}(w_4)) > 2$, то переименуем вершины и применим рассуждения из случаев 1 и 2. Если же $\operatorname{deg}(w_2)= \operatorname{deg}(w_3)=\operatorname{deg}(w_4)=2$, то легко видеть, что вершины множества $\{x_3,x_4,w_3,w_4\}$ являются пустыми в $T$. Действительно, каждое НДМ дерева $T$ должно содержать хотя бы одну вершину из окрестностей $N[x_4]$ и $N[u_4]$. С другой стороны, как следует из рассуждений предыдущего варианта, каждое НДМ содержит не более одной вершины из множества $\{x_3,x_4,x_5,w_3,w_4\}$. Таким образом, $T$ содержит пустые вершины, что противоречит условию леммы. Случай 4: $\operatorname{deg}(x_2)=\operatorname{deg}(x_3) =\operatorname{deg}(x_4)=\operatorname{deg}(x_5)=2$. Рассмотрим дерево $T_4$, полученное из $T$ удалением вершин $x_1$, $x_2$, $x_3$. Докажем, что если $T$ не содержало пустых вершин, то $T_4$ также их не содержит. Сначала покажем, что $\gamma(T)=\gamma(T_4)+1$. С одной стороны, каждое НДМ дерева $T$ содержит вершину из множества $\{x_1,x_2\}$, откуда $\gamma(T) \geqslant \gamma(T_4)+1$. С другой стороны, для любого НДМ $D'$ дерева $T_4$ множество $D' \cup \{x_2\}$ будет НДМ для дерева $T$, откуда $\gamma(T) \leqslant \gamma(T_4)+1$. Предположим, что некоторая вершина $x'$ пуста в $T_4$, но непуста в $T$. Тогда найдется НДМ $D$ дерева $T$, включающее в себя $x'$. Рассмотрим множество $D'= D \setminus \{x_1,x_2\}$. Очевидно, что $D'$ содержит не более одной вершины из множества $\{x_3,x_4\}$. Если $D'$ содержит вершину $x_3$, то рассмотрим множество $D''=(D' \setminus \{x_3\}) \cup \{x_4\}$, иначе положим $D''=D'$. Тогда $D''$ является НДМ для $T_4$ и при этом содержит вершину $x'$, противоречие. Таким образом, дерево $T_4$ не содержит пустых вершин. По предположению индукции в $T_4$ существует единственное разбиение $\mathcal{S}(T_4)$. Очевидно, что оно включает в себя множество $\{x_4,x_5\}$. Нетрудно видеть, что разбиение является единственным подходящим для дерева $T$. Лемма доказана. Следствие 2. Для любого дерева $T$ без пустых вершин имеют место следующие утверждения: Доказательство. Докажем первое утверждение. Предположим, что некоторый элемент $S'$ такой, что $|S'| \geqslant 3$, содержит некоторый лист $u'$. В этом случае $S'$ содержит и смежную с ним вершину $u$. Поскольку $\partial_M^+(T,u')+\partial_M^+(T,u)= \partial_M(T)$, то все вершины $S' \setminus \{u,u'\}$ являются пустыми в $T$, что невозможно. Если же $S'$ содержит некоторый предлист $w$, но при этом не содержит лист $w'$, смежный с $w$, то, поскольку вершина $w'$ не универсальна, она не может входить ни в одно множество разбиения $\mathcal{S}(T)$, противоречие. Таким образом, все элементы $S'$ не являются листьями или предлистьями, что и требовалось. Второе и третье утверждения следствия сразу же вытекают из утверждения 2 предыдущей леммы. 4. Случай 4-максимальных деревьевЛемма 7. Для любого $n \geqslant 3$ если $n$-вершинное дерево $T$ без пустых вершин является 4-максимальным, то все элементы разбиения $\mathcal{S}(T)$ содержат не более 3 вершин. Доказательство. Предположим, что для некоторого 4-максимального дерева $T$ условие леммы не выполнено. Поскольку $\Delta(T) \leqslant 4$, то каждый элемент $\mathcal{S}(T)$ содержит не более 5 вершин. Возможны два случая. Случай 1: найдутся некоторые вершины $w,w_1,w_2,w_3 \in V(T)$ такие, что верно соотношение Для всех $1 \leqslant i \leqslant 3$ обозначим через $T_i$ максимальное по включению поддерево $T$, содержащее вершины $w$ и $w_i$ и не содержащее других соседей вершины $w$. Обозначим через $T'_i$ результат присоединения к вершине $w$ дерева $T_i$ листа $w_0$. Обозначим через $F_i$ результат удаления из $T_i$ вершин $w$ и $w_i$, а также всех инцидентных им ребер. При любом $1 \leqslant i \leqslant 3$ лес $F_i$ непуст и не содержит изолированных вершин, поскольку по следствию 2 все вершины окрестности $N[w]$ не являются листьями или предлистьями.Введем обозначения
$$
\begin{equation*}
A^+_i=\partial_+(T_i,w_i), \qquad A_i=\partial(F_i), \qquad A^-_i=\partial_+(T'_i,w_0).
\end{equation*}
\notag
$$
Имеет место равенство
$$
\begin{equation*}
\begin{aligned} \, \partial_M(T) &=\partial_M^+(T,w)+\partial_M^+(T,w_1)+\partial_M^+(T,w_2) +\partial_M^+(T,w_3) \\ &= A_1A_2A_3+A^+_1A^-_2A^-_3+A^-_1A^+_2A^-_3+A^-_1A^-_2A^+_3. \end{aligned}
\end{equation*}
\notag
$$
Удалим из дерева $T$ вершины $w$ и $w_3$, а к вершинам $w_1$ и $w_2$ присоединим листья $w'_1$ и $w'_2$ соответственно (см. рис. 2). В полученном лесе $F$ обозначим через $T''_1$ (соответственно через $T''_2$) компоненту связности, содержащую вершину $w_1$ (соответственно $w_2)$. Тогда $F=T''_1 \cup T''_2 \cup F_3$. Имеем
$$
\begin{equation*}
\begin{aligned} \, \partial_M(F) &=\bigl(\partial_M^+(T''_1,w_1)+\partial_M^+(T''_1,w'_1)\bigr) \cdot \bigl(\partial_M^+(T''_2,w_2)+\partial_M^+(T''_2,w'_2)\bigr)\cdot \partial_M(F_3) \\ &=(A^+_1+A_1) \cdot (A^+_2+A_2) \cdot A_3=A^+_1A^+_2A_3+A^+_1A_2A_3+A_1A^ +_2A_3+A_1A_2A_3. \end{aligned}
\end{equation*}
\notag
$$
Поскольку дерево $T$ не содержит универсальных вершин, то для любого $1 \leqslant i \leqslant 3$ найдется некоторое НДМ леса $F_i$, не содержащее ни одной из вершин, смежных с вершиной $w_i$ в дереве $T$. Тогда для любого $1 \leqslant i \leqslant 3$ имеет место строгое неравенство $A_i > A^-_i$. Кроме того, верно неравенство $A^+_i \geqslant A_i$. Мы можем считать, что $A^+_1/A_1 \geqslant A^+_2/A_2 \geqslant A^+_3/A_3$. Тогда имеет место строгое неравенство $A^+_1A^+_2A_3 \geqslant A_1A_2A^+_3 > A^-_1A^-_2A^+_3$, откуда $\partial_M(F) > \partial_M(T)$. Значит, по лемме 5 дерево $T$ не является 4-максимальным, противоречие. Случай 2: найдутся некоторые вершины $w,w_1,w_2,w_3,w_4 \in V(T)$ такие, что верно соотношение Для всех $1 \leqslant i \leqslant 4$ определим подграфы $T_i$, $T'_i$, $F_i$ и введем обозначения $A^+_i$, $A_i$, $ A^-_i$ аналогично предыдущему случаю. Имеет место равенство
$$
\begin{equation*}
\partial_M(T)=A_1A_2A_3A_4+A^+_1A^-_2A^-_3A^-_4+A^-_1A^+_2A^-_3A^-_4 +A^-_1A^-_2A^+_3A^-_4+A^-_1A^-_2A^-_3A^+_4.
\end{equation*}
\notag
$$
Удалим из дерева $T$ вершину $w_4$ и все инцидентные ей ребра, а также ребро $ww_3$, после чего присоединим лист $w'_3$ к вершине $w_3$. В полученном лесе $F$ обозначим через $T'$ компоненту связности, содержащую вершины $w$, $w_1$, $w_2$, а через $T''$ – компоненту связности, содержащую вершины $w_3$ и $w'_3$. Тогда $F=T' \cup T'' \cup F_4$. Имеет место равенство
$$
\begin{equation*}
\begin{aligned} \, \partial_M(F) &=\bigl(\partial_M^+(T',w)+\partial_M^+(T',w_1)+\partial_M^+(T',w_2)\bigr) \\ &\qquad\times \bigl(\partial_M^+(T'',w_3)+\partial_M^+(T'',w'_3)\bigr) \cdot \partial_M(F_4) \\ &=(A_1A_2+A^+_1A^-_2+A^-_1A^+_2)\cdot (A^+_3+A_3)\cdot A_4. \end{aligned}
\end{equation*}
\notag
$$
Мы можем считать, что $A^+_1/A^-_1 \geqslant A^+_3/A^-_3 \geqslant A^+_4/A^-_4 > A^+_4/A_4$, тогда имеет место строгое неравенство $A^+_1A^-_2A^+_3A_4 > A^-_1A^-_2A^-_3A^+_4$. Следовательно, $\partial_M(F) > \partial_M(T)$ и по лемме 5 дерево $T$ не является 4-максимальным, противоречие. Теорема 1. Для любого $n \geqslant 4$ каждое 4-максимальное $n$-вершинное дерево $T$ содержит не более $(\sqrt{2})^{n}$ НДМ. Равенство $\partial_M(T)=(\sqrt{2})^{n}$ достигается, если и только если $n=2l$ и $T$ содержит ровно $l$ предлистовых вершин, каждая из которых смежна с единственным листом. Доказательство. Легко проверить, что условие теоремы выполнено при $n < 6$. Предположим, что при $n \geqslant 6$ найдутся деревья, для которых это условие не выполнено; выберем среди них дерево $T$ с наименьшим количеством вершин. По следствию 1 если $T$ содержит универсальные или пустые вершины, то оно содержит менее $(\sqrt{2})^n$ НДМ. Аналогично, нетрудно проверить, что если $T$ разделимо, то по следствию 1 оно удовлетворяет условию теоремы, что противоречит предположению. Тогда по лемме 6 существует единственное $\mathcal{S}$-разбиение $\mathcal{S}(T)$. Поскольку дерево $T$ неразделимо, оно не содержит смежных предлистовых вершин и разбиение $\mathcal{S}(T)$ содержит хотя бы один элемент $S'$ из 3 вершин (случай $|S'| > 3$ невозможен по предыдущей лемме). По следствию 1 все вершины $S'$ не являются листьями или предлистьями, откуда $\operatorname{diam}(T) \geqslant 6$. Обозначим через $X=x_1x_2x_3x_4x_5x_6\dots $ некоторый диаметральный путь $T$ (в качестве иллюстрации см. пример на рис. 3). Если вершина $x_3$ является предлистом, то в $T$ есть пара смежных предлистьев $x_2$ и $x_3$, тогда по лемме 4 дерево $T$ разделимо, что противоречит предположению. Поскольку в $T$ нет пустых вершин, то любой предлист $T$ смежен с единственным листом. Таким образом, все соседи вершины $x_3$, отличные от $x_4$, являются предлистьями степени 2. Тогда по леммам 6 и 7 имеем $x_3 \in N[x_4]=\{x_3,x_4,x_5\} \in \mathcal{S}(T)$. Докажем, что если $\operatorname{deg}(x_5) \geqslant 3$, то все вершины множества $N[x_5] \setminus \{x_4,x_5,x_6\}$ являются предлистьями степени 2. Пусть это множество непусто, обозначим через $w$ одну из входящих в него вершин. Предположим, что $w$ не является предлистом, тогда найдутся такие вершины $w_0$ и $w_1$, что По следствию 1 вершина $w_1$ не является листом и предлистом; тогда в $T$ найдется путь $(w_1,u',u'')$, где вершина $u'$ отлична от вершины $w_0$. Но тогда путь $u''u'w_1w_0wx_5x_6 \dots$ длиннее пути $X$, противоречие. Если же вершина $w$ смежна с листом $w'$ и при этом $\operatorname{deg}(w) \geqslant 3$, то обозначим через $u$ соседа $w$, отличного от $x_5$ и $w'$. Если $u$ является предлистом, то дерево $T$ разделимо по лемме 4. Если же $u$ не является предлистом, то найдутся такие вершины $u_0$ и $u_1$, что $\{u,u_0,u_1\}=N[u_0] \in \mathcal{S}(T)$. Тогда путь $u_1u_0uwx_5\dots$ имеет ту же длину, что и путь $X$, но при этом по следствию 2 вершина $u_1$ не является листом, противоречие.Таким образом, вершины $x_3$ и $x_5$ смежны с $a=\operatorname{deg}(x_3) - 1$ и $b=\operatorname{deg}(x_5) - 2$ предлистьями степени 2 соответственно. Обозначим через $T'$ дерево, полученное в результате удаления из $T$ этих предлистьев, смежных с ними листьев, а также вершины $x_3$. Обозначим через $T_6$ результат удаления из $T'$ вершин $x_4$ и $x_5$. По предположению индукции
$$
\begin{equation*}
\partial_M(T') \leqslant 2^{|V(T')|/2}=2^{(n - 2a - 2b -1)/2}.
\end{equation*}
\notag
$$
Имеем
$$
\begin{equation*}
\begin{gathered} \, \partial_M(T')=\partial_M^+(T',x_4) +\partial_M^+(T',x_5), \qquad \partial_M(T)=\partial_M^+(T,x_3)+\partial_M^+(T,x_4) +\partial_M^+(T,x_5), \\ \partial_M^+(T,x_4)=2^{a+b} \cdot \partial_M^+(T',x_4), \qquad \partial_M^+(T,x_5)=(2^a - 1) \cdot 2^b \cdot \partial_M^+(T',x_5), \\ \partial_M^+(T,x_3)=2^a \cdot (2^b-1) \cdot \partial_M(T_6)+2^a \cdot \partial_M^+(T_6,x_6). \end{gathered}
\end{equation*}
\notag
$$
Нетрудно доказать, что если $a,b \in \{1,2\}$, то из соотношений $\partial_M^+(T_6,x_6) \leqslant \partial_M(T_6)$, $\partial_M(T_6)=\partial_M^+(T',x_4)$ и $\partial_M^+(T',x_4) \leqslant \partial_M^+(T',x_5)$ следует выполнение неравенства
$$
\begin{equation*}
2^{a+b+1/2} \cdot (\partial_M^+(T',x_4)+\partial_M^+(T',x_5)) > \partial_M^+(T,x_3)+\partial_M^+(T,x_4)+\partial_M^+(T,x_5).
\end{equation*}
\notag
$$
Если же $a=3$, то для выполнения этого неравенства потребуется также выполнение соотношения $\partial_M^+(T_6,x_6)/\partial_M(T_6) \leqslant 3/4$. Цель дальнейших рассуждений – доказать это соотношение. Мы рассмотрим четыре случая в зависимости от того, являются ли вершины $x_6$, $x_7$ или их соседи предлистьями в дереве $T$. Случай 1: найдутся вершины $w$ и $w'$ такие, что $\{x_6,w,w'\}=N[w] \in \mathcal{S}(T)$. Заметим, что вершина $w$ может как совпадать, так и не совпадать с вершиной $x_7$. Вариант 1, a: все соседи вершины $x_6$, отличные от $x_5$ и $w$, являются предлистьями степени 2 (в частности, возможен вариант $\operatorname{deg}_T(x_6)=2$). Очевидно, что имеет место неравенство $\partial_M^+(T_6,x_6) \leqslant \partial_M^+(T_6,w)$, откуда $\partial_M^+(T_6,x_6)/\partial_M(T_6) \leqslant 1/2$. Вариант 1, b: вершина $x_6$ смежна с некоторой вершиной $x'_5$, которая отлична от вершин $x_5$ и $w$ и не является предлистом, а также, возможно, с предлистовой вершиной $x''_5$ степени 2. Тогда найдутся вершины $x'_3$ и $x'_4$ такие, что $\{x'_3,x'_4,x'_5\}=N_{T}[x'_4] \in \mathcal{S}(T)$. Обозначим через $T'_5$ максимальное по включению поддерево $T$, содержащее $x'_5$ и не содержащее $x_6$. Легко видеть, что дерево $T'_5$ является крайним подграфом $W_{a',b'}$ дерева $T_6$ с контактной вершиной $x'_5$, где $a'=\operatorname{deg}(x'_3) - 1$ и $b'=\operatorname{deg}(x'_5) - 2$. Мы можем считать, что $a'=3$ (иначе рассмотрим диаметральный путь, проходящий через вершины $x'_5$ и $x_6$, переименуем вершины дерева и применим к этому пути рассуждения выше). Обозначим через $T'_6$ максимальное по включению поддерево дерева $T_6$, содержащее вершину $x_6$ и не содержащее вершину $x'_5$. Тогда справедливы соотношения
$$
\begin{equation*}
\partial_M^+(T_6,x_6)=\partial_M^+(T'_6,x_6) \cdot \widehat{\partial}_M(W_{a',b'}), \qquad \partial_M^+(T_6,w)=\partial_M^+(T'_6,w) \cdot \partial_M(W_{a',b'}).
\end{equation*}
\notag
$$
Как и в предыдущем варианте, имеет место неравенство $\partial_M^+(T'_6,x_6) \leqslant \partial_M^+(T'_6,w)$. Поскольку $\partial_M(W_{3,b'})/\widehat{\partial}_M(W_{3,b'}) \geqslant 15/23$, то $\partial_M^+(T',x_6)/\partial_M(T_6) \leqslant 3/4$. Заметим, что в рассмотренных вариантах рассуждения останутся верными и в случаях, когда предлистья, смежные с $x_6$, имеют степень более 2. Этот факт пригодится нам при рассмотрении варианта 3, b. Вариант 1, c: вершина $x_6$ смежна с двумя вершинами $x'_5$ и $x''_5$, которые отличны от вершин $x_5$ и $w$ и не являются предлистьями. Из рассуждений варианта 1, b следует, что вершины $x'_5$ и $x''_5$ являются контактными вершинами крайних подграфов $W_{3,b'}$ и $W_{3,b''}$ дерева $T_6$, где $b'=\operatorname{deg}(x'_5) - 2$ и $b''=\operatorname{deg}(x''_5) - 2$. Обозначим через $T''_6$ максимальное по включению поддерево $T$, содержащее вершину $x_6$ и не содержащее вершины $x'_5$ и $x''_5$. Тогда
$$
\begin{equation*}
\begin{gathered} \, \partial_M(T_6,x_6)=\widehat{\partial}_M(W_{3,b'}) \cdot \widehat{\partial}_M(W_{3,b''}) \cdot \partial_M(T''_6,x_6), \\ \partial_M(T_6,w)=\partial_M(W_{3,b'}) \cdot \partial_M(W_{3,b''}) \cdot \partial_M(T''_6,w), \\ \partial_M^+(T_6,w) \geqslant \frac{\partial_M(W_{3,b'})}{\widehat{\partial}_M(W_{3,b'})} \cdot \frac{\partial_M(W_{3,b''})}{\widehat{\partial}_M(W_{3,b''})} \cdot \partial_M^+(T_6,x_6) > \frac 13 \cdot \partial_M^+(T_6,x_6). \end{gathered}
\end{equation*}
\notag
$$
Следовательно, имеет место неравенство $\partial_M^+(T_6,x_6)/\partial_M(T_6) \leqslant 3/4$. Рассмотрение случая 1 завершено. В случаях 2–4 мы предполагаем, что вершина $x_6$ является предлистовой и смежна с листом $l_6$, с вершинами $x_5$ и $x_7$, а также, быть может, с вершиной $x'_5$, отличной от вершин $x_5$, $l_6$ и $x_7$. При этом вершина $x'_5$ (если она присутствует в дереве) является контактной вершиной некоторого внешнего подграфа $W_{3,b'}$, где $b'=\operatorname{deg}(x'_5) - 2$. Поскольку $\partial_M(T_6)=\partial_M^+(T_6,x_6) +\partial_M^+(T_6,l_6)$, то достаточно доказать, что либо выполнено неравенство $\partial_M^+(T_6,x_6) \leqslant 3\partial_M^+(T_6,l_6)$, либо дерево $T$ не является 4-максимальным. Случай 2: вершины $x_7$ и $x_8$ принадлежат разным элементам разбиения $\mathcal{S}(T)$. Поскольку $T$ неразделимо, то вершина $x_7$ не является предлистовой. Тогда найдутся вершины $u$ и $u'$ такие, что $ \{x_7,u,u'\} =N[u] \in \mathcal{S}(T)$. Поскольку путь $X$ является диаметральным и $T$ не содержит пустых вершин, то все соседи $u'$, отличные от $u$, являются предлистовыми вершинами степени 2. Далее возможны два варианта в зависимости от значения величины $\operatorname{deg}_T(x_6)$. Вариант 2, a: $\operatorname{deg}_T(x_6)=3$. Покажем, что имеет место неравенство $\partial_M^+(T_6,x_6) < 3 \partial_M^+(T_6,l_6)$. Обозначим через $T_7$ максимальное по включению поддерево $T_6$, содержащее вершину $x_7$ и не содержащее вершину $x_6$. Обозначим через $F_7$ результат удаления вершины $x_7$ и всех инцидентных ей ребер из дерева $T_7$. Имеем
$$
\begin{equation*}
\begin{gathered} \, \partial_M^+(T_6,l_6)=\partial_M(T_7)= \partial_M^+(T_7,x_7) +\partial_M^+(T_7,u)+\partial_M^+(T_7,u'), \\ \partial_M^+(T_6,x_6)=\partial_M^+(T_7,x_7)+\partial_M^+(F_7,u)+\partial_M^+(F_7,u'). \end{gathered}
\end{equation*}
\notag
$$
Заметим, что $\partial_M^+(F_7,u')=\partial_M^+(F_7,u)$, поскольку все соседи вершины $u'$, кроме вершины $u$, являются предлистьями степени 2. Легко видеть, что
$$
\begin{equation*}
\partial_M^+(F_7,u)=\partial_M^+(T_7,u)=\partial_M(T_7 \setminus N[u]).
\end{equation*}
\notag
$$
Тогда имеет место соотношение
$$
\begin{equation*}
\partial_M^+(T_6,x_6)=\partial_M^+(T_7,x_7) +2\partial_M^+(T_7,u) < 2\partial_M^+(T_6,l_6).
\end{equation*}
\notag
$$
Вариант 2, b: $\operatorname{deg}_T(x_6)=4$. В дереве $T_6$ найдется вершина $x'_5$, которая смежна с $x_6$ и является контактной вершиной крайнего подграфа $W_{3,b'}$, где $b'=\operatorname{deg}(x'_5) -2$. Используя рассуждения варианта 2, a, получим соотношения
$$
\begin{equation*}
\begin{gathered} \, \partial_M^+(T_6,l_6)=\partial_M(W_{3,b'}) \cdot (\partial_M^+(T_7,x_7) +\partial_M^+(T_7,u)+\partial_M^+(T_7,u')), \\ \partial_M^+(T_6,x_6)=\widehat{\partial}_M(W_{3,b'}) \cdot ( \partial_M^+(T_7,x_7) +2\partial_M^+(T_7,u)). \end{gathered}
\end{equation*}
\notag
$$
Легко проверить, что $\partial_M^+(T_7,u) \leqslant 2 \partial_M^+(T_7,x_7)$ (равенство возможно только в случае $\operatorname{deg}(u')=2$). Тогда из неравенства $\partial_M(W_{3,b'}) / \widehat{\partial}_M(W_{3,b'}) \geqslant 15/23$ следует неравенство $\partial_M^+(T_6,x_6) < 3 \partial_M^+(T_6,l_6)$, что и требовалось. Случай 3: вершины $x_7$ и $x_8$ находятся в одном множестве разбиения, при этом $\operatorname{deg}(x_7) > 2$. В этом случае $N[x_8]=\{x_7,x_8,x_9\} \in \mathcal{S}(T)$. Вариант 3, a: вершина $x_7$ смежна хотя бы с одной предлистовой вершиной $x'_7$ (при этом возможен случай $\operatorname{deg}(x'_7) >2$). Обозначим через $l'_7$ единственный лист, смежный с $x'_7$. Покажем, что в этом случае имеет место неравенство $\partial_M^+(T_6,x_6) < 3\partial_M^+(T_6,l_6)$. Обозначим через $T_7$ максимальное по включению поддерево $T$, содержащее $x_7$ и не содержащее $x_6$. Обозначим через $F_7$ результат удаления из $T_7$ вершины $x_7$ и всех инцидентных ей ребер. Имеем
$$
\begin{equation*}
\partial_M^+(T_6,l_6)=\partial_M^+(T_7,x_7)+\partial_M^+(T_7,x_8)+\partial_M^+(T_7,x_9).
\end{equation*}
\notag
$$
С другой стороны,
$$
\begin{equation*}
\partial_M^+(T_6,x_6)=\partial_M^+(T_7,x_7)+\partial_M^+(T_7,x_8)+\partial_M^+(F_7,x_9).
\end{equation*}
\notag
$$
Поскольку $\partial_M^+(T_7,x'_7) \geqslant \partial_M^+(T_7,l'_7)$, то верно неравенство $\partial_M^+(F_7,x_9) \leqslant 2 \partial_M^+(T_7,x_9)$, откуда $\partial_M^+(T_6,x_6) < 2 \partial_M^+(T_6,l_6)$, что и требовалось. Вариант 3, b: вершина $x_7$ смежна с некоторой вершиной $x'_6$, отличной от $x_8$, которая не является предлистовой. Предположим, что найдется некоторый диаметральный путь $X''=x''_1x''_2x''_3x''_4x''_5x'_6x_7\dots$ . Поскольку вершина $x'_6$ не является предлистовой, то рассмотрим путь $X''$ вместо пути $x$ и применим рассуждения из случая 1. Если же такого пути не найдется, то, как нетрудно видеть, вершина $x'_6$ сама является контактной вершиной некоторого крайнего подграфа $W_{a',b'}$. Тогда найдется некоторый путь $X'''=x'''_2x'''_3x'''_4x'''_5x'_6x_7\dots$, содержащий $\operatorname{diam}(T)$ вершин. Нетрудно проверить, что рассуждения случая 1 применимы и для пути $X'''$ (в этом случае вершина $x_7$, которая не является предлистовой, будет играть роль вершины $x_6$). Случай 4: вершины $x_7$ и $x_8$ находятся в одном множестве разбиения, причем $\operatorname{deg}(x_7)=2$. В этом случае $N[x_8]=\{x_7,x_8,x_9\} \in \mathcal{S}(T)$. Обозначим через $T'_6$ максимальное по включению поддерево $T$, содержащее вершину $x_6$ и не содержащее вершину $x_7$. Для $m \in \{7,8,9\}$ обозначим через $T_m$ максимальное по включению поддерево $T$, содержащее вершину $x_m$ и не содержащее вершину $x_{m-1}$. Вариант 4, a: $\operatorname{deg}(x_6)=3$. Дерево $T$ устроено следующим образом (см. рис. 4). Имеют место равенства
$$
\begin{equation*}
\begin{gathered} \, \partial_M(T)=\partial_M^+(T,x_7)+\partial_M^+(T,x_8)+\partial_M^+(T,x_9), \\ \partial_M^+(T,x_7)=\partial_M^+(T_7,x_7) \cdot \partial_M(T'_6) =\partial_M^+(T_7,x_7) \cdot \partial_M(W_{3,b+1}), \\ \partial_M^+(T,x_8)=\partial_M^+(T_7,x_8) \cdot \partial_M(T'_6) =\partial_M^+(T_7,x_8) \cdot \partial_M(W_{3,b+1}), \\ \partial_M^+(T,x_9)=\partial_M^+(T_8,x_9) \cdot \partial_M^+(T'_6,x_6) =\partial_M^+(T_8,x_9) \cdot \widehat{\partial}_M(W_{3,b}). \end{gathered}
\end{equation*}
\notag
$$
Напомним, что
$$
\begin{equation*}
\partial_M(W_{3,b})=2^{3+b}+(2^3-1)2^b+2^3(2^b-1), \qquad \widehat{\partial}_M(W_{3,b})=\partial_M(W_{3,b})+2^b.
\end{equation*}
\notag
$$
Удалим из дерева $T$ ребро $x_7x_8$, а компоненту связности, содержащую вершину $x_7$, заменим на лес $(6+b)P_2$. Обозначим через $F$ получившийся лес, тогда имеем $\partial_M(F)=2^{6+b}(\partial_M^+(T_8,x_8)+\partial_M^+(T_8,x_9))$. Кроме того, имеет место неравенство
$$
\begin{equation*}
\partial_M^+(T_7,x_7) \leqslant \partial_M^+(T_7,x_8) =\partial_M^+(T_8,x_8) \leqslant \partial_M^+(T_8,x_9).
\end{equation*}
\notag
$$
Нетрудно проверить, что имеет место строгое неравенство $\partial_M(F) > \partial_M(T)$. Тогда по лемме 5 дерево $T$ не 4-максимально, противоречие. Вариант 4, b: $\operatorname{deg}(x_6)=4$. В этом случае вершина $x_6$ смежна с некоторой вершиной $x'_5$, отличной от $x_5$, $x_6$ и $l_6$. Поскольку $T$ неразделимо, то $x'_5$ является контактной вершиной подграфа $W_{3,b'}$, где $b'=\operatorname{deg}(x'_5) -2 $. Тогда имеют место следующие соотношения:
$$
\begin{equation*}
\begin{aligned} \, \partial_M(T) &=\partial_M^+(T,x_7)+\partial_M^+(T,x_8)+\partial_M^+(T,x_9), \\ \partial_M^+(T,x_7) &=\partial_M^+(T_7,x_7) \cdot \partial_M(T_6)=\partial_M^+(T_7,x_7) \cdot \bigl(\partial_M^+(T_6,l_6)+\partial_M^+(T_6,x_6)\bigr) \\ &=\partial_M^+(T_7,x_7)\cdot\bigl(\partial_M(W_{3,b}) \cdot \partial_M(W_{3,b'} ) +\widehat{\partial}_M(W_{3,b}) \cdot \widehat{\partial}_M(W_{3,b'} )\bigr), \\ \partial_M^+(T,x_8) &=\partial_M^+(T_7,x_8) \cdot \bigl(\partial_M(W_{3,b}) \cdot \partial_M(W_{3,b'} )+\widehat{\partial}_M(W_{3,b}) \cdot \widehat{\partial}_M(W_{3,b'} )\bigr), \\ \partial_M^+(T,x_9) &=\partial_M^+(T_8,x_9) \cdot \partial_M^+(T_6,x_6) =\partial_M^+(T_8,x_9) \cdot \widehat{\partial}_M(W_{3,b}) \cdot \widehat{\partial}_M(W_{3,b'}). \end{aligned}
\end{equation*}
\notag
$$
Удалим из дерева вершины $x_6$ и $l_6$, после чего в получившемся лесе заменим компоненты связности, содержащие вершины $x_5$ и $x'_5$, на лес $(7+b+b')P_2$. Кроме того, присоединим к вершине $x_7$ три предлиста степени 2. В полученном $n$-вершинном лесе $F$ обозначим через $T'$ компоненту связности, содержащую вершину $x_7$. Тогда верны соотношения
$$
\begin{equation*}
\begin{gathered} \, \partial_M(F)=2^{7+b+b'}( \partial_M^+(T',x_7)+\partial_M^+(T',x_8) +\partial_M^+(T',x_9)), \\ \partial_M(T',x_7)=8 \cdot \partial_M^+(T_7,x_7), \ \partial_M(T',x_8) =8 \cdot \partial_M^+(T_7,x_8), \ \partial_M(T',x_9)=7 \cdot \partial_M^+(T_8,x_9). \end{gathered}
\end{equation*}
\notag
$$
Нетрудно проверить, что при любых значениях $b,b' \in \{0,1,2\}$ имеет место строгое неравенство $\partial_M(F) > \partial_M(T)$. Тогда по лемме 5 дерево $T$ не 4-максимально, противоречие. Теорема доказана. 5. Оценки максимально возможного количества НДМ в $n$-вершинных деревьях5.1. Нижняя оценкаНапомним, что 19-вершинное дерево $W_{4,4}$ есть результат присоединения к каждому из концов пути $P_3$ четырех предлистьев степени 2 (см. рис. 5). При этом $\partial_M(W_{4,4})=736 > (\sqrt{2})^{19}$. Введем обозначение $\theta =736^{1/19}=1.415\dots$ . Доказательство. Сначала покажем, что при $n=19k$ утверждение теоремы выполнено. Рассмотрим лес $kW_{4,4}$ и будем произвольным образом соединять предлистья степени 2 из разных компонент связности, пока не получим некоторое дерево $T_{19k}$. Из доказательства леммы 5 следует, что $\Delta(T_{n})=5$ и Пусть теперь $n=19k+r$, где $k \geqslant 0$ и $1 \leqslant r < 19$. Если $r$ четно, то положим Если $r$ нечетно и $k=0$, то положим
$$
\begin{equation*}
F_n=P_r \quad\text{при}\ \ r < 7, \qquad F_{n}=P_7 \cup \frac{r-7}{2}P_2 \quad\text{при}\ \ r \geqslant 7.
\end{equation*}
\notag
$$
Если же $r$ нечетно и $k > 0$, то положим
$$
\begin{equation*}
F_n=(k-1)W_{5,5} \cup \biggl(10+\frac{r-1}{2}\biggr)P_2.
\end{equation*}
\notag
$$
Будем произвольным образом соединять предлистья степени не более 2 из разных компонент связности $F_n$, пока не получим некоторое дерево $T_n$. Из доказательства леммы 5 следует, что $\Delta(T_{n}) \leqslant 5$ и $\partial_M(T_n)=\partial_M(F_n)$. Легко проверить, что при всех $n < 19$ верно неравенство $\partial_M(T_n) >(1/3)\cdot \theta^n$. Заметим, что для всех целых $p$ на отрезке $[1,36]$ выполнено неравенство $(\sqrt{2})^p/\theta^p >1/3$. Тогда, как нетрудно видеть, для всех целых $n=19k+r \geqslant 19$ имеет место неравенство
$$
\begin{equation*}
\frac{\partial_M(T_n)}{ \theta^n} \geqslant \frac{\theta^{19(k-1)} \cdot (\sqrt{2})^{19+r}} {\theta^{19k+r}} > \frac 13,
\end{equation*}
\notag
$$
откуда Теорема доказана. 5.2. Верхняя оценкаПо-видимому, максимальные деревья обладают сложной структурой, которая плохо поддается описанию. Используя понятие $\mathcal{S}$-разбиения, мы получим нетривиальную верхнюю оценку на количество НДМ в $n$-вершинном дереве. Лемма 8. Пусть $T$ – максимальное $n$-вершинное дерево, не содержащее пустых вершин. Тогда все элементы разбиения $\mathcal{S}(T)$ содержат не более трех вершин. Доказательство. Предположим, что для некоторого максимального дерева $T$ найдется элемент $S' \in \mathcal{S}(T)$, содержащий $k > 3$ вершин. Если $k \in \{4,5\}$, то применим рассуждения из леммы 7. Пусть $k=2p+\delta$, где $p \geqslant 3$ и $\delta \in \{0,1\}$. В этом случае найдутся вершины $w,w_1,\dots,w_{k-1}$ такие, что $\{w,w_1,\dots,w_{k-1}\}=N[w] \in \mathcal{S}(T)$. Для всех $1 \leqslant i \leqslant k-1$ определим подграфы $T_i$, $T'_i$, $F_i$ и величины $A_i$, $A^+_i$, $A^-_i$ аналогично лемме 7. Напомним, что имеет место неравенство $A^-_i < A_i \leqslant A^+_i$. Введем обозначения
$$
\begin{equation*}
\begin{gathered} \, A_*=\prod_{i=1}^{k-1} A_i, \qquad A_*^+=\prod_{i=1}^{k-1} A^+_i, \qquad A_*^-=\prod_{i=1}^{k-1} A^-_i, \\ A^+_{\mathrm{I}}=\prod_{i=1}^{p} A^+_i \cdot\prod_{j=p+1}^{k-1} A_j, \qquad A^+_{\mathrm{II}}=\prod_{i=1}^{p} A_i \cdot \prod_{j=p+1}^{k-1} A^+_j. \end{gathered}
\end{equation*}
\notag
$$
Заметим, что $\partial_M(T)=A_*+A_*^- \cdot \sum_{i=1}^{k-1} (A^+_i/A^-_i)$. Кроме того, для любого натурального $s$ такого, что $s \leqslant p$, верно неравенство $A_*^- \cdot A^+_s/A^-_s < A^+_{\mathrm{I}}$. Если же $p < s \leqslant k-1$, то верно неравенство $A_*^- \cdot A^+_s/A^-_s < A^+_{\mathrm{II}}$. Наконец, для всех $1 \leqslant s \leqslant k-1$ верно неравенство $A_*^- \cdot A^+_s/A^-_s < A_*^{+}$. Случай $\delta=1$. Рассмотрим лес $F'=(p-2)P_2 \cup T'_{\mathrm{I}} \cup T'_{\mathrm{II}}$, в котором компонента $T'_{\mathrm{I}}$ есть результат присоединения к концу пути $P_2$ лесов $F_1,\dots,F_p$ (здесь и далее подразумевается, что вершина пути соединяется с теми и только теми вершинами леса $F_i$, которые были смежны с вершиной $w_i$ в дереве $T$), а компонента $T'_{\mathrm{II}}$ есть результат присоединения к концу пути $P_2$ лесов $F_{p+1},\dots,F_{2p}$. Тогда
$$
\begin{equation*}
\partial_M(F')=2^{p-2}( A_*+A^+_{\mathrm{I}}+A^+_{\mathrm{II}}+A_*^+).
\end{equation*}
\notag
$$
Нетрудно проверить, что имеет место неравенство $\partial_M(T) < \partial_M(F')$. По лемме 5 дерево $T$ не максимально, противоречие. Случай $\delta=0$. Рассмотрим лес $F''=(p-3)P_2 \cup T''$, в котором компонента $T''$ есть результат присоединения к одному из предлистьев пути $P_7$ лесов $F_1,\dots,F_p$, а к другому из предлистьев этого же пути лесов $F_{p+1},\dots,F_{2p-1}$. Тогда
$$
\begin{equation*}
\partial_M(F'')=2^{p-3}(A_*+2A^+_{\mathrm{I}}+2A^+_{\mathrm{II}}+3A_*^+), \qquad \partial_M(T)< \partial_M(F'').
\end{equation*}
\notag
$$
По лемме 5 дерево $T$ не максимально, противоречие. Доказательство. Очевидно, что при $n < 6$ условие теоремы выполнено. Предположим, что при $n \geqslant 6$ существуют $n$-вершинные деревья, содержащие хотя бы $1.4205^n$ НДМ. Выберем среди них дерево $T$ с наименьшим количеством вершин (мы можем считать, что $T$ максимально). По следствию 1 $T$ неразделимо и не содержит пустых вершин, тогда по лемме 6 существует единственное $\mathcal{S}$-разбиение $\mathcal{S}(T)$, которое по лемме 8 содержит только множества из 2 и 3 вершин. Рассмотрим некоторый диаметральный путь $X=x_1x_2x_3x_4x_5\dots$ в $T$. Поскольку $T$ неразделимо, то $\{x_3,x_4,x_5\}=N[x_4] \in \mathcal{S}(T)$ и $\operatorname{deg}(x_4)=2$, а вершины $x_3$ и $x_5$ смежны с $a=\operatorname{deg}(x_3) - 1$ и $b=\operatorname{deg}(x_5) - 2$ предлистьями степени 2 соответственно. Обозначим через $T'$ результат удаления из $T$ всех предлистьев степени 2, смежных с вершинами $x_3$ и $x_5$, всех смежных с ними листьев, а также вершины $x_3$. По предположению $\partial_M(T') < 1.4205^{|V(T')|}$, откуда Покажем, что имеет место неравенство
$$
\begin{equation*}
2^{a+b+1} \cdot \partial_M^+(T',x_4)+(2^a-1)\cdot 2^b \cdot \partial_M^+(T',x_5) < 1.4205^{2a+2b+1} (\partial_M^+(T',x_4)+\partial_M^+(T',x_5)).
\end{equation*}
\notag
$$
Очевидно, что при любых $a,b \geqslant 0$ имеет место неравенство $1.4205^{2a+2b+1} > (2^a-1)2^b$. Кроме того, поскольку в дереве $T'$ вершина $x_4$ является листом, то $\partial_M^+(T',x_4) \leqslant \partial_M^+(T',x_5)$. Таким образом, достаточно рассмотреть случай, когда $\partial_M^+(T',x_4)=\partial_M^+(T',x_5)$. Покажем, что имеет место неравенство Разделим на 2 обе части неравенства и рассмотрим функцию Нетрудно проверить, что $\min_{x,y \geqslant 0}f(x,y) > 0$, откуда Полученное противоречие означает, что $n$-вершинных деревьев, содержащих хотя бы $1.4205^n$ НДМ, не существует. Теорема доказана.
Цитирование в формате AMSBIB
\RBibitem{Tal23} |
|
|||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|