Планарность и раскраска

Планарные графы

Граф планарный, если его можно нарисовать на плоскости без пересечений рёбер.

Формула Эйлера: для связного планарного графа V − E + F = 2, где F — число граней (включая внешнюю).

Следствие: E ≤ 3V − 6 (для V ≥ 3). Если нет треугольников: E ≤ 2V − 4.

Граф K₅ (полный на 5 вершинах): E=10, 3V−6=9. Следовательно, K₅ непланарен.

Граф K₃,₃ (полный двудольный 3+3): E=9, 2V−4=8 (биpartite). Непланарен.

Теорема Куратовского: граф планарен тогда и только тогда, когда не содержит подграф, являющийся подразделением K₅ или K₃,₃.

Раскраска графов

Хроматическое число χ(G) — минимальное k, при котором можно раскрасить вершины в k цветов так, чтобы соседние вершины имели разные цвета.

χ(G) = 1 ⟺ G — пустой (нет рёбер). χ(G) = 2 ⟺ G двудольный.

Теорема о четырёх красках (Аппель, Хакен, 1976): Каждый планарный граф имеет χ ≤ 4. Первое крупное доказательство, использующее компьютер (проверка 1936 конфигураций).

Применения: расписания (конфликты → рёбра), распределение частот (радиосети), раскраска карт.

Теорема Рамсея

R(m,n) — наименьшее N такое, что любое двухцветное рёбер-раскрашивание K_N содержит K_m в первом цвете или K_n во втором.

R(3,3) = 6: среди 6 человек всегда найдётся 3 взаимных знакомых или 3 взаимных незнакомца.

Теория Рамсея изучает «порядок в хаосе» — неизбежные закономерности в больших структурах.

Хроматический полином и алгебраические методы

Хроматический полином P(G, k) — число правильных k-раскрасок графа G. Это полином по k степени n (число вершин). Для пустого графа (нет рёбер): P = kⁿ. Для полного Kₙ: P = k(k−1)(k−2)...(k−n+1). Рекуррентность удаления-стягивания: P(G, k) = P(G−e, k) − P(G/e, k), где G−e — граф без ребра e, G/e — со стянутым ребром e.

Наименьшее k с P(G, k) > 0 — хроматическое число χ(G). Теорема о 4-красках ⟺ P(G, 4) > 0 для всех планарных G. Сложность вычисления P(G, k) — #P-полная задача (сложнее NP-полных — вычисление числа решений, а не просто его существование).

Теорема Рамсея: точные значения

Известны лишь немногие точные значения чисел Рамсея: R(3,3)=6, R(3,4)=9, R(3,5)=14, R(4,4)=18. Уже R(5,5) неизвестно: известно лишь 43 ≤ R(5,5) ≤ 48. Вычисление R(5,5) — одна из открытых проблем комбинаторики. Эрдёш заметил: если бы инопланетная цивилизация потребовала вычислить R(5,5) под угрозой уничтожения Земли, следовало бы направить все усилия математиков. Если бы они потребовали R(6,6) — следовало бы попробовать напасть первыми.

Верхняя оценка: R(m,n) ≤ C(m+n−2, m−1) — из комбинаторного доказательства через принцип ящика. Нижняя оценка Эрдёша-Спенсера: R(n,n) > 2^{n/2} (вероятностный метод, 1947). Этот разрыв между 2^{n/2} и 4^n отражает наши ограниченные знания.

Двудольность и алгоритм двудольного паросочетания

Теорема Холла (о паросочетании): Двудольный граф G=(A∪B, E) имеет паросочетание, насыщающее A, тогда и только тогда, когда для каждого S ⊆ A: |N(S)| ≥ |S| (N(S) — соседи S). Это условие Холла — необходимо и достаточно.

Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе за O(√V·E) — оптимальный алгоритм. Применения: задача о назначениях (workers↔tasks с минимальной стоимостью — венгерский алгоритм O(V³)), распределение студентов по проектам, паросочетание в онлайн-рекламе (рекламные слоты ↔ пользователи в реальном времени).

Теорема о 5-красках: конструктивное доказательство

В отличие от теоремы о 4-красках, теорема о 5-красках планарных графов имеет элегантное конструктивное доказательство (Кемпе, 1879, исправленное Херводом). Идея: по формуле Эйлера у планарного графа (V ≥ 3) всегда есть вершина степени ≤ 5. Удаляем её, 5-красим оставшийся (по индукции), возвращаем. Если ≤ 4 соседа — красим в свободный цвет. Если 5 соседей все разных цветов — используем аргумент цепей Кемпе для освобождения цвета.

Простота 5-красочного доказательства против сложности 4-красочного (компьютерная проверка 1936 случаев) иллюстрирует принципиальное различие: иногда чуть слабший результат допускает несравненно более изящное доказательство.

Ориентированные графы и задачи достижимости

В ориентированном графе (орграфе) рёбра имеют направление. Сильная связность: каждая вершина достижима из любой другой. Алгоритм Тарьяна: нахождение компонент сильной связности за O(V+E) — один проход DFS с использованием стека и нумерации обнаружения. Конденсация: граф сильно связных компонент — DAG (ациклический орграф). Задача достижимости в DAG решается топологической сортировкой за O(V+E). Применения: анализ зависимостей в компиляторах, обнаружение циклических зависимостей.

Численный пример: компоненты сильной связности

Задача: Орграф на 5 вершинах: 1→2, 2→3, 3→1, 3→4, 4→5, 5→4. Найти ССС алгоритмом Тарьяна.

Шаг 1: DFS из 1: нумерация обнаружения d[1]=0, d[2]=1, d[3]=2, d[4]=3, d[5]=4. Стек: [1,2,3,4,5].

Шаг 2: У вершины 5: ребро 5→4, d[4]=3 < d[5] → обратное ребро. low[5]=min(4,3)=3. d[5]=low[5]? Нет (4≠3). Возврат в 4.

Шаг 3: У вершины 4: low[4]=min(3,low[5])=3. d[4]=low[4]=3 → pop до 4: ССС₁={4,5}.

Шаг 4: Продолжаем: 3→1 — обратное ребро к d=0, low[3]=0. Возврат: low[2]=0, low[1]=0. d[1]=low[1]=0 → pop: ССС₂={1,2,3}. Конденсация — DAG: ССС₂→ССС₁. Так компилятор обнаруживает взаимную рекурсию.