В рамках образовательного проекта MIT OpenCourseWare опубликована лекция, посвященная одному из самых изящных применений вероятностного метода в комбинаторике и теории графов — доказательству неравенства для числа пересечений (Crossing Number Inequality). Лектор наглядно демонстрирует, как объединение топологии, комбинаторики и теории вероятностей позволяет решать сложные геометрические задачи. Процесс «бутстрэппинга» (самоусиления), рассматриваемый в материале, превращает тривиальную топологическую оценку в мощный математический инструмент.
📐 Понятие числа пересечений графа 0:12
При визуализации абстрактных графов на плоскости одной из ключевых задач является минимизация пересечений ребер. Некоторые графы можно расположить на плоскости вообще без пересечений — такие графы называются планарными. Классическим примером служит полный граф на четырех вершинах ($K_4$), который легко изобразить в двухмерном пространстве без пересекающихся линий.
Однако для более сложных структур, таких как полный граф на пяти вершинах ($K_5$), планарное представление невозможно. Профессор отмечает, что это фундаментаческий топологический факт: $K_5$ гарантированно будет иметь хотя бы одно пересечение при любом способе укладки на плоскости непрерывными кривыми. Минимально возможное количество таких пересечений для конкретного графа $G$ называется его числом пересечений и обозначается как $cr(G)$. Для графа $K_5$ это число равно единице.
Естественным образом возникает вопрос: если граф содержит огромное количество ребер, обязано ли число его пересечений быть пропорционально большим? Неравенство для числа пересечений утверждает, что для любого графа $G = (V, E)$, у которого количество ребер не менее чем в четыре раза превышает количество вершин ($|E| \ge 4|V|$), справедливо следующее соотношение:
$$cr(G) \ge c \cdot \frac{|E|^3}{|V|^2}$$
Здесь $c$ представляет собой некоторую абсолютную константу. Из этого утверждения вытекает важное следствие: если граф является плотным и количество его ребер соотносится с числом вершин как $|E| = \Theta(|V|^2)$, то число пересечений растет с огромной скоростью и составляет не менее $\Theta(|V|^4)$. Лектор подчеркивает, что данный порядок величины является оптимальным, поскольку даже при случайном расположении вершин на плоскости общее число пересечений пар ребер не может превысить квадрата от их количества ($|E|^2$).
🗺️ Шаг 1: Анализ планарных графов и формула Эйлера 4:00
Доказательство неравенства лектор разделяет на три последовательных этапа, начиная с базовых топологических свойств планарных графов, то есть графов с нулевым числом пересечений.
Фундаментальный вывод этого этапа заключается в том, что в любом планарном графе количество ребер жестко ограничено сверху линейной функцией от числа вершин:
$$|E| \le 3|V|$$
В терминах теории графов это означает, что средняя степень вершины в любой планарной структуре не может превышать шести. Этот результат напрямую выводится из знаменитой топологической формулы Эйлера для плоских графов:
$$|V| - |E| + |F| = 2$$
В данной формуле переменная $|F|$ обозначает количество граней (включая внешнюю неограниченную область), на которые граф делит плоскость. В качестве иллюстрации лектор предлагает рассмотреть простой граф с 4 вершинами, 5 ребрами и 3 гранями, для которого тождество Эйлера $4 - 5 + 3 = 2$ выполняется безупречно. Комбинируя формулу Эйлера с ограничением на минимальную длину цикла, ограничивающего грань, математики получают искомое неравенство $|E| \le 3|V|$.
✂️ Шаг 2: От одного пересечения к множеству 6:34
Второй этап позволяет перекинуть мост от идеальных планарных графов к произвольным структурам, требующим пересечений. Идея лектора проста, но эффективна: если исходный граф $G$ не является планарным, его можно сделать таковым, последовательно удаляя по одному ребру из каждой точки пересечения.
Если в процессе укладки графа мы избавимся от части ребер, формирующих пересечения, то в остатке мы гарантированно получим планарный граф. К получившемуся очищенному графу применимо неравенство из первого шага:
$$|E| - cr(G) \le 3|V|$$
Путем несложной алгебраической перестановки слагаемых лектор выводит базовую нижнюю оценку для числа пересечений:
$$cr(G) \ge |E| - 3|V|$$
Этот промежуточный результат доказывает, что как только количество ребер превышает $3|V|$, в графе неизбежно появляется хотя бы одно пересечение. Однако полученная оценка является довольно слабой. Например, для плотных графов, где количество ребер пропорционально квадрату вершин ($|E| \sim |V|^2$), эта формула предсказывает лишь квадратичный рост числа пересечений, в то время как реальный масштаб проблемы, как было показано ранее, требует четвертой степени.
🎲 Шаг 3: Вероятностный метод и бутстрэппинг 9:19
Чтобы преодолеть слабость промежуточной оценки, на третьем этапе применяется вероятностный метод — стратегия, называемая лектором «бутстрэппингом» (самоусилением). Метод позволяет превратить слабое неравенство в оптимальное с помощью случайного сэмплирования.
Алгоритм доказательства выглядит следующим образом:
- Выбирается некоторое фиксированное значение вероятности $p$ в диапазоне от 0 до 1, точное значение которого будет определено позже.
- Из исходного детерминированного графа $G$ формируется случайный подграф $G'$. Каждая вершина графа $G$ сохраняется в подграфе $G'$ с вероятностью $p$ независимо от остальных вершин. Если вершина удаляется, то автоматически уничтожаются и все инцидентные ей ребра.
- В результате формируется новый случайный граф $G'$, состоящий из подмножества оставшихся вершин $V'$ и подмножества ребер $E'$, соединяющих эти выжившие вершины.
Поскольку $G'$ является полноценным графом, к нему применимо базовое неравенство, доказанное на втором шаге: $cr(G') \ge |E'| - 3|V'|$. Это соотношение выполняется для абсолютно любой случайной реализации подграфа, а значит, оно справедливо и для математического ожидания величин:
$$\mathbb{E}[cr(G')] \ge \mathbb{E}[|E'|] - 3\mathbb{E}[|V'|]$$
Используя свойство линейности математического ожидания, лектор последовательно вычисляет средние значения для каждого компонента уравнения:
- Математическое ожидание числа вершин $\mathbb{E}[|V'|]$: Поскольку каждая вершина сохраняется с вероятностью $p$, среднее число оставшихся вершин равно $p \cdot |V|$.
- Математическое ожидание числа ребер $\mathbb{E}[|E'|]$: Ребро сохраняется в подграфе тогда и только тогда, когда выживают обе его концевые вершины. Так как выбор происходит независимо, вероятность этого события равна $p^2$, а среднее число ребер составляет $p^2 \cdot |E|$.
- Математическое ожидание числа пересечений $\mathbb{E}[cr(G')]$: Чтобы конкретное пересечение ребер перенеслось из исходного чертежа графа $G$ в новый граф $G'$, должны уцелеть все четыре вершины, формирующие две пересекающиеся линии. Вероятность сохранения такого квартета вершин равна $p^4$. Даже с учетом того, что для уменьшенного графа $G'$ теоретически можно найти более эффективную укладку с меньшим числом пересечений, неравенство $\mathbb{E}[cr(G')] \le p^4 \cdot cr(G)$ остается строгим и корректным.
Подставляя вычисленные математические ожидания в исходную формулу, математики получают фундаментальное неравенство:
$$p^4 \cdot cr(G) \ge p^2 \cdot |E| - 3p \cdot |V|$$
Разделив обе части на $p^4$, лектор изолирует искомую переменную числа пересечений:
$$cr(G) \ge p^{-2} \cdot |E| - 3p^{-3} \cdot |V|$$
На финальной стадии остается лишь оптимизировать свободный параметр $p$. Для максимизации правой части и получения красивой константы лектор выбирает значение $p = \frac{4|V|}{|E|}$. Профессор обращает внимание на критическую важность начального условия теоремы $|E| \ge 4|V|$: именно оно гарантирует, что вероятность $p$ не превысит единицу и математическое построение не потеряет физический смысл.
После подстановки оптимального $p$ в формулу, все вычисления сводятся к итоговому результату:
$$cr(G) \ge \frac{1}{64} \cdot \frac{|E|^3}{|V|^2}$$
Таким образом, теорема успешно доказана, а абсолютная константа $c$ зафиксирована на уровне $1/64$. По мнению лектора, данное доказательство служит великолепной и вдохновляющей демонстрацией возможностей вероятностного метода в современной комбинаторике. Изящный трюк с сэмплированием позволил преодолеть ограничения слабой топологической оценки и вывести мощную закономерность, определяющую структуру сложных сетей.
