Урок 20. Применение графов

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

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

• Как граф помогает разбираться в схемах дорог и метро
• Как находить и считать маршруты между двумя точками
• Как с помощью дерева вариантов подсчитывать число возможностей
• Как вообще «перевести» задачу из жизни на язык графа и решить её

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

За прошлые уроки ты собрал целый набор инструментов: вершины, рёбра, степени, пути, циклы, деревья. Пора пустить их в дело! Графы — это не просто кружочки на бумаге, это способ решать настоящие задачи: проложить маршрут, посчитать варианты, разобраться в запутанной схеме.

📌 Запомни: Главный приём — перевести задачу на язык графа. Спроси себя: что здесь вершины? Что здесь рёбра? Как только ответил — задача обычно становится в разы понятнее.

Схемы дорог и метро

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

Красные станции Б и Д — пересадочные: у них самые большие степени, через них проходит больше всего маршрутов.

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

Подсчёт маршрутов

Часто спрашивают: сколькими способами можно добраться из точки А в точку Б? Тут помогает аккуратный перебор путей. Главное — двигаться по системе, чтобы не пропустить и не повторить.

⚠️ Частая ошибка: Считать маршруты «на глаз» и сбиться. Лучше выписывай пути по очереди: сначала все, что идут через одну вершину, потом через другую. Так ничего не потеряется.

⏱ Попробуй сам: На рисунке 1 найди два разных маршрута от А до В. Какой из них короче (меньше перегонов)?

Дерево возможных вариантов — для подсчёта

Это, пожалуй, самое мощное применение графов в нашем предмете. Когда нужно сосчитать, сколько всего вариантов чего-то, рисуют дерево вариантов: каждый уровень — это один выбор, каждая ветка — один из его исходов.

🤔 А знаешь ли ты? Если на каждом шаге одинаковое число вариантов, их можно просто перемножить. Два броска монетки: 2 × 2 = 4. Три блюда по 2 варианта: 2 × 2 × 2 = 8. Дерево как раз показывает, почему варианты перемножаются — каждая ветка делится ещё на столько же.

Универсальный план решения задачи через граф

1. Определи вершины — что за объекты (города, люди, выборы).
2. Определи рёбра — какие связи между ними.
3. Нарисуй граф аккуратно.
4. Переформулируй вопрос на языке графа (связность? путь? степень? число листьев дерева?).
5. Реши и переведи ответ обратно на «человеческий».

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

Пример 1. На рисунке 1 можно ли доехать с станции А на станцию Ж? Если да — назови маршрут.

Решение. Это вопрос про связность. Ведём путь: А → Б → В → Ж. Все рёбра существуют. Доехать можно.

Ответ: да, например А → Б → В → Ж.

Пример 2. На рисунке 1 найди самый короткий маршрут от Г до Ж (по числу перегонов).

Решение. Г соединена с Д. Дальше из Д: к Б, к Е, к Г. Идём Г → Д → Е → Ж — это 3 перегона. Проверим, нет ли короче: любой путь от Г сначала обязан пройти через Д (других рёбер у Г нет), а от Д до Ж минимум 2 перегона (через Е или через Б→В). Значит, 3 перегона — минимум.

Ответ: Г → Д → Е → Ж, 3 перегона.

Пример 3. Сколько разных маршрутов от А до Д на рисунке 1, если не проходить через одну вершину дважды?

Решение. Из А единственное ребро — в Б. Из Б идём либо в В, либо в Д.

• А → Б → Д — маршрут 1.
• А → Б → В → Ж → Е → Д — маршрут 2. Других вариантов, не повторяя вершины, нет.

Ответ: 2 маршрута.

Пример 4. В магазине футболки трёх цветов (красная, синяя, белая) и двух размеров (M, L). Сколькими способами можно выбрать одну футболку? Построй дерево вариантов.

Решение. Первый уровень — цвет (3 ветки), от каждого — размер (по 2 ветки). Всего на концах 3 × 2 = 6.

Ответ: 6 способов.

Пример 5. Пять городов нужно соединить дорогами так, чтобы из любого можно было доехать в любой, а дорог построить как можно меньше. Сколько дорог понадобится? Какой это граф?

Решение. «Из любого в любой» = связный. «Как можно меньше рёбер» при связности = дерево. У дерева из 5 вершин ровно 5 − 1 = 4 ребра.

Ответ: 4 дороги; получится дерево.

Пример 6. Маршрутка едет по кольцу через остановки 1–2–3–4–5–1. Является ли эта схема деревом? Сколько в ней рёбер?

Решение. Это кольцо — значит, есть цикл, а в дереве циклов быть не может. Деревом не является. Рёбер 5 (1–2, 2–3, 3–4, 4–5, 5–1), как и вершин, — а у дерева их было бы на одно меньше.

Ответ: нет, не дерево (это цикл); рёбер 5.

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

• Чтобы решить задачу графом: найди вершины, найди рёбра, нарисуй, переформулируй вопрос.
• «Можно ли добраться» = вопрос про связность.
• «Сколько перегонов / какой короче» = считай рёбра в пути.
• «Сколько вариантов» = строй дерево вариантов; число исходов — это листья на концах веток.
• Если на каждом шаге одинаковое число выборов — варианты перемножаются.

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

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