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

Чтобы посчитать количество путей из города А в город Н, проходящих через город G, необходимо рассмотреть все возможные маршруты и сложить количество путей. 1. A -> D -> G -> H (1 путь) 2. A -> D -> C -> G -> H (1 путь) 3. A -> B -> F -> G -> H (1 путь) 4. A -> E -> F -> G -> H (1 путь) Теперь рассмотрим пути, включающие более длинные маршруты до G: 5. A -> D -> C -> F -> G -> H: Нет такого пути, так как нет пути из C в F. 6. A -> B -> F -> G -> H (уже посчитали) 7. A -> E -> F -> G -> H (уже посчитали) Итого, есть 4 пути: 1. A -> D -> G -> H 2. A -> D -> C -> G -> H 3. A -> B -> F -> G -> H 4. A -> E -> F -> G -> H Ответ: 4