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