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

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

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

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

Обозначения

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

Определим граф $T_n(v)$ с $v$ вершинами следующим образом. Разобьём все вершины на $n-1$ «почти равных» групп (то есть возьмём $r$ групп по $m+1$ вершине и $n-1-r$ групп по $m$ вершин, где $v=m(n-1)+r$, здесь $r$ — остаток от деления $v$ на $n-1$) и соединим рёбрами все пары вершин из разных групп. Таким образом получим $(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}]$.

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

• Доказательство теоремы Турана влечёт несколько более сильный результат: для любого графа $\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.

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

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