На рисунке – схема дорог, связывающих города. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение:

Смотри, тут всё просто: нужно посчитать, сколько путей ведёт в каждый город, двигаясь от A к K. Логика такая: количество путей в город равно сумме путей из всех городов, из которых в него можно попасть.

1. В город А – 1 путь (изначально).
2. В город Б – 1 путь (из А).
3. В город Г – 1 путь (из А).
4. В город В – 1 (из А) + 1 (из Г) = 2 пути.
5. В город Д – 1 (из Б) + 2 (из В) = 3 пути.
6. В город Е – 2 (из В) + 1 (из Г) = 3 пути.
7. В город Ж – 3 (из Д) + 2 (из В) + 3 (из Е) = 8 путей.
8. В город З – 3 (из Е) + 8 (из Ж) = 11 путей.
9. В город И – 3 (из Д) + 8 (из Ж) = 11 путей.
10. В город К – 11 (из И) + 11 (из З) = 22 пути.

Ответ: 22

Проверка за 10 секунд: Проверь, правильно ли ты сложил пути на каждом этапе.

Доп. профит: База: Помни, что в задачах на графы важно внимательно считать все возможные пути и не упускать варианты.