EssayAI
Блог
Блог
Естественные науки

Теорема Турана: максимум рёбер без большой клики

8 ноября 2026Время чтения: 8 минут
#теорема турана#теория графов#клика#экстремальная комбинаторика#граф турана
Теорема Турана: максимум рёбер без большой клики

Сколько связей можно провести между участниками сети, если запрещена группа из четырёх человек, знакомых попарно? Ответ зависит от числа участников, но искать все возможные сети не придётся. Теорема Турана даёт точный предел для простого графа без клики заданного размера и показывает, как устроен пример, достигающий этого предела. Калькулятор ниже делит вершины на группы, подсчитывает рёбра и показывает границу, после которой запрещённая клика неизбежна.

Постановка: рёбра против клик

Работаем с конечным простым неориентированным графом: петли и кратные рёбра запрещены. Клика размера kk - это kk различных вершин, каждая пара которых соединена ребром. Её обозначают KkK_k; например, K3K_3 - треугольник. Граф называется KkK_k-свободным, если в нём нет такого полного подграфа. Дополнительные рёбра к другим вершинам не мешают выбранной группе быть кликой.

Зафиксируем число вершин nn и запретим Kr+1K_{r+1}. Какое наибольшее число рёбер может остаться? Это экстремальная задача: нужно одновременно доказать верхнюю границу для всех допустимых графов и предъявить граф, который её достигает. Первая часть исключает лучшие ответы, вторая подтверждает точность.

Доли графа меняются с 4, 3 и 1 на 3, 3 и 2: после балансировки число рёбер растёт с 19 до 21, а клика из четырёх вершин по-прежнему невозможна.

Здесь анимация сравнивает два полных трёхдольных графа на одних и тех же восьми вершинах. Рёбра идут только между долями. Если четыре вершины выбраны из трёх долей, по крайней мере две попали в одну долю и не соединены; значит, K4K_4 нет ни в одном из состояний.

Формулировка теоремы Турана

Пусть r≥2r\ge 2, n≥rn\ge r, а GG - простой граф на nn вершинах без Kr+1K_{r+1}. Разделим nn вершин на rr долей, размеры которых отличаются не больше чем на единицу. Соединим каждую пару вершин из разных долей и не будем соединять вершины одной доли. Получится граф Турана Tr(n)T_r(n).

Теорема утверждает: число рёбер GG не превосходит числа рёбер Tr(n)T_r(n). Равенство достигается только на графе Турана с точностью до переименования вершин. Стандартное обозначение экстремального числа - ex⁡(n,Kr+1)=e(Tr(n))\operatorname{ex}(n,K_{r+1})=e(T_r(n)).

Запрет именно на Kr+1K_{r+1} важен: параметр rr обозначает число долей, а не размер запрещённой клики. Это соглашение используется и в исследовательской работе о теореме плотности клик, где классический результат Турана служит отправной точкой. В некоторых книгах граф индексируют иначе, поэтому всегда проверяйте определения.

Как устроен граф Турана

Доли графа - независимые множества: внутри каждой нет рёбер. При этом любые две вершины из разных долей соединены. Это полная rr-дольная конструкция. Она не содержит Kr+1K_{r+1} по принципу Дирихле: из r+1r+1 вершин две обязательно окажутся в одной доле.

С другой стороны, когда все rr долей непусты, по одной вершине из каждой образуют KrK_r. Ограничение не исключает малые клики: оно запрещает конкретный размер и, следовательно, все большие размеры. Подробнее о множествах без внутренних рёбер рассказано в статье про независимое множество в графе.

Раскраска тоже помогает понять конструкцию: каждой доле можно присвоить свой цвет. В полном многодольном графе это правильная раскраска, поскольку рёбра внутри цветовых классов отсутствуют. Но произвольный граф без Kr+1K_{r+1} не обязан быть rr-раскрашиваемым. Различие между кликами и раскрасками важно и при изучении хроматического полинома.

Точная формула и остаток

Пусть n=qr+sn=qr+s, где q=⌊n/r⌋q=\lfloor n/r\rfloor и 0≤s<r0\le s<r. Тогда ss долей содержат по q+1q+1 вершине, а остальные r−sr-s - по qq. Число рёбер получается из суммы произведений размеров всех пар долей:

tr(n)=12(n2−s(q+1)2−(r−s)q2).t_r(n)=\frac12\left(n^2-s(q+1)^2-(r-s)q^2\right).

Здесь из n2n^2 вычтена сумма квадратов размеров долей, а деление на два устраняет двойной счёт. Эквивалентная запись через остаток удобна для ручного расчёта:

tr(n)=12((1−1r)n2−s(r−s)r).t_r(n)=\frac12\left(\left(1-\frac1r\right)n^2-\frac{s(r-s)}r\right).

Часто используют более простую оценку e(G)≤(1−1/r)n2/2e(G)\le (1-1/r)n^2/2. Она верна, но при ненулевом остатке может быть нецелой и не всегда даёт точное значение после округления. Калькулятор считает точную величину через размеры долей, а не по приближению.

Пример: восемь вершин без K4K_4

Для запрета K4K_4 берём r=3r=3. Деление 8=2⋅3+28=2\cdot3+2 даёт доли размеров 3,3,23,3,2. Между первой и второй долями есть 3⋅3=93\cdot3=9 рёбер, между каждой из них и третьей - по 3⋅2=63\cdot2=6. Всего получаем 9+6+6=219+6+6=21.

Трёхдольный граф с долями 3, 3 и 2: между долями 21 ребро, а внутри долей рёбер нет
Трёхдольный граф с долями 3, 3 и 2: между долями 21 ребро, а внутри долей рёбер нет

Теорема доказывает, что 21 - максимум без K4K_4. Поэтому 22 ребра гарантируют клику из четырёх вершин. При 21 ребре гарантия ещё не работает: нарисованный граф служит контрпримером. Граф с меньшим числом рёбер тоже может содержать K4K_4; достаточное условие выше порога не является критерием для каждого отдельного графа.

Почему доли должны быть почти равными

Рассмотрим полный многодольный граф с размерами долей aa и bb, где a≥b+2a\ge b+2. Перенесём одну вершину из большей доли в меньшую. Её связи с остальными долями не изменятся; она потеряет bb рёбер к новой доле и приобретёт a−1a-1 рёбер к прежней. Выигрыш равен a−b−1>0a-b-1>0.

Например, для размеров 4,3,14,3,1 имеем 4⋅3+4⋅1+3⋅1=194\cdot3+4\cdot1+3\cdot1=19. Перенос из доли размера 4 в долю размера 1 даёт размеры 3,3,23,3,2 и прибавляет 4−1−1=24-1-1=2 ребра. Пока две доли отличаются хотя бы на два, такой перенос улучшает конструкцию. Следовательно, среди полных rr-дольных графов максимум достигается при наиболее равных размерах. Это ещё не доказывает теорему для произвольного графа: надо отдельно объяснить, почему другие структуры не лучше.

В этом рассуждении удобно считать не проведённые, а отсутствующие рёбра. Полный граф имел бы ребро между каждой парой вершин, однако внутри долей они исключены. Чем крупнее доля, тем больше пар теряется внутри неё. Неравномерное распределение концентрирует такие потери, а перенос вершины уменьшает их общее число. Аргумент о переносе даёт строгий расчёт этого наблюдения и работает для любого числа долей.

Проверка полезна и при работе с формулой: сумма размеров долей должна равняться исходному числу вершин, а каждую пару долей при подсчёте рёбер нужно брать ровно один раз. Если умножить размер каждой доли на число вершин вне неё и сложить результаты, каждое ребро будет учтено дважды. Именно поэтому в формуле стоит множитель одна вторая.

Идея доказательства верхней границы

Приведём индукционный аргумент. Возьмём в GG наибольшую клику размера k≤rk\le r. Вне её остаётся N=n−kN=n-k вершин. Каждая из них соединена не более чем с k−1k-1 вершинами клики: иначе клику можно было бы увеличить. Внутри клики ровно (k2)\binom{k}{2} рёбер. По индукции подграф на оставшихся вершинах имеет не более tr(N)t_r(N) рёбер. Для N<rN<r считаем пустые доли допустимыми; тогда Tr(N)T_r(N) - полный граф.

Поэтому e(G)≤tr(N)+(k−1)N+(k2)e(G)\le t_r(N)+(k-1)N+\binom{k}{2}. Чтобы сравнить это с tr(n)t_r(n), добавим к сбалансированным долям Tr(N)T_r(N) по одной вершине в kk наименьших долей. Новые вершины образуют клику. Сумма размеров выбранных долей не больше NN, поэтому число новых рёбер к старым вершинам не меньше (k−1)N(k-1)N. После добавления доли остаются сбалансированными. Значит, получен Tr(n)T_r(n), и его число рёбер не меньше правой части оценки. Это доказывает верхнюю границу; анализ случая равенства даёт единственность конструкции.

Случай треугольников и применение

При r=2r=2 получаем теорему Мантеля: граф на nn вершинах без треугольников имеет не более ⌊n2/4⌋\lfloor n^2/4\rfloor рёбер. Экстремальный пример - полный двудольный граф с долями, максимально близкими по размеру. Для 11 вершин это доли 6 и 5 и ровно 30 рёбер; 31 ребро уже гарантирует треугольник. Другую задачу о свойствах двудольных графов разбирает теорема Кёнига.

В анализе сетей оценка работает как сертификат существования плотной группы: зная только число вершин и рёбер, можно гарантировать клику при превышении порога. Теорема не находит конкретные вершины и не учитывает направления или веса связей. Для поиска самой группы нужна дополнительная алгоритмическая процедура; задачи обхода связей, например обход графа в ширину, отвечают на другие вопросы.

В обратную сторону число рёбер само по себе обычно не определяет структуру сети. Например, сети с одинаковым числом связей могут по-разному распределять их между вершинами: одна содержит плотную группу, другая избегает её. Экстремальный пример важен именно потому, что показывает границу знания, доступного по одному только счётчику рёбер. Для отдельных данных полезно дополнительно проверить соседей вершин и найти саму клику, если она существует.

Частые ошибки

  • Путать rr и r+1r+1. При трёх долях запрещается K4K_4, а треугольники возможны.
  • Округлять размеры долей независимо. Сумма должна оставаться равной nn: используйте частное и остаток.
  • Считать любую клику отсутствующей ниже порога. Предел гарантирует её выше порога; ниже она может как существовать, так и отсутствовать.
  • Применять формулу к мультиграфу. Неограниченные кратные рёбра разрушают конечную верхнюю границу.

FAQ

Должны ли все вершины графа участвовать в клике?

Нет. KkK_k состоит из любых kk попарно смежных вершин; остальные вершины и их рёбра произвольны.

Если рёбер ровно tr(n)t_r(n), клика Kr+1K_{r+1} невозможна?

Нет. Существует граф Турана с таким числом рёбер без запрещённой клики, но другой граф с тем же числом рёбер может её содержать. Равенство классифицирует только графы, которые уже известны как Kr+1K_{r+1}-свободные.

Что если вершин меньше размера запрещённой клики?

Тогда клика физически не помещается, и все (n2)\binom n2 рёбер допустимы. Конструкцию можно продолжить до этого случая, разрешив пустые доли.

Коротко

Теорема Турана связывает плотность простого графа с вынужденным появлением клики. Для запрета Kr+1K_{r+1} точную границу даёт полный rr-дольный граф с максимально равными долями. Одно дополнительное к этой границе ребро гарантирует запрещённую клику, а сам граф Турана показывает, что границу улучшить нельзя.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

8 ноября 20268 минут
Дополнение графа: определение и построение

Дополнение графа: определение и построение

Как построить дополнение простого графа по рёбрам и матрице смежности, проверить число рёбер и степени вершин и использовать связь клик с независимыми множествами.

8 ноября 20269 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Граф Кэли: как построить граф группы

Граф Кэли: как построить граф группы

Граф Кэли связывает операции группы с вершинами и рёбрами. Разбираем построение на вычетах по модулю 8, связность, кратчайшие пути и выбор образующих.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях связывает сумму степеней вершин и число рёбер графа. Разбираем доказательство, нечётные степени, петли и типовые задачи на примерах.

8 ноября 20267 минут
Ориентированный ациклический граф: что такое DAG

Ориентированный ациклический граф: что такое DAG

Ориентированный ациклический граф простыми словами: как читать вершины, рёбра и пути, проверить отсутствие циклов и рассчитать сроки работ на примере DAG.

8 ноября 20268 минут