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

Обозначим количество путей из А до каждой вершины. В город А можно попасть одним способом: начать путь в А.

В В ведут дороги из А и С. В С ведёт дорога из А, поэтому до В можно добраться двумя способами: напрямую из А или через С. До С — одним способом.

До Е можно попасть из В или С: 2 + 1 = 3 пути.

До D можно попасть из А или С: 1 + 1 = 2 пути. До F можно попасть из D, значит, до F — 2 пути.

В G ведут дороги из С, Е и F. Следовательно, всего путей: 1 + 3 + 2 = 6.

Ответ: 6 путей.