Задание 19 Параграф 10 ГДЗ Босова 11 класс (Информатика)

Задача

На рисунке представлена схема дорог, связывающих города А, В, С, D, Е, F, G, Н, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько разных путей существует из города А в город J?

Подробный ответ

Обозначим в скобках количество путей, ведущих в каждую вершину. Тогда для любой вершины число путей равно сумме чисел путей во всех вершинах, из которых в неё можно попасть.

Получаем:

$$B(1),\ D(1),\ C(3),\ E(1),\ F(1),\ G(1+3+1=5),$$

$$H(5),\ I(5),\ J(5+5=10).$$

Значит, из города $$A$$ в город $$J$$ существует $$10$$ различных путей.