Урок 18. Пути и циклы

Вероятность и статистика, 7 класс · Введение в теорию графов · ~45 минут

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

• Что такое путь в графе и как «пройти» от одной вершины к другой
• Что такое цикл и чем он отличается от обычного пути
• Какой граф называют связным, а какой — несвязным
• Как быстро проверить, связный граф или нет

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

Открой в телефоне карту метро. Тебе нужно доехать с одной станции на другую. Ты ведёшь пальцем по линиям, перескакивая со станции на станцию, пока не доберёшься до места. Вот это движение по рёбрам графа и называется путь.

📌 Запомни: Путь — это последовательность вершин, в которой каждые две соседние соединены ребром. Путь показывает, как «дойти» от одной вершины к другой по рёбрам графа.

Например, путь от А до Г: А → Б → В → Г. Каждый шаг — по существующему ребру. Можно и по-другому: А → Д → В → Г. Оба варианта — пути от А до Г.

💡 Лайфхак: Чтобы записать путь, веди пальцем по линиям и выписывай вершины, которые проходишь. Если между двумя выписанными вершинами нет ребра — значит, ты «перепрыгнул», так нельзя.

⏱ Попробуй сам: Найди на рисунке 1 путь от Д до Г. Сколько рёбер ты прошёл?

Цикл — путь, который вернулся домой

А что, если идти по рёбрам и вернуться туда, откуда начал, не повторяя дорогу? Это цикл.

📌 Запомни: Цикл — это путь, который начинается и заканчивается в одной и той же вершине, при этом не проходит дважды по одному ребру и не наступает дважды на одну вершину (кроме стартовой, она же финишная).

На рисунке 1 есть цикл: А → Б → В → Д → А. Стартовали в А и вернулись в А, обойдя четыре вершины по кругу.

⚠️ Частая ошибка: Просто сходить туда-обратно по одному ребру (А → Б → А) — это не цикл! Ты прошёл по одному и тому же ребру дважды. Цикл должен быть настоящим кольцом из разных рёбер.

🤔 А знаешь ли ты? Если в графе друзей есть цикл — значит, можно устроить «круговую рассылку»: передать записку по кругу так, что она вернётся к отправителю, побывав у каждого ровно раз. Удобно для секретиков!

Связный и несвязный граф

Представь карту метро, где две линии вообще никак не пересекаются — нет ни одной пересадки между ними. Тогда с одной части города на другую на метро не доедешь. Такой граф называется несвязным.

📌 Запомни: Граф связный, если из любой вершины можно дойти до любой другой по рёбрам. Если хотя бы до одной вершины добраться нельзя — граф несвязный.

На рисунке 2 граф распался на две части (их называют компонентами связности). Из А никак не дойти до Е — нет ни одного ребра-мостика между левой и правой группой.

Как проверить связность

Простой способ — игра «закрашивание»:

1. Выбери любую вершину и закрась её (например, в уме поставь галочку).
2. Закрась всех её соседей, до кого ведёт ребро.
3. Закрась соседей соседей, и так дальше, пока есть кого закрашивать.
4. Когда закрашивать стало некого — посмотри: все ли вершины закрашены? Если все — граф связный. Если осталась хоть одна незакрашенная — несвязный.

💡 Лайфхак: Это похоже на то, как растекается вода или ползёт краска по рёбрам. Если краска дотекла до всех вершин — граф связный.

⏱ Попробуй сам: Закрась граф на рисунке 1, начав с вершины А. Все ли вершины закрасились? Значит ли это, что он связный?

✍️ Разбор примеров

Пример 1. На рисунке 1 запиши путь от А до Г, проходящий через вершину Д.

Решение. От А есть ребро к Д. От Д есть ребро к В. От В есть ребро к Г. Путь: А → Д → В → Г.

Ответ: А → Д → В → Г.

Пример 2. Является ли А → Б → В → Д → А циклом в графе на рисунке 1?

Решение. Проверим каждое ребро: А–Б есть, Б–В есть, В–Д есть, Д–А есть. Старт и финиш — А, вершины не повторяются (кроме стартовой). Это цикл!

Ответ: да, это цикл.

Пример 3. Связный ли граф на рисунке 2? Сколько у него компонент связности?

Решение. Запустим «краску» из А: закрасим А, потом Б и В (соседи А), потом... больше соседей нет — Г, Д, Е остались белыми. Значит, не все вершины достижимы из А. Граф несвязный. Частей две: {А, Б, В} и {Г, Д, Е}.

Ответ: несвязный, 2 компоненты связности.

Пример 4. В графе вершины 1, 2, 3, 4 и рёбра 1–2, 2–3, 3–4. Связный ли он? Есть ли в нём цикл?

Решение. «Краска» из 1: закрашиваем 1 → 2 → 3 → 4. Все закрашены — граф связный. Цикла нет: это просто цепочка, вернуться в начало, не повторяя рёбер, невозможно.

Ответ: связный; цикла нет.

Пример 5. Добавим к графу из примера 4 ребро 4–1. Появился ли цикл? Связный ли граф теперь?

Решение. Теперь рёбра 1–2, 2–3, 3–4, 4–1 образуют кольцо. Цикл: 1 → 2 → 3 → 4 → 1. Граф связный (был связным и остался).

Ответ: да, появился цикл 1 → 2 → 3 → 4 → 1; граф связный.

💡 Запомни главное

• Путь — последовательность вершин, где соседние соединены рёбрами.
• Цикл — путь, который вернулся в стартовую вершину, не повторяя рёбер.
• Сходить по одному ребру туда-обратно — это не цикл.
• Граф связный, если из любой вершины можно дойти до любой другой.
• Проверка связности — «закрашивание»: растекись краской по рёбрам и посмотри, все ли вершины закрасились.

📝 Домашнее задание

1. На рисунке 1 найди два разных пути от Б до Д.
2. Запиши на рисунке 1 любой цикл, проходящий через вершину Д.
3. Граф: вершины П, Р, С, Т, рёбра П–Р, Р–С, П–С, Т (без рёбер). Связный ли он? Сколько компонент связности?
4. Нарисуй связный граф из 4 вершин, в котором нет ни одного цикла.
5. Нарисуй граф из 4 вершин, в котором есть цикл, проходящий через все четыре вершины.
6. Проверь связность графа методом «закрашивания»: вершины А, Б, В, Г, Д; рёбра А–Б, Б–В, Г–Д. Опиши шаги.
7. Объясни, почему путь А → Б → А не считается циклом.
8. ⭐ В графе 5 вершин, и он связный. Какое наименьшее число рёбер в нём может быть? Нарисуй пример с этим числом рёбер. Подсказка: чтобы «дотянуться» до каждой вершины, рёбер должно хватить, но лишних не нужно.