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

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.

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

Впервые задачу о запрещённом подграфе поставил венгерский математик Ту́ран, Пал (англ.) (венг. Pál Turá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\leq 8$ основную формулу можно записать короче: $ex(v,n)=\left[v^2\cdot\frac{n-2}{2n-2}\right]$.

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

Применение

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Литература

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

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

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