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

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

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

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