Меню Главная Случайная статья Настройки Теорема Турана Материал из https://ru.wikipedia.org Теорема Турана даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа. Впервые задачу о запрещённом подграфе поставил венгерский математик Пал Туран в 1941 году. Содержание 1 Формулировка 1.1 Обозначения 1.2 Теорема 1.3 Замечания 2 Вариации и обобщения 3 Литература 4 Внешние ссылки Формулировка Обозначения Обозначим через ${\displaystyle K_{n}}$ полный n-вершинный граф. Определим граф ${\displaystyle T_{n}(v)}$ с ${\displaystyle v}$ вершинами следующим образом. Разобьём все вершины на ${\displaystyle n-1}$ «почти равных» групп (то есть возьмём ${\displaystyle r}$ групп по ${\displaystyle m+1}$ вершине и ${\displaystyle n-1-r}$ групп по ${\displaystyle m}$ вершин, где ${\displaystyle v=m(n-1)+r}$, здесь ${\displaystyle r}$ — остаток от деления ${\displaystyle v}$ на ${\displaystyle n-1}$) и соединим рёбрами все пары вершин из разных групп. Таким образом получим ${\displaystyle (n-1)}$-дольный граф. Будем обозначать через ${\displaystyle ex(v,n)}$ максимальное количество рёбер, которое может иметь граф с ${\displaystyle v}$ вершинами, не содержащий подграфа, изоморфного ${\displaystyle K_{n}}$. Теорема Среди всех графов на ${\displaystyle v}$ вершинах, не содержащих подграфа ${\displaystyle K_{n}}$, максимальное количество рёбер имеет граф ${\displaystyle T_{n}(v)}$. Если ${\displaystyle v=m(n-1)+r}$, где ${\displaystyle r}$ — остаток от деления ${\displaystyle v}$ на ${\displaystyle n-1}$, то этот максимум равен ${\displaystyle ex(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2}}}$ Замечания При ${\displaystyle n\leq 8}$ основную формулу можно записать короче: ${\displaystyle ex(v,n)=\left[v^{2}\cdot {\frac {n-2}{2n-2}}\right]}$. Доказательство можно провести, например, с помощью математической индукции по количеству вершин графа ${\displaystyle v}$. Введем индукцию по числу вершин ${\displaystyle n}$ в полном подграфе. База ${\displaystyle n=3}$. Доказательство: Введем индукцию по числу вершин. База ${\displaystyle n=1,2}$. Для данных случаев оценка очевидна. Доказательство базы для ${\displaystyle n=1,2,3}$: Пусть доказано для ${\displaystyle k}$. Докажем для ${\displaystyle k+2}$. Если в графе нет ребер то все доказано. Иначе выделим ребро. Заметим что к этому ребру из остальных вершин графа выходит не более одного ребра (иначе есть треугольник) ${\displaystyle \Rightarrow }$ этих ребер не более ${\displaystyle k}$. Для остального графа применим предположение индукции. Откуда общее количество рёбер не более ${\displaystyle {\frac {k^{2}-r^{2}}{4}}+k+1={\frac {(k+2)^{2}-r^{2}}{4}}}$. Что и требовалось. База доказана. Шаг: Пусть для ${\displaystyle n-1}$ верно, докажем для ${\displaystyle n}$. Введем индукцию. База ${\displaystyle k=1,2,\ldots ,n-1}$. Для данных случаев утверждение очевидно. Шаг. Пусть для ${\displaystyle k}$ верно, докажем для ${\displaystyle k+n-1}$. Если в графе нет полного графа на ${\displaystyle n-1}$ вершинах воспользуемся предыдущим шагом (очевидно, что оценка будет лучше). Иначе выделим его. Из каждой из остальных вершин к нему выходит не более ${\displaystyle n-2}$ ребер, то есть всего не более ${\displaystyle k\cdot (n-2)}$. Следовательно, общее количество рёбер в графе не превышает $${\displaystyle {\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}}}$$ Что и требовалось. Шаг индукции доказан. Вариации и обобщения Доказательство теоремы Турана влечёт несколько более сильный результат: для любого графа ${\displaystyle \Gamma }$ не содержащего копию полного графа ${\displaystyle K_{n+1}}$ найдётся ${\displaystyle n}$-дольный граф ${\displaystyle \Gamma '}$ с тем же множеством вершин, что и ${\displaystyle \Gamma }$ и со степенью каждой вершины не меньше чему у ${\displaystyle \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. Внешние ссылки Теорема Турана в словаре теории графов