Графы: количество путей и оптимальный маршрут
Коротко
Число путей в ориентированном графе без циклов считают последовательно: число путей в вершину равно сумме чисел путей во все вершины, из которых в неё ведёт дуга. Начальной вершине ставят 1. Если путь обязан пройти через вершину, перемножают число путей до неё и после неё; если не должен — считают её значение равным 0. В ЕГЭ 2027 задание 23 посвящено графам: подсчёту путей и поиску оптимального пути.
Метод
- Расположите вершины так, чтобы дуги вели «вперёд».
- Старту — 1.
- Для каждой следующей вершины: сумма значений всех вершин, из которых входит дуга.
Пример
Дуги: А→Б, А→В, Б→В, Б→Г, В→Г. А = 1; Б = 1; В = А + Б = 2; Г = Б + В = 3.
Ограничения
| Условие | Как считать |
|---|---|
| Через вершину X | пути(А→X) · пути(X→Г) |
| Не через X | значение X = 0 |
Кратчайший путь
Для весового графа: в каждую вершину записывают минимум из (значение предшественника + вес дуги).
На Python
E = {'А': 'БВ', 'Б': 'ВГ', 'В': 'Г', 'Г': ''}
def paths(u, t):
return 1 if u == t else sum(paths(v, t) for v in E[u])
print(paths('А', 'Г')) # 3
Типичные ошибки
- Считают вершину до того, как посчитаны все её предшественники.
- Перемножают вместо сложения при параллельных ветках.
Что дальше
Проверьте себя на заданиях этого типа в тренажёре Upward. Начните с диагностики по предмету: она покажет, какие номера уже получаются, а какие стоит подтянуть, и по её итогам соберётся личный план подготовки.
Как это выглядит в задании 23
Пример 1 из 2
Дуги: А→Б, А→В, Б→В, Б→Г, В→Г. Сколько путей из А в Г?
- Разбор
- А = 1, Б = 1, В = 2, Г = 3.
- Ответ
- 3
Пример 2 из 2
Путей из А в Х — 4, из Х в Я — 5. Сколько путей из А в Я через Х?
- Разбор
- Перемножаем.
- Ответ
- 20
Мини-тест: 5 вопросов
- Вопрос 1 из 5
Значение стартовой вершины?
Показать ответ
Ответ: 1.
Один пустой путь.
- Вопрос 2 из 5
Как найти число путей в вершину?
Показать ответ
Ответ: Сумма по входящим дугам.
Значения предшественников.
- Вопрос 3 из 5
Как учесть обязательную вершину?
Показать ответ
Ответ: Перемножить пути до и после.
Правило произведения.
- Вопрос 4 из 5
Как исключить вершину?
Показать ответ
Ответ: Считать её значение 0.
Через неё нет путей.
- Вопрос 5 из 5
Как найти кратчайший путь в весовом графе без циклов?
Показать ответ
Ответ: Минимум (предшественник + вес).
Динамика.
Проверьте всё задание 23, а не одну тему
Диагностика Upward покажет, какие задания ЕГЭ по информатике стоит подтянуть в первую очередь.
Уже есть аккаунт? Войти