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

По схеме дороги направлены так: A→B, A→E, A→G; B→C, B→E; G→E, G→H; E→C, E→D, E→F, E→H; C→D; H→F; F→D.

Посчитаем число путей до каждой вершины, начиная с A:

• A: 1 путь.
• B: 1 путь; G: 1 путь.
• E: из A, B и G — 1 + 1 + 1 = 3 пути.
• C: из B и E — 1 + 3 = 4 пути.
• H: из G и E — 1 + 3 = 4 пути.
• F: из E и H — 3 + 4 = 7 путей.
• D: из C, E и F — 4 + 3 + 7 = 14 путей.

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