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

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

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

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

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

[править | править код]

Обозначения

[править | править код]

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

Определим граф с вершинами следующим образом. Разобьём все вершины на «почти равных» групп (то есть возьмём групп по вершине и групп по вершин, где , здесь — остаток от деления на ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим -дольный граф.

Будем обозначать через максимальное количество рёбер, которое может иметь граф с вершинами, не содержащий подграфа, изоморфного .

Среди всех графов на вершинах, не содержащих подграфа , максимальное количество рёбер имеет граф . Если , где — остаток от деления на , то этот максимум равен

  • При основную формулу можно записать короче:
    .

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

[править | править код]
  • Доказательство теоремы Турана влечёт несколько более сильный результат: для любого графа не содержащего копию полного графа найдётся -дольный граф с тем же множеством вершин, что и и со степенью каждой вершины не меньше чему у .

Литература

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

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

[править | править код]