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

Рассматриваем пути по стрелкам. В D можно попасть из C, E и F. Число путей до каждой вершины считаем суммированием числа путей до вершин, из которых в неё ведут стрелки.

1. До B — 1 путь (A→B), до G — 1 (A→G).
2. До E ведут дороги из A, B и G: число путей до E равно 1 + 1 + 1 = 3.
3. До C ведут дороги из B и E: число путей до C равно 1 + 3 = 4.
4. До H ведут дороги из G и E, поэтому до H — 1 + 3 = 4 пути. До F ведут дороги из E и H, поэтому до F — 3 + 4 = 7 путей.
5. В D ведут дороги из C и F, следовательно, число путей равно 4 + 7 = 11.

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