Базовый (1 балл)
Время: 2-3 мин
Метод сложения вершин на графе
Задание №9 ОГЭ. Анализ информации в виде схем (Количество путей)
Тема: Динамическое программирование на графах, подсчет маршрутов из города А в город L
Определение количества различных путей из начального пункта А в конечный пункт по ориентированному графу (со стрелками).
1. Алгоритм динамического сложения на графе
Число путей в любую вершину $V$ равно сумме чисел путей во все вершины, из которых в $V$ ведут стрелки:
- Стартовой вершине A присваиваем значение 1 ($N(A) = 1$).
- Для каждой следующей вершины считаем число путей ТОЛЬКО тогда, когда известны значения ВСЕХ вершин, откуда в неё идут стрелки.
- Постепенно двигаемся слева направо до конечного пункта.
2. Как учитывать условие 'проходящих через пункт C':
Если путь ОБЯЗАН проходить через город C:
- Вычеркните все стрелки, которые идут из левой части графа в правую в обход города C!
Разновидности и прототипы задания на экзамене
1. Все пути из A в конечный пункт
Прямой подсчет суммы входящих стрелок для каждой вершины.
2. Пути, проходящие через обязательный пункт C
Удаление всех стрелок, идущих в обход пункта C.
3. Пути, НЕ проходящие через пункт C
Вычеркивание вершины C и всех входящих/исходящих из нее стрелок.
Типичные ошибки
✕ Не так
Ошибка: Посчитать вершину до того, как определены все входящие в нее стрелки
Если в вершину Д идут стрелки из Б, В и Г, а посчитаны только Б и В — результат будет неполным.
✓ Так
Правильно: Всегда дожидаться подсчета ВСЕХ источников входящих стрелок!
ГРОБ
ЛОВУШКА ОГЭ №9: Дорога, идущая в обход обязательного пункта
В условии: 'проходящих через город Ж'. Стрелка из В сразу в К минует Ж.
Как обойти
Сразу зачеркните стрелку В -> К крестиком, чтобы случайно не включить её в сумму для вершины К.
Лайфхаки на экзамене
- Подписывайте числа прямо возле кружков вершин на распечатанном бланке или черновике жирным карандашом.