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

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

1. До A — 1 путь.
2. До C — 1 путь (A → C), до B — 2 пути (A → B и A → C → B).
3. До D — 2 пути, до E — 2 пути.
4. До F — 1 + 2 = 3 пути: через C или E.
5. До G — 2 + 2 + 3 = 7 путей: через D, E или F.

Ответ: 7.