ОГЭ · ЗАДАНИЕ 9
Дороги: два ограничения · схема 8
Сколько различных путей ведёт из А в З? Движение возможно только по стрелкам. Маршрут должен проходить через Г, но не через Е.
Дороги текстом
А → Б; А → В; А → Г; Б → Г; Б → Д; Б → Е; В → Г; В → Е; Г → Д; Г → Е; Д → Е; Д → Ж; Е → Ж; Ж → З
Источник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 3
Перечислим допустимые пути, соблюдая направление стрелок и ограничение:
- А → Б → Г → Д → Ж → З
- А → В → Г → Д → Ж → З
- А → Г → Д → Ж → З
Получилось 3 маршрутов. Независимая проверка сложением числа путей во входящих вершинах даёт тот же ответ.