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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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


Применение[править | править вики-текст]

Литература[править | править вики-текст]

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

Внешние ссылки[править | править вики-текст]