Урок 4. Графы: точки, линии и рукопожатия

Олимпиадная математика · ~40 минут

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

🎯 Что ты узнаешь

Что такое граф, вершина, ребро, степень вершины
Лемму о рукопожатиях и её мгновенные следствия
Эйлеровы пути и загадку мостов Кёнигсберга
Деревья и идею связности

📖 Разбираемся в теме

Язык графов

Граф — это набор вершин (точек) и рёбер (линий, соединяющих пары вершин). Степень вершины — число рёбер, выходящих из неё. Граф связен, если из любой вершины можно добраться до любой другой по рёбрам.

Здесь 4 вершины. Степени: у верхней-средней вершины степень 3, у остальных — 2, 2, 1... посчитай сам как упражнение.

Лемма о рукопожатиях

📌 Запомни: Сумма степеней всех вершин графа равна удвоенному числу рёбер: $\sum \deg(v) = 2E$.

Почему: каждое ребро вносит $+1$ в степень каждого из двух своих концов, то есть $+2$ в общую сумму. Отсюда сразу:

📌 Следствие: Число вершин нечётной степени всегда чётно.

(Ведь сумма всех степеней чётна; чётные слагаемые на чётность не влияют, значит нечётных слагаемых чётное число.)

🤔 А знаешь ли ты? Отсюда «задача о рукопожатиях»: на любой вечеринке число людей, пожавших нечётное количество рук, — чётно. Вершины — люди, рёбра — рукопожатия.

Эйлеровы пути и мосты Кёнигсберга

Эйлеров путь — маршрут, проходящий по каждому ребру ровно один раз. Если он к тому же замкнут (возвращается в старт) — это эйлеров цикл.

В городе Кёнигсберге было 7 мостов через реку с двумя островами, и горожане спорили: можно ли пройти по всем мостам ровно по разу и вернуться домой? Эйлер перевёл это на граф (берега и острова — вершины, мосты — рёбра) и доказал, что нельзя.

📌 Критерий Эйлера: Связный граф имеет эйлеров цикл тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь (незамкнутый) существует тогда и только тогда, когда вершин нечётной степени ровно 0 или 2.

Идея «только тогда»: проходя вершину «насквозь», путь тратит 2 ребра (вошёл-вышел). Значит все степени должны быть чётны — кроме, может быть, старта и финиша незамкнутого пути. В Кёнигсберге все четыре вершины имели нечётную степень (3, 3, 3, 5) — их четыре, а можно не больше двух. Поэтому обхода нет.

Деревья

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

💡 Полезно помнить: связный граф с $n$ вершинами имеет $\ge n-1$ рёбер. Если ровно $n-1$ — это дерево.

⚠️ Не путай: «нет эйлерова цикла» не значит «граф несвязен». Связность и эйлеровость — разные свойства.

✍️ Разбор задачи

Задача. В стране 15 городов, и из каждого выходит ровно 3 дороги. Докажи, что такого быть не может (или найди ошибку в условии).

Решение. Города — вершины, дороги — рёбра графа. По условию степень каждой из 15 вершин равна 3. Тогда сумма степеней равна $15\cdot 3 = 45$ — нечётное число. Но по лемме о рукопожатиях сумма степеней равна $2E$ — всегда чётна. Нечётное число не может равняться чётному. Противоречие, значит такой страны не существует. ∎

Мораль: нельзя иметь нечётное число вершин, все нечётной степени. Это следствие рукопожатий работает как инвариант чётности из первого урока.

Задача (эйлеров путь). Можно ли нарисовать конверт (прямоугольник с диагональю крыши и двумя диагоналями внутри — классический «открытый конверт») одним росчерком, не отрывая карандаша и не проводя ни одной линии дважды?

Решение. Вершины конверта — 5 точек. Посчитаем степени. У «открытого конверта» (прямоугольник + треугольная крыша над ним, но без нижней стороны — нет, разберём стандартный: прямоугольник со всеми сторонами, двумя диагоналями и «крышей»)... возьмём классику: две нижние вершины имеют степень 4, две средние (углы прямоугольника, где сходится крыша) — степень 3, верхняя точка крыши — степень 2. Вершин нечётной степени ровно две (степени 3). По критерию Эйлера незамкнутый эйлеров путь существует — значит можно нарисовать одним росчерком, начав в одной вершине нечётной степени и закончив в другой. ∎

📝 Задачи

В компании из 9 человек каждый пожал руку ровно трём другим. Возможно ли это? Обоснуй.
Может ли в графе быть ровно одна вершина нечётной степени? Ровно три?
На плоскости отметили 6 точек. Докажи, что если каждая соединена ребром хотя бы с тремя другими, то в графе есть цикл.
В графе 10 вершин, и он связен. Какое наименьшее число рёбер в нём может быть? А наибольшее (без кратных рёбер и петель)?
Можно ли обойти все клетки шахматной доски $3\times 3$ ходом коня, побывав в каждой ровно раз? Переведи на язык графа и попробуй понять, где застреваешь. (Центральная клетка — особенная.)
Нарисуй граф из букв «А», «Б», «В» и т.п. и придумай два разных рисунка (фигуры), про которые можно спросить «рисуется ли одним росчерком»: один — да, другой — нет. Обоснуй ответы через степени.
В стране несколько городов, некоторые соединены дорогами. Известно, что из каждого города выходит хотя бы 2 дороги. Докажи, что в стране есть замкнутый маршрут (цикл), не проходящий по одной дороге дважды.
⭐ На вечеринке 2026 человек. Докажи, что можно рассадить их за круглый стол так, чтобы каждый сидел рядом со своими знакомыми... нет, точнее: докажи, что если каждый из $n$ человек знаком хотя бы с $n/2$ другими, то всех можно усадить за один круглый стол так, что любые двое соседей знакомы. (Это теорема Дирака; докажи хотя бы идею для маленького случая $n=4$ и опиши, почему условие $n/2$ существенно.)