| Математические заметки |
|
|
|
|
|
Оптимальные реализации графов с заданными мерами связности М. Б. Абросимов, Б. А. Теребин Саратовский национальный исследовательский государственный университет им. Н. Г. Чернышевского
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 3, Pages DOI: https://doi.org/10.1134/S000143462303001X 
Реферативные базы данных:
  1. Условие УитниВ работе рассматриваются простые неориентированные графы. Основные понятия из теории графов используются в соответствии с работами [1], [2]. Напомним, что связным называется граф, любая пара вершин которого соединена маршрутом. В противном случае граф называется несвязным. Компонентой связности графа $G$ (или просто компонентой) называется максимальный по включению связный подграф графа $G$. Тривиальным называется одновершинный граф. Граф, любые две вершины которого смежны, называется полным. Определение 1. Вершинной связностью $k(G)$ графа $G$ называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Определение 2. Реберная связность $\lambda(G)$ нетривиального графа $G$ определяется как наименьшее количество ребер, удаление которых приводит к несвязному графу. Вершина графа $G$ называется доминирующей, если ее степень равна $(n-1)$, где $n$ – количество вершин графа $G$. Обозначим минимальную степень вершины в графе $G$ за $\delta(G)$. Вершинная связность $k(G)$, реберная связность $\lambda(G)$ и минимальная степень вершины $\delta(G)$ связаны неравенством, которое было найдено Уитни [3]. Позднее Чартрэнд и Харари [4] доказали следующее утверждение. Теорема 2. Для любых натуральных чисел $a$, $b$, $c$, таких что $0 < a \leqslant b \leqslant c$, существует граф $G$, у которого $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$. Из доказательства теоремы 2 следует, что для любых $a$, $b$, $c$ можно построить граф с числом вершин $2(c+1)$ и с числом ребер $c(c+1)+b$. Строится граф следующим образом: первые $c+1$ вершины образуют полный подграф $G_1$, вторые $c+1$ вершины образуют полный подграф $G_2$. В $G_1$ выбираются $a$ вершин – множество $A$, а в $G_2$ выбираются $b$ вершин – множество $B$. Далее вершины из $A$ и $B$ соединяются $b$ ребрами так, чтобы в первой части эти ребра были инцидентны всем $a$ вершинам, а в другой части – всем $b$ вершинам. Схематично структура графа показана на рис. 1. Возникает вопрос: можно ли для заданных $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$ построить граф с меньшим числом вершин или ребер? Оказывается, что в некоторых случаях это возможно. Предварительные результаты были представлены в работах [5], [6], данная работа является завершающей эти исследования. 2. Минимальное число вершинДля удобства неравенство $a \leqslant b \leqslant c$ представим с помощью совокупности следующих неравенств: Рассмотрим каждый случай отдельно. Далее под графом с параметрами $a$, $b$, $c$ будем понимать граф, удовлетворяющий теореме Чартрэнда–Харари, т.е. граф $G$, у которого $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$. Очевидно, что любой граф, удовлетворяющий теореме Чартрэнда–Харари, должен состоять не менее, чем из $c+1$ вершины. Теорема 3. Граф с наименьшим количеством вершин, удовлетворяющий условию $a=b=c$, является полным графом с числом вершин $c+1$. Доказательство. Поскольку минимальная степень вершины равна $c$, число вершин в графе не может быть меньше, чем $c+1$. Рассмотрим полный граф $K_{c+1}$, состоящий из $c+1$ вершины. Степень каждой его вершины равна $\delta(K_{c+1})=c$. Поскольку после удаления любых вершин из полного графа останется полный граф, то $k(K_{c+1})=c$. По теореме 1 имеем Следовательно, и $K_{c+1}$ есть граф с параметрами $a$, $b$, $c$, где $a=b=c$. Всякий граф на $c+1$ вершине, не являющийся полным, содержит вершину степени меньше чем $c$, т.е. не является графом с параметрами $a$, $b$, $c$.В следующей теореме рассмотрим два случая: $a < b < c$ и $a=b < c$, общим для них является условие $b < c$. Теорема 4. Граф с наименьшим количеством вершин, удовлетворяющий условию $a \leqslant b < c$, является графом с числом вершин $2(c+1)$. Доказательство. Заметим, что граф, построенный по схеме из теоремы 2, имеет в точности $2(c+1)$ вершин. Докажем, что если $b < c$, то такое число вершин является минимальным. Пусть $G$ – граф с параметрами $a$, $b$, $c$ из условия теоремы. Так как $0 < a \leqslant b < c$, то $c > 1$ и $G$ не является тривиальным графом. Так как реберная связность графа $G$ равна $b$, то в графе $G$ есть $b$ ребер, удаление которых приводит к несвязному графу, который обозначим $G^*$. Так как $G^*$ является несвязным, он состоит по крайней мере из двух компонент связности. Пусть $G_1$ одна из них. Если в $G_1$ есть вершина степени $c$, то минимально возможное число вершин в $G_1$ есть $c+ 1$. Предположим, что все вершины в $G_1$ имеют степень меньше, чем $c$. Обозначим максимальную из степеней вершин в $G_1$ через $\Delta_1$, а через $n_1$ – количество вершин в $G_1$. Очевидно, что $n_1 > \Delta_1$ и $0 < \Delta_1 < c$. До удаления $b$ ребер все вершины из $G_1$ в графе $G$ имели степень не ниже $c$. Так как $b$ – это минимальное число ребер, удаление которых нарушает связность графа $G$, среди них не может быть ребер, которые соединяют пары вершин из $G_1$. Поэтому каждое из этих $b$ ребер инцидентно одной вершине из $G_1$, соответственно удаление одного ребра приводит к уменьшению на 1 степени одной вершины в $G_1$. Тогда получаем, что Далее, так как $\Delta_1 < n_1$ или $\Delta_1+1 \leqslant n_1$, получаем
$$
\begin{equation*}
(c-\Delta_1)(\Delta_1+1) \leqslant (c-\Delta_1)n_1 \leqslant b, \qquad c\Delta_1+c-\Delta_1^2-\Delta_1 \leqslant b.
\end{equation*}
\notag
$$
Так как по условию $b < c$, то
$$
\begin{equation*}
c\Delta_1+c-\Delta_1^2-\Delta_1 < c, \qquad c-\Delta_1-1 < 0.
\end{equation*}
\notag
$$
По предположению $\Delta_1 < c$, поэтому последнее неравенство невозможно. Следовательно, каждая компонента связности в графе $G^*$ содержит не менее $c+1$ вершин. Таким образом, наименьшее возможное число вершин, из которого может состоять граф из условия теоремы, равно $2(c+1)$. Теорема 5. Граф с наименьшим количеством вершин, удовлетворяющий условию $a < b=c$, является графом с числом вершин $2(c+1)-a$. Доказательство. Пусть $G$ – граф с параметрами $a$, $b$, $c$ из условия теоремы. Так как вершинная связность графа $G$ равна $a$, то в графе $G$ есть $a$ вершин, удаление которых приводит к несвязному графу, который обозначим $G^*$. Так как $G^*$ является несвязным, он состоит по крайней мере из двух компонент связности. Пусть $G_1$ одна из них. Минимальная степень вершины в графе $G$ есть $c$. После удаления $a$ вершин минимальная степень может уменьшиться не более, чем на $a$. Следовательно, в $G_1$ будет не менее, чем $c-a+1$ вершин. Тогда в графе $G$ будет не менее, чем $2(c- a+ 1)+a=2(c+1)-a$ вершин. Покажем, что граф $G$ с параметрами $a$, $b$, $c$ из условия теоремы и числом вершин $2(c+1)-a$ существует. Так как $b=c$, данное значение реберной связности $\lambda(G)=b$ может быть получено удалением всех ребер у любой вершины минимальной степени $c$, т.е. ее изоляцией. Построим множество $A$ из $a$ вершин так, чтобы эти вершины были смежны друг с другом и смежны со всеми остальными вершинами из графов $G_1$ и $G_2$, т.е. вершины множества $A$ – доминирующие вершины. Графы $G_1$ и $G_2$ полные графы на $c-a+1$ вершинах. Описанный граф схематично показан на рис. 2. Условие $\lambda(G)=b$ достигается путем изоляции любой вершины из $G_1$ и $G_2$; $\lambda(G)=b= \delta(G)=c$: каждая вершина из $G_1$ и $G_2$ смежна с каждой вершиной из $A$ и смежна с остальными вершинами из своей части. Таким образом, степень каждой вершины из $G_1$ и $G_2$ равна $a+((c-a+1)- 1)=c=\delta(G)$. Вершины множества $A$ доминирующие, т.е. их степени равны $a+(2(c-a+1)- 1)=2(c+1)-a-1 > c$, так как $c > a$. При удалении вершин из множества $A$ получим 2 компоненты: $G_1$ и $G_2$, следовательно, $k(G)=a$. Таким образом, построили граф из $2(c+1)-a$ вершины, в котором $a < b=c$. 3. Минимальное число реберТеперь определим графы с минимальным количеством ребер, которые удовлетворяют условию Уитни. Представим неравенство $a \leqslant b \leqslant c$ с помощью совокупности случаев так же, как это делалось ранее. Рассмотрим каждый случай отдельно. Теорема 6. Граф с наименьшим количеством ребер, удовлетворяющий условию $a=b=c$, является полным графом с числом ребер ${c(c-1)}/{2}$. Доказательство. Доказательство аналогично доказательству теоремы 3. Теорема 7. Граф с наименьшим количеством ребер, удовлетворяющий условию $a < b < c$, является графом с числом ребер Доказательство. Построим граф $G$ с $2(c+1)$ вершинами следующим образом: выделим 2 множества с $c+1$ вершинами. Обозначим соответствующие подграфы через $G_1$ и $G_2$. Пометим $a$ вершин в $G_1$ и обозначим это помеченное множество за $A$, а остальные вершины из $G_1$ обозначим $\overline{A}$. Пометим $b$ вершин в $G_2$ и обозначим это помеченное множество за $B$, а остальные вершины из $G_2$ обозначим $\overline{B}$. Соединим ребрами в $G_1$ все непомеченные вершины из $\overline{A}$ друг с другом, а также соединим их со всеми вершинами из $A$. Аналогичным образом произведем соединение $G_2$ и $B$. Пусть вершины внутри множеств $A$ и $B$ не смежны. Получим, что степени вершин множества $\overline{A}$ равны $\delta(G)=c$. Поскольку все $c-a+1$ вершин множества $\overline{A}$ смежны друг с другом, соответствующий подграф содержит ${(c-a)(c-a+1)}/{2}$ ребер. К тому же, все $c-a+1$ вершины смежны с $a$ вершинами из $A$. Тогда количество ребер между $\overline{A}$ и $A$ равно $a(c-a+1)$. Получаем, что количество ребер внутри $\overline{A}$ и между $\overline{A}$ и $A$ равно Аналогичным образом получаем для $\overline{B}$ и $B$: Соединим вершины множеств $A$ и $B$. Каждая вершина множества $A$ будет инцидентна $[b/a]$ ребрам. Каждое такое ребро, инцидентное вершине из $A$, будет инцидентно ровно одной вершине из $B$. Может получиться, что $b-a[b/a]=m$ вершин из $B$ не будут смежны с $A$. Тогда попарно соединим $m$ любых вершин из $A$ с вершинами из $B$. После соединения получаем еще $b$ ребер. В итоге получим, что $m$ вершинам из $A$ будет инцидентно $[b/a]+1$ ребро, а $(a-m)$ вершинам – $[b/a]$. Теперь рассмотрим множество $B$. Степень каждой вершины равна $c-b+2$. Это следует из того, что каждая вершина смежна с каждой вершиной из $\overline{B}$ и смежна с вершиной из $A$, следовательно $(c- b+1)+1=c-b+2$. Если $b > 2$, то степень каждой вершины из $B$ меньше $c$. Соединим вершины $B$ между собой таким образом, чтобы их степени стали не меньше $c$. Соединим их с помощью
$$
\begin{equation*}
\biggl\lceil\frac{b(c-(c-b-2))}{2}\biggr\rceil=\biggl\lceil\frac{b(b-2)}{2}\biggr\rceil
\end{equation*}
\notag
$$
ребер, где величина $c-(c-b+2)$ – количество ребер, которое должно быть инцидентно каждой вершине внутри $B$. Если $b < 2$, то получим, что количество ребер меньше 0, что невозможно. Тогда определим величину $\sigma$ следующим образом:
$$
\begin{equation*}
\sigma=\begin{cases} 0, & \text{если } b \leqslant 2, \\ \biggl\lceil\dfrac{b(b-2)}{2}\biggr\rceil & \text{иначе}. \end{cases}
\end{equation*}
\notag
$$
Теперь рассмотрим множество $A$. Степень $(a-m)$ вершин равна $(c-a+1)+ [b/a]$ и степень $m$ вершин равна $(c-a+1)+[b/a]+1$. Если $a \geqslant [b/a]+2$, то степень некоторых (а при строгом неравенстве – всех) вершин из $A$ меньше $c$. Соединим вершины $A$ между собой таким образом, чтобы их степени стали не меньше $c$. Рассуждая аналогично предыдущему случаю, получим следующее количество ребер:
$$
\begin{equation*}
\theta=\begin{cases} 0, & \text{если } a <\biggl[\dfrac{b}{a}\biggr]+2, \\ \biggl\lceil \dfrac{(a-m)(a-1-[{b}/{a}])}{2} +\dfrac{m(a-2-[{b}/{a}])}{2} \biggr\rceil & \text{иначе}. \end{cases}
\end{equation*}
\notag
$$
Тогда, сложив все результаты, получим следующее количество ребер:
$$
\begin{equation*}
(c-a+1)\bigg(\frac{c-a}{2}+a\bigg)+(c-b+1)\bigg(\frac{c-b}{2}+b\bigg)+b+\sigma+\theta,
\end{equation*}
\notag
$$
где
$$
\begin{equation*}
\begin{gathered} \, \theta=\begin{cases} 0, & \text{если } a < \biggl[\dfrac{b}{a}\biggr]+2, \\ \biggl\lceil \dfrac{(a-m)(a-1-[{b}/{a}])}{2} +\dfrac{m(a-2-[{b}/{a}])}{2} \biggr\rceil & \text{иначе}, \end{cases} \\ m=b-a\biggl[\frac{b}{a}\biggr], \\ \sigma=\begin{cases} 0, & \text{если }b \leqslant 2, \\ \biggl\lceil\dfrac{b(b-2)}{2}\biggr\rceil & \text{иначе}. \end{cases} \end{gathered}
\end{equation*}
\notag
$$
При этом условие $a < b < c$, где $k(G)=a$, $\lambda(G)=b$, $\delta(G)=c$, будет верно по теореме Уитни. Посмотрим, действительно ли полученное выражение меньше, чем $(c+1)c+b$. Если раскрыть выражения с обеих сторон, то в худшем случае получим следующее значение (когда $\sigma$ и $\theta$ не равны нулю): $c^2+c-{m}/{2} < c^2+c+b.$ Теорема 8. Граф с наименьшим количеством ребер, удовлетворяющий условию $a=b < c$, является графом с числом ребер $c^2-b^2+2b+c+2\sigma$, где Доказательство. Этот случай является частным случаем предыдущего. Множества $A$ и $B$ будут иметь одинаковую размерность, а значит, количество ребер, которое нужно будет добавить в $A$ и $B$, будет совпадать, т.е. $\sigma=\theta$. Теорема 9. Граф с наименьшим количеством ребер, удовлетворяющий условию $a < b=c$, является графом с числом ребер $c^2-a^2+a+c+\sigma$, где Доказательство. Построим граф $G$ как в теореме 5, но со следующим изменением: вершины множества $A$ не смежны друг с другом. $G_1$ и $G_2$ являются полными подграфами по построению, число вершин в каждом из них равно $(c- a+1)$. Так как в полном графе с числом вершин $n$ количество ребер равно ${n(n-1)}/{2}$, количество ребер, соединяющих вершины $G_1$ и $G_2$, равно $(c-a)(c-a+1)$. При этом каждая из вершин $G_1$ и $G_2$ смежна с каждой вершиной из $A$, т.е. $2(c-a+1)$ вершины смежны с $a$ вершинами. Тогда получаем $2a(c-a+1)$ ребра. В итоге количество ребер равно $(c-a)(c-a+1)+2a(c-a+1)=c^2-a^2+a+c$. Если $a=c-1$, то степень каждой вершины из $A$ равна 4. В случае, когда $c > 4$, степень каждой вершины из $A$ будет меньше $\delta(G)$, что противоречит условию. Таким образом, наименьшее количество ребер, которое может содержать граф, – это $c^2-a^2+a+c$. Это условие является необходимым, но не достаточным. Получили, что степени вершин в $A$ могут быть меньше $c$. Тогда нужно соединить вершины множества $A$ между собой так, чтобы их степени стали не меньше $\delta(G)=c$. Степень каждой вершины из множества $A$ равна $2(c-a+1)$. Чтобы эта величина стала не меньше $c$, необходимо соединить вершины внутри $A$ между собой $\lceil{a(c-2(c-a+ 1))}/{2}\rceil$ ребрами, где величина $c-2(c-a+1)$ – количество ребер, которое должно быть инцидентно каждой вершине внутри $A$. Обозначим полученную величину за $\sigma$ и распишем ее:
$$
\begin{equation*}
\sigma=\biggl\lceil\frac{a(c-2(c-a+1))}{2}\biggr\rceil =\biggl\lceil\frac{2a^2-ac-2a}{2}\biggr\rceil.
\end{equation*}
\notag
$$
При $a=1$ данная величина равна $\lceil(2-c-2)/{2}\rceil=\lceil {-c}/{2}\rceil$. Поскольку количество ребер отрицательным быть не может, то
$$
\begin{equation*}
\sigma=\begin{cases} 0, & \text{если } \biggl\lceil\dfrac{2a^2-ac-2a}{2}\biggr\rceil \leqslant 0, \\ \biggl\lceil\dfrac{2a^2-ac-2a}{2}\biggr\rceil & \text{иначе}. \end{cases}
\end{equation*}
\notag
$$
Таким образом, минимальное количество ребер, которое может содержать граф, удовлетворяющий условию $a < b=c$, равно следующему значению: где
$$
\begin{equation*}
\sigma=\begin{cases} 0, & \text{если }\biggl\lceil\dfrac{2a^2-ac-2a}{2}\biggr\rceil \leqslant 0, \\ \biggl\lceil\dfrac{2a^2-ac-2a}{2}\biggr\rceil & \text{иначе}. \end{cases}
\end{equation*}
\notag
$$
Определим, действительно ли полученное выражение меньше, чем $c(c+1)+b$. Если раскрыть выражения с обеих сторон, то в худшем случае получим следующее значение (когда $\sigma$ не равно нулю): $c^2+c-{ac}/{2} < c^2+c+b$. Рассмотрим несколько примеров. Пусть $a=4$, $b=c=5$. Тогда $k(G)=4$, $\lambda(G)=\delta(G)=5$. Данный случай удовлетворяет условию теорем 5 и 9. Посчитаем количество вершин и ребер, из которого будем строить граф. В силу теоремы 5 количество вершин равно $2(c+ 1)- a=2(5+1)-4=8$. Далее рассчитаем число ребер. Для начала найдем значение $\sigma$:
$$
\begin{equation*}
\sigma=\biggl\lceil\frac{2a^2-ac-2a}{2}\biggr\rceil=\biggl\lceil\frac{36-20-8}{2}\biggr\rceil=2.
\end{equation*}
\notag
$$
Тогда число ребер равно $c^2-a^2+a+c+\sigma=25-16+4+5+2=20$. Пусть $a=b=4$, $c=5$. Тогда $k(G)=\lambda(G)=4$, $\delta(G)=5$. Данный случай удовлетворяет условию теорем 4 и 8. Посчитаем количество вершин и ребер, из которого будем строить граф. В силу теоремы 4 количество вершин равно $2(c+1)=2(5+1)=12$. Далее рассчитаем число ребер. Для начала найдем значение $\sigma$:
$$
\begin{equation*}
\sigma=\biggl\lceil\frac{b(b-2)}{2}\biggr\rceil=\biggl\lceil\frac{4(4-2)}{2}\biggr\rceil=4.
\end{equation*}
\notag
$$
Тогда число ребер равно $c^2-b^2+2b+c+2\sigma=25-16+8+5+8=30$. В итоге получаем графы, которые удовлетворяют условию Уитни с минимальным количеством вершин и ребер. Графы, минимальные по ребрам, являются минимальными и по вершинам. 4. ЗаключениеОказалось, что нет универсального способа построения графа $G$ с минимальным числом вершин и ребер для любых чисел $a$, $b$, $c$, таких что $0 < a \leqslant b \leqslant c$ и $k(G)=a$, $\lambda(G)=b$, $ \delta(G)=c$. Однако, были сформулированы и доказаны теоремы, позволяющие строить такие графы для всех отдельных ситуаций: $a=b=c$, $a < b < c$, $a=b < c$ и $a < b=c$. Самым простым является случай $a=b=c$, когда все характеристики равны между собой, и соответствующей реализацией является полный граф на $c+1$ вершинах. В некоторых ситуациях оптимальным является граф с $2(c+1)$ вершинами, который был предложен Чартрэндом и Харари, и построить граф с меньшим числом вершин или ребер не представляется возможным. При $b=c$ всегда можно построить граф с меньшим числом вершин и ребер, чем граф, построенный по схеме Чартрэнда и Харари. 
Цитирование в формате AMSBIB
\RBibitem{AbrTer23} |
|
||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|