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

Исключим из подсчёта город D и все пути через него.

1. Через B к H можно пройти одним способом: A → B → H.
2. Через C к H можно пройти одним способом: A → C → G → H.
3. Через E к H есть два способа: A → E → G → H и A → E → F → H либо A → E → F → G → H. Последняя часть формулировки показывает два пути из F: напрямую в H или через G, поэтому вместе с путём через G из E всего три пути? Перечислим: A → E → G → H; A → E → F → H; A → E → F → G → H — всего 3.

Итого 1 + 1 + 3 = 5 путей.

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