| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) О деревьях диаметра 5 с максимальным количеством паросочетаний Н. А. Кузьмин, Д. С. Малышев Национальный исследовательский университет ``Высшая школа экономики'', г. Нижний Новгород
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 2, Pages DOI: https://doi.org/10.4213/sm9745e 
Реферативные базы данных:
    § 1. ВведениеХимические соединения часто рассматриваются в форме молекулярных графов, где атомам соответствуют вершины графа, а связям между ними – ребра графа. При этом свойства химических соединений описываются в терминах топологических индексов, которые представляют собой некоторые инварианты графов относительно переобозначения вершин и которые позволяют аналитически исследовать некоторые аспекты химической структуры вещества. В настоящей работе рассматриваются только обыкновенные графы, т.е. неориентированные, непомеченные графы без петель и кратных ребер. Паросочетанием графа называется произвольное множество попарно не смежных его ребер, в том числе и пустое. Топологический индекс Хосойи, предложенный в пионерской работе [1], для графа $G$ определяется как количество его паросочетаний и обозначается через $z(G)$. Значения индекса Хосойи определяют некоторые физико-химические свойства соответствующих химических соединений, в частности, точки кипения алканов, энергию сопряженных $\pi$-электронных систем, см., например, обзоры [2]–[4]. Поскольку топологические индексы определяют ту или иную энергию химических соединений, то интересна задача по выявлению графов из заданных классов с экстремальным (минимальным или максимальным) значением того или иного топологического индекса. В статье рассматриваются только обыкновенные графы, т.е. неориентированные, непомеченные графы без петель и кратных ребер. Напомним, что эксцентриситетом вершины графа называется максимальное из расстояний между ней и остальными вершинами. Радиус и диаметр графа – минимальный и максимальный из эксцентриситетов его вершин. Понятно, что единственным $n$-вершинным деревом радиуса $1$ будет только $n$-звезда, имеющая ровно $n$ паросочетаний. Задача о поиске деревьев диаметра $3$ фиксированного размера с максимальным значением индекса Хосойи также тривиальна. В работе [5] полностью описаны деревья радиуса $2$ на $n$ вершинах с наибольшим количеством паросочетаний. В настоящей работе рассматривается и решается задача максимизации индекса Хосойи в $n$-вершинных деревьях диаметра $5$, которая, по сведениям авторов, является открытой. Любое $n$-вершинное дерево диаметра $5$ c наибольшим количеством паросочетаний назовем максимальным. Оказалось, что при любом $n\geqslant 5$ данное дерево является единственным. § 2. Некоторые определения, обозначения и фактыНапомним, что листом графа называется произвольная его вершина степени 1. Центральная вершина графа – вершина с минимальным эксцентриситетом. Лист, смежный с центральной вершиной графа, будем называть центральным листом. Центр графа – множество его центральных вершин. Согласно известной теореме Жордана центр любого дерева состоит либо из одной вершины, либо из двух смежных вершин. Количество паросочетаний (включая и пустое) в графе $G$ будем обозначать через $z(G)$. Пусть $A,B\subseteq V(G)$ и $A\cap B=\varnothing$. Через $z(G,A,B)$ обозначается количество паросочетаний графа $G$, покрывающих все вершины из $A$ и не покрывающих ни одной вершины из $B$. Пусть $G$ – некоторый граф, а $H$ – его подграф. Любое подмножество $S\subseteq V(H)$ такое, что никакая вершина из $V(G)\setminus V(H)$ не смежна ни с какой вершиной из $V(H)\setminus S$, назовем $H$-отделяющим. Пусть $S$ – некоторое $H$-отделяющее множество. Через $G_S$ обозначим граф $((V(G)\setminus V(H))\cup S,E(G)\setminus E(H))$. В работе [6] (см. [6; лемма 1]) было доказано следующее утверждение. Предположим, что некоторые графы $G^1$ и $G^2$ содержат подграфы $H_1$ и $H_2$, причем одновременно выполнены следующие два условия: 1) некоторое подмножество $S\subseteq V(G^1)\cap V(G^2)$ одновременно является и $H_1$-отделяющим и $H_2$-отделяющим; 2) подграфы $G^1_{S}$ и $G^2_{S}$ изоморфны. Тем самым равенство $z(G^1_S,S',S\setminus S')=z(G^2_S,S',S\setminus S')$ имеет место при любом $S'\subseteq S$. Если для любого подмножества $S'\subseteq S$ справедливо $z(H_2\setminus S')\geqslant z(H_1\setminus S')$, причем для некоторого $\widetilde{S'}\subseteq S$ выполнено
$$
\begin{equation*}
z(H_2\setminus \widetilde{S'})>z(H_1\setminus \widetilde{S'}),\qquad z(G^1_S,\widetilde{S'},S\setminus \widetilde{S'})\neq 0,
\end{equation*}
\notag
$$
то $z(G^2)>z(G^1)$, что следует из леммы 2.1. Это замечание оказывается полезным для доказательства того факта, что то или иное преобразование графов увеличивает индекс Хосойи. Оно и связанные с ним обозначения будут использоваться в настоящей работе.
§ 3. Формулировка основных результатовРассмотрим дерево диаметра 5, представленное на рис. 1. Уточним, что $l_i\in \{0,1\}$, где $l_i=1$ тогда и только тогда, когда соответствующий лист содержится в дереве. Через $a_i$ и $b_i$ обозначено количество соответствующих вхождений 2-путей и 3-путей в дерево. 3.1. Описание максимальных деревьев при $n\geqslant 105$При $n\geqslant 105$ верно следующее утверждение. Теорема 3.1. Пусть $n=6k+(3l+m)$, где $l \in \{0, 1\}, m \in \{0, 1, 2\}$. Тогда, если $n \geqslant 105$, то максимальное $n$-вершинное дерево диаметра 5 единственно и имеет вид, представленный на рис. 1, где 3.2. Описание максимальных деревьев при $n\leqslant 104$При $n \leqslant 5$ деревьев диаметра 5 не существует. С целью выявления максимальных деревьев при $6 \leqslant n\leqslant 104$ был проведен вычислительный эксперимент по поиску оптимальных целочисленных $l_1$, $l_2$, $a_1$, $a_2$, $b_1$ и $b_2$, показавший, что центральный лист в максимальном дереве может содержаться только при $6 \leqslant n \leqslant 13$, соответствующие значения параметров представлены в табл. 1. Таблица 1.Значения параметров, соответствующие максимальным деревьям при $6\leqslant n\leqslant 13$ При $14 \leqslant n \leqslant 104$ центральных листьев в дереве не содержится, т.е. $l_1=l_2=0$. Соответствующие значения оптимальных параметров представлены в табл. 2. Таблица 2.Значения параметров, соответствующие максимальным деревьям при $14\leqslant n\leqslant 104$ § 4. Некоторые известные преобразования графов, увеличивающие индекс ХосойиВ работе [5] были предложены следующие преобразования графов и доказаны (см. [5; леммы 3.1, 3.4 и 3.5]) соответствующие утверждения. Пусть граф $G_1$ состоит из подграфов $G'_S$ и $G''_S$ и отделенного от них вершинами $s_1$ и $s_2$ порожденного 3-пути $H_1=(v,s_2,s_1)$, а граф $G_2$ состоит из подграфов $G'_S$ и $G''_S$ и отделенного от них вершинами $s_1$ и $s_2$ порожденного 3-пути $H_2=(s_2,v,s_1)$ так, как показано на рис. 2. Пусть граф $G_1$ состоит из подграфа $G_S$ и отделенной от него вершиной $s_1$ звезды $H_1$ с $q+1$ листьями (рис. 3). В случае четного $q$ граф $G_2$ состоит из подграфа $G_S$ и отделенного от него вершиной $s_1$ подграфа $H_2$ так, как показано на рис. 4. В случае нечетного $q$ граф $G_2$ состоит из подграфа $G_S$ и отделенного от него вершиной $s_1$ подграфа $H_2$ так, как показано на рис. 5. § 5. Некоторые новые преобразования графов, увеличивающие индекс ХосойиПусть граф $G_1$ состоит из подграфа $G_s$ и отделенного от него вершинами $s_1$ и $s_2$ порожденного 4-пути $H_1$, а граф $G_2$ состоит из подграфа $G_s$ и отделенного от него вершинами $s_1$ и $s_2$ порожденного 4-пути $H_2$ так, как показано на рис. 6. Доказательство. Несложно проверить, что
$$
\begin{equation*}
\begin{gathered} \, z(H_1)=z(H_2)=5, \qquad z(H_1 \setminus s_2) =z(H_1 \setminus s_1)=z(H_2 \setminus s_2)=2, \\ z(H_2 \setminus s_1)=3, \qquad z(H_1 \setminus \{s_1, s_2\})=1, \qquad z(H_2 \setminus \{s_1, s_2\})=2. \end{gathered}
\end{equation*}
\notag
$$
Тогда по лемме 2.1 выполнено Лемма доказана. Пусть граф $G_1$ состоит из подграфа $G_s$ и отделенной от него вершиной $s_1$ вилки $H_1$, а граф $G_2$ состоит из подграфа $G_s$ и отделенной от него вершиной $s_1$ вилки $H_2$ так, как показано на рис. 7. Доказательство. Несложно проверить, что
$$
\begin{equation*}
z(H_1)=7, \qquad z(H_2)=8, \qquad z(H_1 \setminus s_1)=3, \qquad z(H_2 \setminus s_1)= 4.
\end{equation*}
\notag
$$
Тогда по лемме 2.1 выполнено
Лемма доказана. Пусть граф $G_1$ состоит из подграфа $G_s$ и отделенного от него вершинами $s_1$ и $s_2$ подграфа $H_1$, а граф $G_2$ состоит из подграфа $G_s$ и отделенного от него вершинами $s_1$ и $s_2$ подграфа $H_2$ так, как показано на рис. 8. Доказательство. Нетрудно проверить, что
$$
\begin{equation*}
\begin{gathered} \, z(H_1)=11, \quad z(H_2)=13, \quad z(H_1 \setminus s_1)=z(H_2 \setminus s_1)=6, \quad z(H_1 \setminus s_2)=4, \\ z(H_2 \setminus s_2)=6,\quad z(H_1 \setminus \{s_1, s_2\})=3, \quad z(H_2 \setminus \{s_1, s_2\})=4. \end{gathered}
\end{equation*}
\notag
$$
Тогда по лемме 2.1 выполнено Лемма доказана. § 6. О свойствах максимальных деревьев диаметра 56.1. Структура максимальных деревьев диаметра 5 и некоторые ее свойстваИз лемм 4.1–4.3 следует, что каждое максимальное дерево диаметра 5 имеет вид, представленный на рис. 1. Индекс Хосойи такого дерева обозначим через $f(l_1,l_2,a_1,a_2,b_1,b_2)$. Очевидно, что если в данном дереве имеется $n$ вершин, то Лемма 6.1. В любом максимальном дереве выполнены следующие свойства. 1. Если дерево содержит центральный лист, то он единственный и $b_1=b_2=0$. 2. Если $n$ – четное, то дерево не содержит центральных листьев. Доказательство. Из леммы 5.1 следует, что в любом максимальном дереве либо $l_1=0$, либо $l_2=0$. Если в нем есть центральные листья, то можно считать, что $l_1=1$. Из лемм 5.2 и 5.3 следует, что $b_1=b_2=0$. Подставив эти значения в равенство (6.1), получим, что $2a_1+2a_2=n-3$, что невозможно в случае четного $n$. Лемма доказана. 6.2. Случай наличия центрального листаПредположим, что $l_1=1$. Тогда по лемме 6.1 имеем, что $l_2=0,b_1=b_2=0$ и $n$ является нечетным. Пусть $n=4k+r$, где $r \in \{1, 3\}$, $g(a_1, a_2)=f(1, 0, a_1, a_2, 0, 0)$. Тогда задача поиска максимальных деревьев, содержащих центральный лист (если таковые существуют), сводится к нахождению максимума функции $g$ при ограничении Нетрудно проверить, что верно следующее равенство: Подставив $a_1=(n-3)/{2}-a_2$ в функцию $g$, получим
$$
\begin{equation*}
g(a_2)=2^{(n-3)/2-2}\biggl (-a_2^2+\biggl (2+\frac{n-3}{2}\biggr) a_2+ (n+9)\biggr).
\end{equation*}
\notag
$$
Очевидно, что максимум этой функции находится в точке $a_2=1+(n-3)/4$. Прямой подстановкой этого значения в функцию доказывается следующее утверждение. Лемма 6.2. Если выполняется (6.2), то 6.3. Случай отсутствия центрального листаПусть $g(a_1, a_2, b_1, b_2)=f(0, 0, a_1, a_2, b_1, b_2)$. Тогда задача поиска максимальных деревьев, не содержащих центральных листьев (если таковые существуют), сводится к нахождению максимума функции $g$ при ограничении Не уменьшая общности можем считать, что $a_1 \geqslant a_2$, поэтому далее в этом пункте всегда будем предполагать, что это неравенство выполняется. Нетрудно проверить, что верно следующее равенство:
$$
\begin{equation*}
g(a_1, a_2, b_1, b_2)=2^{a_1+a_2-2} 3^{b_1+b_2-2}\bigl((3a_1+2b_1+6) (3a_2+2b_2+6)+36\bigr).
\end{equation*}
\notag
$$
Доказательство. Нетрудно проверить, что В силу того, что $a_1 \geqslant a_2$ и $b_1 \geqslant b_2$, получаем Откуда следует, что $g(a_1, a_2, b_2, b_1)-g(a_1, a_2, b_1, b_2) \geqslant 0$. Лемма доказана. Далее будем считать, что $b_2 \geqslant b_1$. Также введем обозначения $c_1=a_1-a_2$, $c_2=b_2-b_1$. Лемма 6.4. Выполнены следующие утверждения. 1. Если $c_1 >(2/3)c_2+1$, то $g(a_1-1, a_2+1, b_1, b_2) > g(a_1, a_2, b_1, b_2)$. 2. Если $c_1 < (2/3)c_2-1$, то $g(a_1+1, a_2-1, b_1, b_2) > g(a_1, a_2, b_1, b_2)$. 3. Если $c_1 > (2/3)(c_2+1)$, то $g(a_1, a_2, b_1-1, b_2+1) > g(a_1, a_2, b_1, b_2)$. 4. Если $c_1 < (2/3)(c_2-1)$, то $g(a_1, a_2, b_1+1, b_2-1) > g(a_1, a_2, b_1, b_2)$. Доказательство. Нетрудно проверить, что Очевидно, что $3(a_1-a_2-1)-2(b_2-b_1)=3(c_1-1)-2c_2 > 0$. Пункты 2–4 доказываются аналогично. Лемма доказана. Пусть $x_k=(a_1-k, a_2+k, b_1, b_2)$, $c_1(x_k)=(a_1-k)-(a_2+k)$. Очевидно, что $c_1(x_{k-1})- 2=c_1(x_k)$. Тогда если для $x_0$ верно, что $c_1(x_0) > \frac{2}{3}c_2+1$, то по п. 1 леммы 6.4 существует такое $k$, что $\frac{2}{3}c_2-1 \leqslant c_1(x_k) \leqslant \frac{2}{3}c_2+1$ и $g(x_k) > g(x_0)$. В то же время пусть $y_k=(a_1+k, a_2-k, b_1, b_2)$, $c_1(y_k)=(a_1+k)-(a_2-k)$. Очевидно, что $c_1(y_{k-1})+2=c_1(y_k)$. Тогда если для $y_0$ верно, что $c_1(y_0) < \frac{2}{3}c_2-1$, то по п. 2 леммы 6.4 существует такое $k$, что $\frac{2}{3}c_2-1 \leqslant c_1(y_k) \leqslant \frac{2}{3}c_2+1$ и $g(y_k) > g(y_0)$. Тем самым доказано, что для любого набора параметров $x=(a_1, a_2, b_1, b_2)$ такого, что $c_1 \notin [\frac{2}{3}c_2-1, \frac{2}{3}c_2+1]$, существует набор $x'=(a'_1, a'_2, b'_1, b'_2)$ такой, что $c'_1 \in [\frac{2}{3}c'_2-1, \frac{2}{3}c'_2+1]$ и $g(x') > g(x)$. То есть для любого оптимального набора параметров $(a_1, a_2, b_1, b_2)$ выполняется неравенство
$$
\begin{equation}
\frac{2}{3}\, c_2-1 \leqslant c_1 \leqslant \frac{2}{3}\, c_2+1.
\end{equation}
\tag{6.3}
$$
Аналогично, используя п. 3, 4 леммы 6.4, можно доказать, что для любого такого набора будет также выполняться неравенство
$$
\begin{equation}
\frac{2}{3}(c_2-1) \leqslant c_1 \leqslant \frac{2}{3}(c_2+1).
\end{equation}
\tag{6.4}
$$
Очевидно, что из (6.4) следует (6.3). По определению $c_1$ и $c_2$ неравенство (6.4) эквивалентно неравенству
$$
\begin{equation*}
3a_2+2b_2-2 \leqslant 3a_1+2b_1 \leqslant 3a_2+2b_2+2 .
\end{equation*}
\notag
$$
Доказательство. Очевидно, что Поскольку $n-2=2a_1+2a_2+3b_1+3b_2$, получаем, что Лемма доказана. Лемма 6.7. Если $n \geqslant 122$, $a_1 \geqslant 2$, $a_2 \geqslant 1$ и выполняется (6.5), то Доказательство. Нетрудно проверить, что
$$
\begin{equation*}
\begin{aligned} \, &\frac{g(a_1-2, a_2-1, b_1+1, b_2+1)-g(a_1, a_2, b_1, b_2)}{2^{a_1+a_2-5}\, 3^{b_1+b_2- 2}} \\ &\qquad=(3a_1+2b_1-3) (3a_2+2b_2-30)-252. \end{aligned}
\end{equation*}
\notag
$$
По лемме 6.6 имеем $(3a_1+2b_1)+(3a_2+2b_2) \geqslant 80$. Тогда из неравенства (6.5) следует, что $(3a_1+2b_1)\geqslant 39$, $(3a_2+2b_2) \geqslant 38$. Таким образом, верно неравенство $(3a_1+2b_1-3) (3a_2+2b_2-30) \geqslant 280$. Лемма доказана. Лемма 6.8. Если $n \geqslant 137$, $a_1 \geqslant 3$ и выполняется (6.5), то Доказательство. Нетрудно проверить, что
$$
\begin{equation*}
\frac{g(a_1-3, 0, b_1+1, b_2+1)-g(a_1, 0, b_1, b_2)}{2^{a_1-5}\, 3^{b_1+b_2-2}} = (3a_1+2b_1- 57) (2b_2+24)+1044.
\end{equation*}
\notag
$$
По лемме 6.6 имеем $(3a_1+2b_1)+2b_2 \geqslant 90$. Тогда из неравенства (6.5) следует, что $(3a_1+2b_1-57)\geqslant -14$. Тогда $(3a_1+2b_1-57) (2b_2+24) \geqslant-994$. Лемма доказана. § 7. Доказательство теоремы 3.1Предположим, что максимальное дерево не содержит центральных листьев и $a_1 \geqslant a_2$. Тогда из лемм 6.7 и 6.8 следует, что $(a_1, a_2) \in \{(0, 0), (1, 0), (1, 1), (2, 0)\}$ и поэтому $c_1 \in \{0, 1, 2\}$. Из неравенства (6.5) получаем, что если $c_1=0$, то $c_2 \in \{0, 1\}$, если $c_1=1$, то $c_2 \in \{1, 2\}$, если $c_1=2$, то $c_2 \in \{2, 3, 4\}$. Пусть $n=6k+r$, где $r \in \{0, 1, 2, 3, 4, 5\}$, тогда $2a_1+2a_2+3b_1+3b_2=6k+r-2$. Если $r=0$, то в силу целочисленности параметров $b_1$ и $b_2$ либо $a_1=a_2=1$, тогда $b_1=b_2=k- 1$, либо $a_1=2$, $a_2=0$, тогда по лемме 6.3 либо $b_1=k-2$, $b_2=k$, либо $b_1=k-3$, $b_2=k+1$. Несложно проверить, что
$$
\begin{equation*}
\begin{gathered} \, g(2, 0, k-2, k)=g(2, 0, k-3, k+1)=3^{2k-4} \bigl((2k+8) (2k+6)+36\bigr), \\ g(1, 1, k-2, k)=3^{2k-4} ((2k+7)^2+36). \end{gathered}
\end{equation*}
\notag
$$
Очевидно, что Если $r=1$, то в силу целочисленности параметров $b_1$ и $b_2$ получим, что $a_1=1$, $a_2=0$, тогда по лемме 6.3 $b_1=k-1$, $b_2=k$. Если $r=2$, то в силу целочисленности параметров $b_1$ и $b_2$ получим, что $a_1=a_2=0$, тогда $b_1=b_2=k$. Если $r=3$, то в силу целочисленности параметров $b_1$ и $b_2$ либо $a_1=a_2=1$, тогда $b_1=b_2=k- 1$, либо $a_1=2$, $a_2=0$, тогда по лемме 6.3 выполнено $b_1=k-2$, $b_2=k+1$. Несложно проверить, что
$$
\begin{equation*}
\begin{gathered} \, g(2, 0, k-2, k+1)=3^{2k-4} ((2k+8)^2+36), \\ g(1, 1, k-2, k)=3^{2k-4}\bigl((2k+7) (2k+9)+36\bigr). \end{gathered}
\end{equation*}
\notag
$$
Откуда следует, что Если $r=4$, то в силу целочисленности параметров $b_1$ и $b_2$ получим, что $a_1=1$, $a_2=0$, тогда по лемме 6.3 имеем $b_1=k-1$, $b_2=k+1$. Если $r=5$, то в силу целочисленности параметров $b_1$ и $b_2$ получим, что $a_1=a_2=0$, тогда по лемме 6.3 имеем $b_1=k$, $b_2=k+1$. Из леммы 6.1 и доказанного выше следует результат теоремы для $r\,{\in}\, \{0, 2, 4\}$. В случае $r \in \{1, 3, 5\}$ по лемме 6.1 максимальное дерево может содержать единственный центральный лист, поэтому сравним соответствующие максимальные значения функций $g$. Напомним, что по лемме 6.2 выполнено Если $r=1$, то по доказанному выше максимальное значение функции $g$
$$
\begin{equation*}
g(1, 0, k-1, k)=\frac{1}{2}\, 3^{(n-16)/3} (n^2+37n+664).
\end{equation*}
\notag
$$
Если $r=3$, то по доказанному выше максимальное значение функции $g$ Если $r=5$, то по доказанному выше максимальное значение функции $g$
$$
\begin{equation*}
g(0, 0, k, k+1)=\frac{1}{4}\, 3^{(n-14)/3} (n^2+32n+521).
\end{equation*}
\notag
$$
Нетрудно проверить, что уже при $n \geqslant 127$
$$
\begin{equation*}
g_l(a_1, a_2)< g(1, 0, k-1, k), g(2, 0, k-2, k), g(0, 0, k, k+1).
\end{equation*}
\notag
$$
Тем самым теорема доказана для $n \geqslant 137$. Проведя компьютерные вычисления, несложно убедится, что данная теорема выполняется уже при $n \geqslant 105$. Теорема доказана.
Цитирование в формате AMSBIB
\RBibitem{KuzMal23} |
|
||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|