Теорема Турана

Встречается также вариант написания: Проблема Турана. Теорема Турáна даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа.

Впервые задачу о запрещённом подграфе поставил венгерский математик Пал Туран в 1941 году.

Формулировка

Обозначения

Обозначим через $K_n$ полный n-вершинный граф.

Определим граф $T_n(v)$ с $v$ вершинами следующим образом. Разобьём все вершины на $n-1$ «почти равных» групп (то есть возьмём $r$ групп по $m+1$ вершине и $n-1-r$ групп по $m$ вершин, если $v:(n-1)=m$ с остатком $r$) и соединим рёбрами все пары вершин из разных групп. Таким образом получим $(n-1)$-дольный граф.

Будем обозначать через $ex(v,n)$ максимальное количество рёбер, которое может иметь граф с $v$ вершинами, не содержащий подграфа, изоморфного $K_n$.

Теорема

Среди всех графов на $v$ вершинах, не содержащих подграфа $K_n$, максимальное количество рёбер имеет граф $T_n(v)$. Если $v=m(n-1)+r$, где $r$ — остаток от деления $v$ на $n-1$, то этот максимум равен

$ex(v,n)=\frac{(n-2)(v^2-r^2)}{2n-2}+\frac{r(r-1)}{2}$

Замечания

• При $n\le 8$ основную формулу можно записать короче:

  $ex(v,n)=[v^2\cdot \frac{n-2}{2n-2}]$.

Доказательство

Доказательство можно провести, например, с помощью математической индукции по количеству вершин графа $v$.

Введем индукцию по числу вершин $n$ в полном подграфе.

• База $n=3$. Доказательство: Введем индукцию по числу вершин.
  • База $n=1,2$. Для данных случаев оценка очевидна.
  • Шаг: Пусть доказано для $k$. Докажем для $k+2$. Если в графе нет ребер то все доказано. Иначе выделим ребро. Заметим что к этому ребру из остальных вершин графа выходит не более одного ребра (иначе есть треугольник) $\Rightarrow$ этих ребер не более $k$. Для остального графа применим предположение индукции. Откуда общее количество рёбер не более $\frac{k^2-r^2}{4}+k+1=\frac{(k+2{)}^2-r^2}{4}$. Что и требовалось.
• База доказана.

• Шаг. Пусть для $n-1$ верно, докажем для $n$. Введем индукцию. База $k=1,2,\dots ,n-1$. Для данных случаев утверждение очевидно. Шаг. Пусть для $k$ верно, докажем для $k+n-1$. Если в графе нет полного графа на $n-1$ вершинах воспользуемся предыдущим шагом (очевидно, что оценка будет лучше). Иначе выделим его. Из каждой из остальных вершин к нему выходит не более $n-2$ ребер, то есть всего не более $k\cdot (n-2)$. Следовательно, общее количество рёбер в графе не превышает

$$\frac{(n-2)(k^2-r^2)}{2n-2}+\frac{(n-1)(n-2)}{2}+k\cdot (n-2)+\frac{r\cdot (r-1)}{2}=\frac{(n-2)((k+n-1{)}^2-r^2)}{2n-2}+\frac{r\cdot (r-1)}{2}$$ Что и требовалось. Шаг индукции доказан.

Вариации и обобщения

• Доказательство теоремы Турана влечёт несколько более сильный результат: для любого графа $\mathrm{\Gamma }$ не содержащего копию полного графа $K_{n+1}$ найдётся $n$-дольный граф ${\mathrm{\Gamma }}^{\prime }$ с тем же множеством вершин, что и $\mathrm{\Gamma }$ и со степенью каждой вершины не меньше чему у $\mathrm{\Gamma }$.

Литература

• «Теория графов» О.Оре. 1980
• Berge C. Graphs (second revised edition), North — Holland, Amsterdam — New York — Oxford, 1985.
• Lovasz L. Combinatorial problems and exercises, Academiqi Kiado, Budapest, 1979.

Внешние ссылки

• Теорема Турана в словаре теории графов