Пути в ориентированном графе — тренажёр для 11 класса
Ориентированный граф без циклов (DAG) — это схема, где стрелки показывают направление, а вернуться в ту же вершину нельзя. Классический пример — схема дорог с односторонним движением. В тренажёре задания построены на подсчёте количества путей от старта до финиша.
Что проверяет эта тема
- Понимать, что такое ориентированный граф.
- Различать DAG (без циклов) и граф с циклами.
- Считать количество путей от старта до финиша.
- Использовать метод «сумма входящих».
Формулы и правила
| Что ищем | Формула | Обозначения |
|---|---|---|
| Количество путей | ways[v] = Σ ways[u] для всех u → v | Число путей в вершину = сумма путей из всех входящих рёбер. |
| Начало | $ways[start] = 1$ | У стартовой вершины 1 путь (пустой). |
| Топологическая сортировка | Сначала — те, у кого нет входящих | Обходим вершины в порядке, где все входящие уже посчитаны. |
Разбор задачи по шагам
Задача: Дан DAG: A→B, A→C, B→D, C→D. Сколько путей от A до D?
Шаг 1. Расставляем «ways» для старта. ways[A] = 1. ways[B] = 0, ways[C] = 0, ways[D] = 0.
Шаг 2. Обходим вершины в топологическом порядке. A → B: ways[B] += ways[A] = 1. A → C: ways[C] += ways[A] = 1.
Шаг 3. Обходим следующие. B → D: ways[D] += ways[B] = 1. C → D: ways[D] += ways[C] = 1 + 1 = 2.
Шаг 4. Записываем ответ. Количество путей от A до D = 2.
Ещё один разбор
Задача. DAG: s→a, s→b, a→c, a→d, b→d, b→e, c→t, d→t, e→t. Сколько путей от s до t?
Ответ: 4
Типичные ошибки
Почему: Кажется, что путей мало
Как проверить: Всегда выписывайте ways для каждой вершины. Иначе легко потерять путь.
Почему: Не понимают, что нужна топологическая сортировка
Как проверить: Начинайте с вершин без входящих, потом двигайтесь вперёд. Иначе ways[u] будет ещё не посчитан.
Почему: Путают пути и рёбра
Как проверить: Путь — это последовательность вершин. Одно ребро — не путь.
Типы задач в тренажёре
В тренажёре:
- Малый DAG (4–5 вершин).
- DAG с ответвлениями.
- Сравнение путей.
- Найти все пути (перечислить).
Ответ проверяется сразу.
Кому и когда это нужно
Тема изучается в 11 классе. В ЕГЭ по информатике — задание № 13 и № 23.
Родителям: объясните через маршруты метро. От станции A можно доехать до D напрямую или через B или C. Сколько всего вариантов? Это и есть «количество путей».
Частые вопросы
Что такое DAG?
Directed Acyclic Graph — ориентированный граф без циклов. В нём нельзя вернуться в ту же вершину по стрелкам.
Зачем нужна топологическая сортировка?
Чтобы обходить вершины в правильном порядке: сначала те, у кого нет входящих рёбер. Иначе ways не посчитать.
Примеры задач
Готовы попробовать свои силы?
В тренажёре задачи проверяются автоматически, а после ошибки показывается пошаговое решение.
Перейти к задачам