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