Задание 9. На рисунке – схема дорог, связывающих города А, В, С, D, E, F, G, H, І и Ј. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ј, не проходящих через город D?

1. Определим все пути из А в J, не проходящие через D.
2. Пути через E: A -> E -> F -> H -> J (1 путь), A -> E -> I -> J (1 путь).
3. Пути через C: A -> C -> E -> F -> H -> J (1 путь), A -> C -> E -> I -> J (1 путь).
4. Пути через B: A -> B -> G -> F -> H -> J (1 путь), A -> B -> G -> I -> J (1 путь).
5. Пути через F: A -> E -> F -> H -> J (уже учтен), A -> C -> E -> F -> H -> J (уже учтен), A -> B -> G -> F -> H -> J (уже учтен).
6. Пути через H: A -> E -> F -> H -> J (уже учтен), A -> C -> E -> F -> H -> J (уже учтен), A -> B -> G -> F -> H -> J (уже учтен).
7. Пути через I: A -> E -> I -> J (уже учтен), A -> C -> E -> I -> J (уже учтен), A -> B -> G -> I -> J (уже учтен).
8. Всего путей: A->E->F->H->J, A->E->I->J, A->C->E->F->H->J, A->C->E->I->J, A->B->G->F->H->J, A->B->G->I->J. Это 6 путей.
9. Проверим пути, которые не проходят через D. Все перечисленные пути не проходят через D. Итого 6 путей.