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