3. Тип 9 № 37197. На рисунке — схема дорог, связывающих города А, В, С, D, E, G, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город G?

Считаем количество путей до каждой вершины, складывая количества путей до всех вершин, из которых в неё ведут стрелки.

1. Из A можно попасть в B, C и E: до каждой из них существует по одному пути.
2. В D ведут дороги из B и E, поэтому путей до D: 1+1=2.
3. В F ведут дороги из C и E, поэтому путей до F: 1+1=2.
4. В G ведут дороги из D, E и F. Итого: 2+1+2=5.

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