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

Для решения задачи схему дорог нужно развернуть и представить в виде графа.

Шаг 1. Из пункта А пути ведут в пункты B, D, и C:

Шаг 2. Из пункта B пути ведут в пункты E и D:

Шаг 3. Из пункта E один путь в пункт H, из пункта D пути ведут в E, H, F:

Шаг 4. Из пункта H в один путь в пункт G, из которого один путь в пункт I, то есть из пункта H один путь в пункт I:

Обратите внимание, завершенную ветвь графа стоит обвести, чтобы потом было легче считать пути.

Шаг 5. Из пункта E, как мы видим, существует только один путь в пункт I, так-же из пунктов H и F один путь. Отметим это на графе:

Шаг 6. По графу видно, что из пункта D в пункт I ведёт три пути. Отметим это:

Шаг 7. Осталось разобрать пункт С. Из него пути ведут в D и в F. Из D в I ведут три пути, из F в I — один. Отметим это на графе:

Подсчитаем количество конечных точек. 1+1+1+1+3+3+1=11

Ответ: 11