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

См. также: Проблема Турана

Теорема Тура́на даёт ответ на вопрос о максимальном количестве рёбер в графе без полного 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\leq 8$ основную формулу можно записать короче:

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

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

Доказательство можно провести, например, с помощью математической индукции по количеству вершин графа $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,\ldots ,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}}$$ Что и требовалось. Шаг индукции доказан.

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

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

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

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