В лекции от образовательного проекта MIT OpenCourseWare подробно разбирается применение вероятностного метода в теории графов на примере теоремы Каро — Вея и теоремы Турана. Преподаватель демонстрирует, как использование инструментов теории вероятностей, таких как случайные перестановки и линейность математического ожидания, позволяет доказывать существование крупных независимых множеств и клик. Этот подход заложил основу экстремальной теории графов, изучающей максимальное или минимальное количество элементов в сетях при заданных структурных ограничениях.
🧩 Базовые понятия: независимые множества и теорема Каро — Вея 0:11
В теории графов одной из фундаментальных задач является поиск и оценка размеров особых подмножеств вершин. Независимое множество в графе представляет собой подмножество вершин, в котором никакие две вершины не являются смежными (то есть не соединены ребром).
В качестве простого примера лектор приводит цикл из четырех вершин. Если пронумеровать их последовательно от 1 до 4, то вершины 1 и 4 будут смежными, и их выбор не образует независимое множество. Однако если выбрать противоположные вершины (например, 1 и 3), они не будут связаны ребром, что полностью соответствует определению независимого множества.
Главный вопрос, который волнует исследователей: какого максимального размера независимое множество можно гарантированно найти в произвольном графе? Ответ на него дает теорема Каро — Вея (в транскрипте ошибочно названная «теоремой Кона — Вея»). Она утверждает, что любой граф $G$ содержит независимое множество, размер которого не меньше определенной величины, вычисляемой через степени его вершин:
$$\sum_{v \in V(G)} \frac{1}{d(v) + 1}$$
Здесь $d(v)$ обозначает степень вершины $v$, то есть количество выходящих из нее ребер.
🎲 Вероятностный метод в действии: случайные перестановки 1:38
Для доказательства теоремы Каро — Вея лектор применяет вероятностный метод. Суть подхода заключается в том, что вместо прямого конструирования независимого множества задается случайный процесс, который на выходе с высокой долей вероятности дает нужный результат.
Алгоритм доказательства выглядит следующим образом:
- Все вершины графа $G$ упорядочиваются случайным образом. Рассматривается абсолютно случайная и равномерно распределенная перестановка вершин.
- Формируется множество вершин $I$ по особому правилу: вершина $v$ включается в него тогда и только тогда, когда она появляется в случайном порядке раньше всех своих соседей.
Чтобы наглядно показать этот механизм, лектор разбирает случайный порядок для четырехугольного цикла с вершинами 1, 2, 3, 4 и ребрами (1-2), (2-4), (3-4) и (1-3). Допустим, случайная перестановка выдала их именно в таком порядке.
- Первая вершина (1) оказывается в списке раньше своих соседей (2 и 3), поэтому она включается в множество $I$.
- Вторая вершина (2) идет после своего соседа (1), поэтому она исключается.
- Третья вершина (3) также идет после соседа (1), а четвертая (4) — после соседей 2 и 3, поэтому они не попадают в итоговый набор.
В данном конкретном примере множество $I$ будет состоять всего из одной вершины, но в более крупных графах этот метод собирает гораздо больше элементов.
Лектор подчеркивает, что сформированное таким образом множество $I$ всегда будет независимым. Если бы в нем оказались две смежные вершины, это означало бы, что в случайной перестановке одна из них шла раньше другой. Но тогда вторая вершина нарушила бы правило отбора, так как перед ней уже стоял бы ее сосед, что принципиально невозможно.
Для оценки размера множества $I$ высчитывается вероятность попадания в него каждой отдельной вершины. Поскольку граф упорядочен случайно, для вершины $v$ и всех ее $d(v)$ соседей существует ровно один благоприятный исход из $d(v) + 1$ возможных, когда $v$ занимает первое место. Таким образом, вероятность равна:
$$P(v \in I) = \frac{1}{d(v) + 1}$$
Используя свойство линейности математического ожидания, лектор суммирует эти вероятности по всем вершинам графа. Средний (ожидаемый) размер множества $I$ оказывается в точности равен сумме, заявленной в теореме Каро — Вея. Из этого математически следует вывод: раз среднее значение равно этой величине, то в графе обязательно существует хотя бы один конкретный вариант перестановки, который дает независимое множество размером не меньше среднего.
🔄 Переход к кликам: концепция дополнения графа 6:34
Как отмечает лектор, содержательный смысл теоремы Каро — Вея заключается в следующем: если в графе преобладают вершины с небольшими степенями (то есть у них мало соседей), то в нем гарантированно присутствует крупное независимое множество.
Этот результат можно легко инвертировать, если рассмотреть операцию дополнения графа. Дополнение графа — это операция, при которой все существующие ребра удаляются, а на месте их отсутствия, наоборот, проводятся новые. При таком переходе независимые множества исходного графа превращаются в клики в его дополнении. Клика представляет собой полный подграф — группу вершин, где абсолютно все пары соединены друг с другом.
Применив теорему Каро — Вея к дополнению графа, лектор выводит важное следствие: любой граф с $n$ вершинами обязательно содержит клику, размер которой не меньше следующей величины:
$$\sum_{v \in V(G)} \frac{1}{n - d(v)}$$
В данном выражении знаменатель отражает степень вершины в дополненном графе, увеличенную на единицу, что трансформируется в $n - d(v)$.
📊 Теорема Турана и экстремальная теория графов 8:48
Выведенное следствие позволяет напрямую перейти к доказательству знаменитой теоремы Турана, которая считается фундаментальным и отправным результатом в экстремальной теории графов. Теорема Турана отвечает на зеркальный вопрос: сколько максимум ребер может содержать граф, если в нем нет клики определенного размера?
Формулировка теоремы Турана гласит: если граф с $n$ вершинами имеет строго больше ребер, чем:
$$\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$$
то такой граф гарантированно содержит клику размером более чем $r$ вершин.
Данная граница является неулучшаемой (оптимальной). В качестве доказательства оптимальности лектор приводит пример для случая, когда общее число вершин $n$ нацело делится на $r$. Если разделить $n$ вершин на $r$ равных непересекающихся групп и провести все возможные ребра между вершинами из разных групп, но не проводить ни одного ребра внутри самих групп, получится так называемый полный дольный (или $r$-дольный) граф Турана.
Простой подсчет показывает, что такой граф содержит ровно $\left(1 - \frac{1}{r}\right) \frac{n^2}{2}$ ребер. При этом в нем физически невозможно собрать клику из $r + 1$ вершин, так как по принципу Дирихле как минимум две вершины попадут в одну и ту же группу, а между ними ребер нет. Максимальная клика здесь собирается путем взятия ровно по одной вершине из каждой доли, что дает клику размера $r$.
Для финального доказательства теоремы Турана лектор использует свойство выпуклости функции $f(x) = \frac{1}{n - x}$. Благодаря выпуклости и неравенству Йенсена, сумму из следствия теоремы Каро — Вея можно ограничить снизу через среднюю степень графа:
$$\sum_{v \in V(G)} \frac{1}{n - d(v)} \ge \frac{n}{n - d_{\text{cp}}}$$
Если подставить в это уравнение условие, что число ребер строго превышает ограничение Турана, то средняя степень графа окажется достаточно высокой. В результате несложных алгебраических преобразований итоговое выражение для минимального размера клики становится строго больше, чем $r$.
Теорема Турана не просто решает конкретную комбинаторную задачу, но и открывает целое направление — экстремальную теорию графов, которая исследует глобальное поведение и структуру сетей на основе локальных ограничений.
