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

Сначала найдём количество путей от A до D. В D можно попасть из A напрямую, из B или из C. До B ведёт один путь, до C — один путь, поэтому всего до D: 1 + 1 + 1 = 3 пути.

Теперь посчитаем пути от D до H. Из D можно попасть в F напрямую или пройти через F? По схеме из D ведут дороги в F и G; из F есть дорога в G, а из G — в H. Поэтому от D до H есть два пути: D → G → H и D → F → G → H.

Кроме того, из D ведёт дорога к E? Нет, стрелка направлена из C в E, а из E идут дороги в G и H. Следовательно, пути через E не проходят через D и не учитываются.

Каждый путь от A до D можно сочетать с каждым путём от D до H: 3 · 2 = 6.

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