| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях) О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний Н. А. Кузьминab, Д. С. Малышевa  a Национальный исследовательский университет – Высшая школа экономики в Нижнем Новгороде b Санкт-Петербургский государственный университет
Английская версия:
Mathematical Notes, 2024, Volume 115, Issue 3, Pages DOI: https://doi.org/10.1134/S0001434624030064 
Реферативные базы данных:
   1. ВведениеХимические соединения принято рассматривать в форме молекулярных графов, где атомам соответствуют вершины графа, а связям между ними – ребра графа. При этом свойства химических соединений описываются в терминах топологических индексов, которые представляют собой некоторые инварианты графов относительно переобозначения вершин и которые позволяют аналитически исследовать ряд аспектов химической структуры вещества. Например, значение индекса Винера, который определяется как сумма длин кратчайших путей между всеми парами вершин заданного графа, связано с точками кипения парафинов [1]. В данной работе, если явным образом не оговаривается противное, рассматриваются только обыкновенные графы, т.е. неориентированные, непомеченные графы без петель и кратных ребер. Паросочетанием графа называется произвольное множество попарно несмежных его ребер. Индекс Хосойи, называемый еще $z$-индексом, предложенный в работе [2] японским химиком Харуо Хосойя, определяется как количество его паросочетаний, включая и пустое. Для графа $G$ значение этого индекса будем обозначать через $z(G)$. Значения индекса Хосойи определяют некоторые физико-химические свойства соответствующих химических соединений, в частности, точки кипения алканов, энергию сопряженных $\pi$-электронных систем, см., например, обзоры [3]–[6]. Поскольку топологические индексы определяют ту или иную “энергию” химических соединений, то интересна задача по выявлению графов из заданных классов с экстремальным (минимальным или максимальным) значением того или иного индекса. По всей видимости, исторически первый результат о максимизации индекса Хосойи в классах графов был получен И. Гутманом в работе [7]. Именно там было показано, что среди ациклических полиэнов максимальное значение $z$-индекса имеет линейный изомер. В графовых терминах это можно переформулировать (и несколько обобщить) так: для любого $n$ в классе $n$-вершинных деревьев, т.е. связных ациклических графов, единственным максимальным графом является $n$-путь. Путь на $n$ вершинах называется $n$-путем, который обозначается через $P_n$. Структура оптимального дерева мотивировала исследователей варьировать ассоциированные с ним ограниченные параметры (количество листьев, максимальную степень, наличие совершенного паросочетания и т.д.), выявлять соответствующие максимальные деревья и находить значение $z$-индекса на них. Значительный интерес также вызывают аналогичные постановки задач для недревесных случаев. Отметим некоторые работы [7]–[19] в этой области. В той же работе [7] было доказано, что для любого $n\geqslant 6$ в классе $n$-вершинных деревьев предмаксимальный граф единственен и получается соединением ребрами листа $(n-4)$-пути с концевыми вершинами двух $2$-путей. Вершина степени один графа называется листом или висячей вершиной. Данный граф имеет три листа и поэтому является максимальным элементом класса $n$-вершинных деревьев с тремя листьями. Случай $n$-вершинных деревьев с четырьмя листьями рассматривался в работе [12]. Оказалось, что для любого $n\geqslant 11$ максимальное дерево не единственно. Первое получается соединением ребрами каждой висячей вершины $(n-8)$-пути с двумя $2$-путями. А второе получается присоединением ребрами $2$-пути к первой и $(n-8)$-пути ко второй центральным вершинам $6$-пути. Данная работа является продолжением работ [7] и [12]. А именно, в ней рассматривается и решается задача максимизации $z$-индекса в 5- и 6-листных $n$-вершинных деревьях. Оказалось, что для любого $n\geqslant 20$ имеется ровно три максимальных 5-листных $n$-вершинных дерева и что для любого $n\geqslant 26$ имеется ровно шесть максимальных 6-листных $n$-вершинных деревьев. 2. Некоторые определения, обозначения и фактыГраф $H$ называется подграфом графа $G$, если $H$ получается из $G$ удалением вершин и ребер, где операция удаления вершины подразумевает удаление всех инцидентных ей ребер. Граф $H$ называется порожденным подграфом графа $G$, если $H$ получается из $G$ только удалениями вершин. Для графа $G$ и его подмножества $V'\subseteq V(G)$ через $G\setminus V'$ обозначается результат удаления из $G$ всех вершин подмножества $V'$. Степень вершины $v$ графа $G$ обозначается через $\deg_G(v)$. Изоморфизм графов $G_1$ и $G_2$ обозначается через $G_1\cong G_2$. Для любых графов $G_1$ и $G_2$ c непересекающимися множествами вершин выполнено $z(G_1+G_2)=z(G_1)\cdot z(G_2)$, где $G_1+G_2$ – дизъюнктное объединение $G_1$ и $G_2$. Пусть $G$ – граф, а $e$ – некоторое его ребро. Равенство где $z_{+}(G,e)$ и $z_{-}(G,e)$ – количества паросочетаний $G$, содержащих и не содержащих $e$ соответственно, будем называть разложением $z(G)$ по ребру $e$. Например, воспользовавшись этим разложением, нетрудно установить, что при любом $i$ индекс Хосойи $i$-пути равен $F_{i+1}$, где
$$
\begin{equation*}
F_0=0, \qquad F_1=F_2=1, \qquad F_{i}=F_{i-1}+F_{i-2}, \quad i\geqslant 3\ -\text{ последовательность чисел,}
\end{equation*}
\notag
$$
известная как последовательность Фибоначчи. Важным свойством чисел Фибоначчи, которое мы будем использовать в данной работе, является следующее тождество:
$$
\begin{equation*}
F_{n+m}=F_{n+1}\cdot F_{m}+F_{n}\cdot F_{m-1}, \qquad n\geqslant 0, \quad m\geqslant 1.
\end{equation*}
\notag
$$
Оно имеет простое комбинаторное обоснование. C одной стороны, $z$-индекс $(n+m- 1)$-пути равен $F_{n+m}$. С другой стороны, разложив его по $n$-му ребру данного пути, получаем $F_{n+1}\cdot F_{m}+F_{n}\cdot F_{m-1}$. В работе [18] был предложен новый метод поиска графов из заданных классов, имеющих максимальное значение $z$-индекса, основанный на специальных локальных преобразованиях. Далее мы представим описание этого метода. Пусть $G$ – некоторый граф, $A$ и $B$ – некоторые непересекающиеся подмножества его вершин. Через $z(G,A,B)$ обозначается количество паросочетаний графа $G$, покрывающих все вершины из $A$ и не покрывающих ни одной вершины из $B$. Пусть $H$ – подграф графа $G$. Любое подмножество $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))$. Следующее утверждение является леммой 1 из работы [18]. Предположим, что $G_S$ состоит из двух компонент связности $G^1_S$ и $G^2_S$. Положим $S_1=V(G^1_S)\cap S$, $S_2=V(G^2_S)\cap S$. Тогда для любого $S' \subseteq S$ справедливо
$$
\begin{equation*}
z(G_S,S',S\setminus S')=z(G^1_S,S_1\cap S',S_1\setminus S') \cdot z(G^2_S,S_2\cap S',S_2\setminus S'),
\end{equation*}
\notag
$$
откуда получаем
$$
\begin{equation*}
z(G)=\sum_{S' \subseteq S}=z(G^1_S,S_1\cap S',S_1\setminus S') \cdot z(G^2_S,S_2\cap S',S_2\setminus S')\cdot z(H\setminus S').
\end{equation*}
\notag
$$
Пусть $G^{(0)}$ – некоторый граф, а $G^{(k)}$ – результат операции $k$-подразбиения некоторого его ребра. Данная операция состоит в удалении ребра $ab$ из графа, добавления вершин $c_1,\dots,c_k$, а также добавления ребер $ac_1,c_1c_2,\dots,c_{k-1}c_k,c_kb$. Равенство $z(G^{(k)})=z(G^{(k-1)})+z(G^{(k-2)})$, верное при каждом $k\geqslant 2$, является следствием из леммы 1, см. работу [18]. Предположим, что графы $G^1$ и $G^2$ содержат подграфы $H_1$ и $H_2$, соответственно, причем некоторое подмножество $S\subseteq V(G^1)\cap V(G^2)$ одновременно является и $H_1$-отделяющим и $H_2$-отделяющим, а также $G^1_{S}$ и $G^2_{S}$ изоморфны. Тогда по лемме 1 выполнено
$$
\begin{equation*}
z(G^2)-z(G^1)=\sum_{S' \subseteq S}z(G^1_S,S',S\setminus S')\cdot \Delta(S'),
\end{equation*}
\notag
$$
где $\Delta(S')=z(H'\setminus S')-z(H\setminus S')$. Если для любого подмножества $S'\subseteq S$ справедливо $\Delta(S')\geqslant 0$, причем для некоторого $\widetilde{S'}\subseteq S$ выполнено
$$
\begin{equation*}
\Delta(\widetilde{S'})>0, \qquad z(G^1_S,\widetilde{S'},S\setminus \widetilde{S'})\neq 0,
\end{equation*}
\notag
$$
то $z(G^2)>z(G^1)$. Это замечание оказывается полезным для доказательства того факта, что то или иное конкретное преобразование графов увеличивает $z$-индекс. В этой работе мы предлагаем несколько новых локальных преобразований, которые увеличивают индекс Хосойи, а также сохраняют количества вершин и листьев графа. 3. Стяжки деревьев с 5 или 6 листьямиПсевдограф (т.е. допускаются петли и кратные ребра) $G'$ называется стяжкой обыкновенного графа $G$, если $G$ получается подразбиениями ребер $G'$ и $G'$ содержит минимальное количество вершин. Ясно, что стяжка любого обыкновенного графа существует и единственна. Также понятно, что для каждого связного графа $G$, отличного от простого цикла, имеем
$$
\begin{equation*}
V(G')=\{v\in V(G)\colon \deg_G(v)\neq 2\}, \qquad \forall\, v\in V(G') \quad [\deg_{G'}(v)=\deg_{G}(v)].
\end{equation*}
\notag
$$
Нетрудно перебрать всевозможные стяжки деревьев с 5 или с 6 листьями. Они изображены на рис. 1 и 2. Тем самым, каждое дерево с 5 или с 6 листьями получается подразбиениями некоторых ребер деревьев, изображенных на рис. 1 и 2. 4. Формулировка основного результатаПусть $a_i,b_j,c_k$ – натуральные числа, причем выполнено
$$
\begin{equation*}
\sum_{i=1}^{7} a_i - 1=\sum_{j=1}^{9} b_j - 2=\sum_{k=1}^{9} c_ k -2= n.
\end{equation*}
\notag
$$
Через $T_5(a_1,\dots,a_7)$, $T^1_6(b_1,\dots,b_9)$ и $T^2_6(c_1,\dots,c_9)$ обозначим деревья, изображенные на рис. 3 и 4 соответственно. Справедливо следующее утверждение, которое является основным в данной работе. Теорема 1. Для любого $n\geqslant 20$ множество максимальных 5-листных деревьев состоит из следующих трех деревьев: Для любого $n\geqslant 26$ множество максимальных 6-листных деревьев образовано двумя деревьями $T^1_6(n-14,2,\dots,2)$ и $T^1_6(2,n-14,2,\dots,2)$, а также следующими четырьмя деревьями: 5. Преобразования графов, увеличивающие $z$-индексПусть $k=p+q+ 1 \geqslant 4$, где $p, q \geqslant 1$ – натуральные числа. Предположим, что графы $G_1$ и $G_2$ состоят из подграфа $G_S$ и отделенного от него вершиной $s_1$ порожденного подграфа $P_{k}$ так, как показано на рис. 5. Преобразование I переводит $G_1$ в $G_2$. Преобразование I было предложено в работе [12], где также было доказано следующее утверждение. Пусть $k=t+p+q \geqslant 7$, где $t \geqslant 3$ и $p, q \geqslant 1$ – натуральные числа. Преобразование II переводит граф $G_1$ в граф $G_2$, где графы $G_1$ и $G_2$ состоят из подграфов $G'_S$ и $G''_S$, где $V(G'_S)\cap V(G''_S)=\varnothing$, и отделенного от них вершинами $s_1$ и $s_2$ порожденного подграфа $P_{k}$ так, как показано на рис. 6. Лемма 3. Если $(p,q)\neq (2,2)$, $\deg_{G'_S}(s_1)\neq 0$, $\deg_{G''_S}(s_2)\neq 0$, то $z(G_2)>z(G_1)$. Доказательство. Нетрудно проверить, что $\Delta(\varnothing)=0$,
$$
\begin{equation*}
\begin{aligned} \, \Delta(\{s_1\}) &=F_3\cdot F_{k-2} - F_{p+1}\cdot F_{k-p}=2F_{k-2}-F_k+F_p\cdot F_{k-p-1} \\ &=F_p\cdot F_{k-p-1}-F_{k-3} =F_p\cdot F_{k-p-1}-(F_p\cdot F_{k-p-2}+F_{p-1}\cdot F_{k-p-3}) \\ &=(F_p-F_{p-1})\cdot F_{k-p-3}\geqslant 0, \\ \Delta(\{s_2\}) &=F_3\cdot F_{k-2} - F_{q+1}\cdot F_{k-q}=(F_q-F_{q-1})\cdot F_{k-q-3}\geqslant 0, \\ \Delta(\{s_1, s_2\}) &=F_3\cdot F_3\cdot F_{k-5} - F_{q+1}\cdot F_{p+1}\cdot F_{t-1}=4F_{k-5}-(F_{p+q+1}-F_p\cdot F_q)\cdot F_{t-1} \\ &=4F_{k-4}-F_{k-1}+F_p\cdot F_q\cdot F_{t-1}+F_{p+q}\cdot F_{t-2} \\ &=-F_{k-7}+F_p\cdot F_q\cdot F_{t-1}+F_{p+q}\cdot F_{t-2} \\ &=F_{k-4}+F_{k-6}+F_p\cdot F_q\cdot F_{t-1}-F_{k-t-1}\cdot F_{t-3} \\ &=F_{k-4}+F_{k-6}+F_p\cdot F_q>0\ (t=3) \\ &\qquad\,\vee\, 2F_{k-6}+F_p\cdot F_q\cdot F_{t-1}+F_{k-t-2}\cdot F_{t-4}>0\ (t\geqslant 4). \end{aligned}
\end{equation*}
\notag
$$
Если $\Delta(\{s_1\})=\Delta(\{s_2\})=0$, то $p=q=2$, что невозможно по условию леммы. Так как $\deg_{G'_S}(s_1)\neq 0$, $\deg_{G''_S}(s_2)\neq 0$, то
$$
\begin{equation*}
z(G'_S,\{s_1\},\varnothing)\neq 0, \qquad z(G''_S, \{s_2\}, \varnothing)\neq 0.
\end{equation*}
\notag
$$
Поэтому либо $\Delta(\{s_1\})>0$, либо $\Delta(\{s_2\})>0$, что по следствию из леммы 1 означает, что $z(G_2)>z(G_1)$. Лемма доказана. Пусть $k=p+q+2\geqslant 5$, где $p$ и $q$ – натуральные числа. Преобразование III переводит граф $G_1$ в граф $G_2$, где графы $G_1$ и $G_2$ состоят из подграфов $G'_S$ и $G''_S$, где $V(G'_S)\cap V(G''_S)=\varnothing$, и отделенного от них вершинами $s_1$ и $s_2$ порожденного подграфа $P_{k}$ так, как показано на рис. 7. Будем предполагать, что $\deg_{G'_S}(s_1)\neq 0$, $\deg_{G''_S}(s_2)\neq 0$. Если
$$
\begin{equation*}
z(G'_S, \{s_1\}, \varnothing) \cdot z(G''_S, \varnothing, \{s_2\}) > z(G'_S, \varnothing, \{s_1\}) \cdot z(G''_S, \{s_2\}, \varnothing),
\end{equation*}
\notag
$$
то включим в преобразование III еще и перестановку местами подграфов $G'_S$ и $G''_S$. Поэтому далее будем считать, что
$$
\begin{equation*}
z(G'_S, \varnothing, \{s_1\}) \cdot z(G''_S, \{s_2\}, \varnothing)\geqslant z(G'_S, \{s_1\}, \varnothing) \cdot z(G''_S, \varnothing, \{s_2\})>0.
\end{equation*}
\notag
$$
Доказательство. Очевидно, что $\Delta(\varnothing)=0$,
$$
\begin{equation*}
\begin{aligned} \, \Delta(\{s_1\}) &=3F_{p+q-1}-F_{p+1}\cdot F_{q+2}=3F_{p+q-1}-F_{p+q+2}+F_p\cdot F_{q+1} \\ &=F_p\cdot F_{q+1}-2F_{p+q-2} \\ &=-F_{p-3}\ (q=1)\, \vee\, F_p\cdot F_{q+1}-2(F_{p}\cdot F_{q-1}+F_{p-1}\cdot F_{q-2}) \\ &=-F_{p-3}\cdot F_{q-2}\ (q\geqslant 3), \\ \Delta(\{s_2\}) &=2F_{p+q} - F_{p+2}\cdot F_{q+1}=2(F_{p}\cdot F_{q+1}+F_{p-1}\cdot F_q)-F_{p+2}\cdot F_{q+1} \\ &=F_{p-1}\cdot (F_q-F_{q-1}), \\ \Delta(\{s_1, s_2\}) &=2F_{(p-1)+q} - F_{p+1}F_{q+1}=F_{p-2}>0\ (q=1)\,\vee\, F_{p-2}\cdot F_{q-2}> 0\ (q\geqslant 3). \end{aligned}
\end{equation*}
\notag
$$
Заметим, что
$$
\begin{equation*}
\Delta(\{s_1\}) + \Delta(\{s_2\})=F_{p-2}>0\ (q=1)\, \vee\, F_{p-2}\cdot F_{q-2}>0 \ (q\geqslant 3).
\end{equation*}
\notag
$$
Тогда из леммы 1 следует, что Лемма доказана.Пусть $q, p, d, t \geqslant 1$ – натуральные числа и граф $G_1$ состоит из подграфов $G'_S$, $ G''_S$, $G'''_S$ и отделенного от них вершинами $s_1, s_2$ и $s_3$ подграфа $H$ так, как показано на рис. 8. Преобразование IV переводит граф $G_1$ в граф $G_2$, удаляя ребро $b_1s_3$ и добавляя ребро $b_1a_1$ (см. рис. 8). При этом подграф $H$ переходит в подграф $H'$. Будем предполагать, что $q \geqslant 2$, если $\deg_{G'_s}(s_1)\neq 0$. Лемма 5. Выполнено неравенство $z(G_2)\geqslant z(G_1)$, причем равенство достигается тогда и только тогда, когда $q=t=d=2$, $G'_S\cong G'''_S \cong P_1$. Доказательство. Выполнив разложение $z$-индексов подграфов $H$ и $H'$ по ребру $s_3a_1$, получим что
$$
\begin{equation*}
\begin{aligned} \, z(H) &=F_{q+1}\cdot (F_{p+d+t+2} - F_p\cdot F_d\cdot F_t) + F_q\cdot F_{p+1}\cdot F_{d+1}\cdot F_{t+1}, \\ z(H') &=F_{q+p+1}\cdot F_{d+t+2} + F_q\cdot F_{p+1}\cdot F_{d+1}\cdot F_{t+1}. \end{aligned}
\end{equation*}
\notag
$$
Поэтому
$$
\begin{equation*}
\Delta(\varnothing)=F_p\cdot F_q\cdot (F_{t+d} + F_t\cdot F_d) - F_p\cdot F_{q-1}\cdot (F_{t+d} + F_{t-1}\cdot F_{d-1}) \geqslant 0.
\end{equation*}
\notag
$$
Откуда очевидно следует
$$
\begin{equation*}
\begin{aligned} \, \Delta(\{s_1\}) &=F_p\cdot F_{q-1}\cdot (F_{t+d} + F_t\cdot F_d) - F_p\cdot F_{q-2}\cdot (F_{t+d} + F_{t-1}\cdot F_{d-1}) \geqslant 0, \\ \Delta(\{s_2\}) &=F_{p-1}\cdot F_q\cdot (F_{t+d} + F_t\cdot F_d) - F_{p-1}\cdot F_{q-1}\cdot (F_{t+d} + F_{t-1}\cdot F_{d-1}) \geqslant 0, \\ \Delta(\{s_1, s_2\}) &=F_{p-1}\cdot F_{q-1}\cdot (F_{t+d} + F_t\cdot F_d) - F_{p-1}\cdot F_{q-2}\cdot (F_{t+d} + F_{t-1}\cdot F_{d-1}) \geqslant 0. \end{aligned}
\end{equation*}
\notag
$$
Несложно проверить, что
$$
\begin{equation*}
\Delta(\varnothing)=0\longleftrightarrow q=t=d=2, \qquad \Delta(\{s_1\})|_{q=t=d=2}=4F_p, \qquad \Delta(\{s_2\})|_{q=t=d=2}=0.
\end{equation*}
\notag
$$
Имеем
$$
\begin{equation*}
\Delta(\{s_3\})=F_{p+q+1}\cdot F_{t+1}\cdot F_{d+1} - F_{p+1}\cdot F_{q+1}\cdot F_{t+1}\cdot F_{d+1}.
\end{equation*}
\notag
$$
Откуда получим
$$
\begin{equation*}
\begin{gathered} \, \Delta(\{s_3\})=F_{p}\cdot F_{q}\cdot F_{t+1}\cdot F_{d+1} > 0, \qquad \Delta(\{s_1, s_3\})=F_p\cdot F_{q-1}\cdot F_{t+1}\cdot F_{d+1} > 0, \\ \Delta(\{s_2, s_3\})=F_{p-1}\cdot F_{q}\cdot F_{t+1}\cdot F_{d+1} \geqslant 0, \\ \Delta(\{s_1, s_2, s_3\})=F_{p-1}\cdot F_{q-1}\cdot F_{t+1}\cdot F_{d+1} \geqslant 0. \end{gathered}
\end{equation*}
\notag
$$
Из наших рассуждений и леммы 1 следует справедливость данной леммы. Лемма доказана. 6. Доказательство теоремы 1Для доказательства теоремы 1 нам понадобится следующее утверждение. Лемма 6. Для любого $n \geqslant 20$ среди $n$-вершинных деревьев вида $T_5(a_1,\dots,a_7)$ наибольшее значение индекса Хосойи достигается при значениях параметров Для любого $n \geqslant 26$ наибольшие значения индекса Хосойи среди $n$-вершинных деревьев вида $T^1_6(b_1,\dots, b_9)$ и $T^2_6(c_1,\dots,c_9)$ одинаковы и достигаются при значениях параметров Доказательство. Рассмотрим деревья вида $T_5(a_1,\dots,a_7)$. Из соображений симметрии можно считать, что
$$
\begin{equation*}
a_1\geqslant a_7, \qquad a_2\geqslant a_4, \qquad a_5\geqslant a_6.
\end{equation*}
\notag
$$
Из леммы 2 следует, что $a_6,a_7\in \{1,2\}$. Из лемм 3 и 4 следует, что одновременно выполнены следующие утверждения:
$$
\begin{equation*}
\begin{gathered} \, a_2\geqslant 3,\quad(a_1,a_3)\neq (2,2)\quad\Longrightarrow\quad a_1+a_2+a_3\leqslant 6, \\ a_2\geqslant 3,\quad(a_3,a_7)\neq (2,2)\quad\Longrightarrow\quad a_2+a_3+a_7\leqslant 6, \\ a_4\geqslant 3,\quad(a_3,a_5)\neq (2,2)\quad\Longrightarrow\quad a_3+a_4+a_5\leqslant 6, \\ a_4\geqslant 3,\quad(a_3,a_6)\neq (2,2)\quad\Longrightarrow\quad a_3+a_4+a_6\leqslant 6, \\ a_2=2\quad\Longrightarrow\quad a_3=1,\quad\max(a_1,a_7)\leqslant 2\vee a_3=2\vee a_3\geqslant 3,\quad a_1=a_7=2, \\ a_4=2\quad\Longrightarrow\quad a_3=1,\quad\max(a_5,a_6)\leqslant 2\vee a_3=2\vee a_3\geqslant 3,\quad a_5=a_6=2. \end{gathered}
\end{equation*}
\notag
$$
Ясно, что при $a_3\geqslant 3$ выполнено Также ясно, что при $n\geqslant 15$ имеем $a_3=2$. Для $n=20$ и $n=21$ были проведены вычислительные эксперименты, показавшие следующие результаты.Таблица 1.Результаты вычислительных экспериментов для 5-листных деревьев вида $T_5(a_1,\dots,a_7)$.
Для $n=20$ и $n=21$ утверждение первого пункта настоящей леммы выполняется. Это является базой индукции. Пусть $n \geqslant 22$; тогда для любого набора $(a_1,\dots,a_7)$ существует такое $i^*$, что $a_{i^*} \geqslant 4$. По следствию из леммы 1 выполнено
$$
\begin{equation*}
z\bigl(T_5(a_1,\dots,a_{i^*},\dots,a_7)\bigr)= z\bigl(T_5(a_1,\dots,a_{i^*}-1,\dots,a_7)\bigr) +z\bigl(T_5(a_1,\dots,a_{i^*}-2,\dots,a_7)\bigr),
\end{equation*}
\notag
$$
откуда следует индукционный переход. Рассмотрим деревья вида $T^2_6(c_1,\dots,c_9)$. Из соображений симметрии можно считать, что
$$
\begin{equation*}
c_1\geqslant c_9, \qquad c_7\geqslant c_8, \qquad c_2\geqslant c_5.
\end{equation*}
\notag
$$
Из леммы 2 следует, что $c_8,c_9\in \{1,2\}$. Из лемм 3 и 4 следует, что одновременно выполнены следующие утверждения:
$$
\begin{equation*}
\begin{gathered} \, c_2\geqslant 3,\quad(c_1,c_3)\neq (2,2)\quad\Longrightarrow\quad c_1+c_2+c_3\leqslant 6, \\ c_2\geqslant 3,\quad(c_3,c_9)\neq (2,2)\quad\Longrightarrow\quad c_2+c_3+c_9\leqslant 6, \\ c_4\geqslant 3,\quad(c_3,c_6)\neq (2,2)\quad\Longrightarrow\quad c_3+c_4+c_6\leqslant 6, \\ c_5\geqslant 3,\quad(c_6,c_7)\neq (2,2)\quad\Longrightarrow\quad c_5+c_6+c_7\leqslant 6, \\ c_5\geqslant 3,\quad(c_6,c_8)\neq (2,2)\quad\Longrightarrow\quad c_5+c_6+c_8\leqslant 6, \\ c_2=2\quad\Longrightarrow\quad c_3=1,\quad\max(c_1,c_9)\leqslant 2\vee c_3=2\vee c_3\geqslant 3,\quad c_1=c_9=2, \\ c_4=2\quad\Longrightarrow\quad \{c_3,c_6\}\in \bigl\{\{1,1\},\{1,2\},\{2,2\}\bigr\}, \\ c_5=2\quad\Longrightarrow\quad c_6=1,\quad\max(c_7,c_8)\leqslant 2\vee c_6=2\vee c_6\geqslant 3,\quad c_7=c_8=2. \end{gathered}
\end{equation*}
\notag
$$
Ясно, что при $n\geqslant 19$ выполнено $c_3,c_6\in \{1,2\}$, причем $(c_3,c_6)\neq (1,1)$. С учетом этих ограничений для $n=26$ и $n=27$ были проведены вычислительные эксперименты, показавшие, что данное утверждение выполняется. Мы не приводим таблицы результатов ввиду их громоздкости. Теперь рассмотрим деревья вида $T^2_6(b_1,\dots,b_9)$. Ввиду симметрии можно считать, что
$$
\begin{equation*}
b_1\geqslant b_9, \qquad b_4\geqslant b_5, \qquad b_7\geqslant b_8, \qquad b_2\geqslant b_3\geqslant b_6.
\end{equation*}
\notag
$$
По лемме 2 можно считать, что $b_5,b_8,b_9\in \{1,2\}$. С учетом этих ограничений для $n=26$ и $n=27$ были проведены вычислительные эксперименты, показавшие, что данное утверждение выполняется. Мы не приводим таблицы результатов ввиду их громоздкости. Пусть $n\geqslant 28$. Тогда для любых наборов $(b_1,\dots,b_9)$ и $(c_1,\dots,c_9)$ существуют такие $j^*, k^*$, что $b_{j^*}, c_{k^*} \geqslant 4$. Лемма доказана. Вернемся к доказательству теоремы 1. Рассмотрим стяжки, изображенные на рис. 1, и предположим, что $n \geqslant 20$. В случае первой стяжки к соответствующему дереву всегда можно применить преобразование IV. После настройки параметров преобразованиями I, II и III, преобразование IV всегда можно применить к дереву со второй стяжкой и оно увеличивает $z$-индекс. Третья стяжка является стяжкой дерева $T_5(a_1,\dots,a_7)$, оптимальные параметры которого найдены в лемме 6. Тем самым, доказан первый пункт теоремы 1. Рассмотрим стяжки, изображенные на рис. 2. Предположим, что $n\geqslant 26$. Стяжки, изображенные в первой строке, не могут быть стяжками никакого максимального 6-листного дерева, так как после настройки параметров преобразованиями I, II и III к ним всегда можно применить преобразование IV, увеличивающее $z$-индекс. В случае первой стяжки из второй строки либо преобразование IV нельзя применить (только если вершина степени 4 смежна с обеими вершинами степени 3), либо оно увеличивает $z$-индекс. Рассмотрим вторую стяжку из второй строки. К соответствующему дереву нельзя применить преобразование IV только если его вершина степени 4 одновременно смежна с тремя листьями и с вершиной степени 3. Если же возможно применить преобразование IV и оно не является увеличивающим, то достигается равенство $z$-индекса с первым графом из третьей строки, причем по лемме 6 такой граф имеет не оптимальные параметры. Из наших рассуждений и преобразований I–III следует, что каждое максимальное 6-листное дерево имеет вид либо деревьев $T^1_6(b_1,\dots,b_9)$ и $T^2_6(c_1,\dots,c_9)$ с параметрами из леммы 6, либо деревьев $A, B, C, D, E$, см. рис. 9, причем подразбиваться могут только отмеченные ребра. Через $T_n$ переобозначим дерево $T^1_6(n-14,2,\dots,2)$. Для каждого $X\in \{A,B,C, D,T\}$ через $X_n$ обозначим граф типа $X$ с $n$ вершинами, если такой граф существует. Для любого $n\geqslant 26$ выполнено что является следствием леммы 1. Можно проверить, что
$$
\begin{equation*}
\begin{gathered} \, z(A_{26})=121016, \quad z(A_{27})=195808, \qquad z(B_{26})=120262, \quad z(B_{27})=194588, \\ z(C_{26})=150464, \quad z(C_{27})=243456, \qquad z(D_{26})=140756, \quad z(D_{27})=227748, \\ z(T_{26})=156160, \quad z(T_{27})=252672. \end{gathered}
\end{equation*}
\notag
$$
Поэтому выполнено
$$
\begin{equation*}
\operatorname{Arg} \max_{n\geqslant 26}\bigl\{z(A_n),z(B_n),z(C_n),z(D_n), z(T_n)\bigr\}=\{T_n\}.
\end{equation*}
\notag
$$
Пусть $p \geqslant q$ – неотрицательные целые числа, причем $p+q=n-13$. Через $E_{n, p}$ обозначим дерево типа $E$, получающееся $p$- и $q$-подразбиениями соответствующих ребер. Тогда для $n\geqslant 26$ выполнено Можно убедиться, что для любого $p$ выполнено
$$
\begin{equation*}
z(E_{26, p}) \leqslant 151888 < z(T_{26})=156160, \qquad z(E_{27, p+1}) \leqslant 245760 < z(T_{27})=252672.
\end{equation*}
\notag
$$
Поэтому $z(E_{n,p})<z(T_n)$ для любых $n\geqslant 26$ и $n-13\geqslant p\geqslant 0$. Теорема доказана.
7. ЗаключениеВ данной работе рассматриваются и при всех достаточно больших $n$ решаются задачи поиска всех 5- и 6-листных деревьев с $n$ вершинами, имеющими максимальное количество паросочетаний среди графов с такими параметрами. Ранее были известны полные ответы к данной задаче для 2-, 3- и 4-листных деревьев с любым достаточно большим количеством вершин. Получение полного описания максимальных $k$-листных $n$-вершинных деревьев при $k\geqslant 7$ является интересной открытой задачей. Это возможная тема для будущих исследований. 
Цитирование в формате AMSBIB
\RBibitem{KuzMal24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|