E6 Графы (общее)

Идея метода: граф — это математическая модель для задач о связях, соединениях, отношениях между объектами. Вершины графа — объекты, рёбра — связи между ними. Огромный класс задач, которые «на вид» не имеют никакого отношения к графам, решается именно через введение подходящего графа и применение классических теорем.

Метод состоит в следующем: (1) интерпретировать объекты задачи как вершины, а отношения между ними — как рёбра; (2) применить базовые свойства графов (лемма о рукопожатиях, связность, двудольность, деревья, раскраска); (3) перевести вывод обратно в язык задачи.

Жизненная аналогия: карта дорог — это граф, где города — вершины, дороги — рёбра. Вопрос «можно ли проехать из A в B?» — это вопрос о связности. Вопрос «существует ли круговой маршрут?» — вопрос о цикле. Вся теория графов — это формализация подобных дорожных задач.

В олимпиадах E6 покрывает «общие» факты о графах: лемму о рукопожатиях, связность, деревья, двудольность и раскраску вершин/рёбер. Более специфические темы (эйлеровы и гамильтоновы пути, планарность, теорема Рэмси) относятся к подметодам.

• Лемма о рукопожатиях: $\sum_{v \in V} \deg(v) = 2|E|$. Следствие: число вершин нечётной степени чётно. Когда использовать: задачи на чётность степеней, существование вершин заданной степени.

• Критерий двудольности: граф двудолен тогда и только тогда, когда он не содержит нечётных циклов. Когда использовать: задачи на раскраску в два цвета, чётно/нечётная структура.

• Дерево: связный граф без циклов. У дерева на $n$ вершинах ровно $n-1$ рёбер. Когда использовать: оптимальные связующие структуры, задачи о числе рёбер.

• Теорема о мостах: ребро $e$ является мостом (его удаление нарушает связность) тогда и только тогда, когда $e$ не входит ни в один цикл. Когда использовать: задачи на связность и критические рёбра.

• Хроматическое число: минимальное число цветов для правильной раскраски вершин. Двудольный граф: хроматическое число $\leq 2$. Когда использовать: задачи на раскраску и совместимость.

• Ввести граф: формально определить $V$ (вершины) и $E$ (рёбра) через условие задачи, дать каждой вершине и ребру чёткий смысл.
• Применить лемму о рукопожатиях: если задача говорит о «количестве связей», сумма степеней = 2|E|.
• Проверить двудольность: попробовать двухраскраску (BFS/жадный алгоритм вручную) и найти нечётный цикл или убедиться в его отсутствии.
• Использовать теорему о деревьях: если граф связный и $|E| = |V| - 1$ — это дерево.
• Рассмотреть компоненты связности: разбить граф на компоненты и решить задачу в каждой.
• Применить принцип Дирихле к вершинам: если $n$ вершин и степени ограничены, найти вершины одинаковой степени.

Поверхностные признаки (что буквально написано):
- «$n$ городов соединены дорогами...», «$n$ людей, некоторые из которых знакомы...».
- «Докажите, что можно раскрасить в два цвета так, что...».
- «Докажите, что существует путь / цикл / маршрут...».

Структурные признаки (форма выражения, объекты):
- Есть конечное множество объектов и бинарное симметричное отношение между ними (знакомство, смежность, соединение).
- Условие ограничивает степени вершин (каждый знает ровно $k$ других).

Цель задачи (что от тебя хотят):
- Доказать существование / невозможность раскраски.
- Найти структурную характеристику: число рёбер, связность, хроматическое число.
- Доказать существование пути, цикла или особой конфигурации.

Задача 1. На вечеринке побывало $n$ человек. Докажите, что нашлись двое, которые познакомились с одинаковым числом гостей.

Источник: тренировочная (классика принципа Дирихле + лемма о рукопожатиях, ВсОШ-7-8)

Как думать (рассуждение ученика$):
1. $Что я вижу?* $n$ людей, знакомства — граф. Нужно найти двух с одинаковой степенью.$2. *$Метод: принцип Дирихле + леммы о графах. «Ящики» — возможные степени: от 0 до $n-1$. Но степени 0 и $n-1$ не могут быть одновременно (если кто-то знает всех, то нет незнакомых с нулём знакомых). Значит, реально только $n-1$ значений степени при $n$ вершинах.$3. *$Вывод*: по Дирихле — две вершины с одинаковой степенью.

Решение:
Построим граф: вершины — люди, рёбра — знакомства. Степень вершины $v$ — число знакомых человека. Каждая степень принадлежит $\{0, 1, \ldots, n-1\}$. Заметим, что степень $0$ (ни с кем не знаком) и степень $n-1$ (знаком со всеми) не могут существовать одновременно: если кто-то знаком со всеми, никто не может иметь 0 знакомств. Значит, реально только $n-1$ различных значений степени для $n$ вершин. По принципу Дирихле, два человека имеют одинаковую степень.

Ответ: утверждение доказано.

Что в этой задаче было главным: ключевое наблюдение о невозможности одновременного существования степеней 0 и $n-1$ сокращает число «ящиков» с $n$ до $n-1$.

Задача 2. В группе из 6 человек докажите, что найдутся три человека, которые знакомы попарно, или три человека, которые не знакомы ни с кем из двух других.

Источник: Теорема Рэмси $R(3,3)=6$ (классика ВсОШ, ТГ)

Как думать (рассуждение ученика$):
1. $Что я вижу?$ 6$ человек, двухцветный граф (знакомы/незнакомы). Нужно найти одноцветный треугольник.$2. *$Метод: рассмотрим степень одной вершины $v$ в «красном» (знакомства) или «синем» (незнакомства) графе.$3. *$Первый ход: у вершины $v$ есть 5 соседей. По Дирихле (5 в 2 «ящика»: красные и синие), не менее 3 соседей одного цвета. Пусть это красные: $u_1, u_2, u_3$.$4. *$Анализ тройки*: если среди $u_1, u_2, u_3$ есть хотя бы одно красное ребро — получаем красный треугольник. Если нет — все три ребра между ними синие — синий треугольник.

Решение:
Пометим знакомства красным, незнакомства синим. Рассмотрим произвольную вершину $v$. Из 5 остальных вершин по принципу Дирихле хотя бы $\lceil 5/2 \rceil = 3$ связаны с $v$ рёбрами одного цвета. Пусть $u_1, u_2, u_3$ — красные соседи $v$. Если хотя бы одно ребро $u_i u_j$ красное — тройка $v, u_i, u_j$ попарно знакома. Если все рёбра $u_1u_2, u_2u_3, u_1u_3$ синие — тройка $u_1, u_2, u_3$ попарно незнакома. В обоих случаях нужная тройка существует.

Ответ: утверждение доказано.

Что в этой задаче было главным: двухцветный принцип Дирихле («3 из 5 соседей одного цвета») — это ключ; дальнейший анализ — случаи.

• Ошибка: ввести граф, но не указать явно, что такое вершины и что такое рёбра — и потом путаться в рассуждении. → Как избежать: первые две строки решения: «Вершины — ..., рёбра — ..., степень вершины означает ...».

• Ошибка: при применении леммы о рукопожатиях забыть умножить на 2: написать $\sum \deg v = |E|$. → Как избежать: лемма: $\sum \deg v = 2|E}$.

• Ошибка: считать граф двудольным без проверки — встречается нечётный цикл. → Как избежать: всегда проверять двудольность явной двухраскраской.

• Ошибка: путать «связный граф» (есть путь между любыми двумя вершинами) и «полный граф» (между любыми двумя есть ребро). → Как избежать: явно написать определение в начале решения.

• Ошибка: в задаче Рэмси рассмотреть «2 из 5» вместо «3 из 5» — неверно применить принцип Дирихле. → Как избежать: $\lceil 5/2 \rceil = 3$, а не 2.