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

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

1. До A — 1 путь.
2. До B — 1 путь; до F — 1 путь.
3. До C — 1 путь. До E ведут дороги из A, B и F, поэтому до E: 1 + 1 + 1 = 3 пути.
4. До G ведут дороги из E и F, поэтому до G: 3 + 1 = 4 пути. До H ведёт дорога из G, значит, до H — 4 пути.
5. До D ведут дороги из B, C, E, G и H. Итого: 1 + 1 + 3 + 4 + 4 = 13.

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