4. На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

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

• до B — 1;
• до G — 1;
• до E: \(1+1+1=3\) пути (через A, B и G);
• до C: \(1+3=4\) пути;
• до H: \(1+3=4\) пути;
• до F: \(3+4=7\) путей.

В D можно попасть из E, C, F и H:

\(3+4+7+4=18\).

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