Задание 4. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город И, проходящих через город Г?

Решение:

Для решения задачи будем использовать метод подсчёта путей. Найдём количество путей из города А в город Г, а затем из города Г в город И.

Пути из А в Г:

• А → Б → Г: 1 путь
• А → В → Г: 1 путь

Всего из А в Г: 1 + 1 = 2 пути.

Пути из Г в И:

Из города Г мы можем попасть в И через другие города. Необходимо рассмотреть все возможные пути:

• Г → Д → И: 1 путь
• Г → Е → Ж → И: 1 путь
• Г → Е → З → И: 1 путь
• Г → В → Ж → И: 1 путь (но дорога из В в Ж есть, а из Г в В нет, значит, такой путь невозможен от Г)

Давайте пройдёмся по каждому городу, подсчитывая количество путей из А:

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из Б) + 1 (из В) = 2
• Д: 2 (из Г)
• Е: 2 (из Г)
• Ж: 1 (из Д) + 1 (из Е) + 1 (из В, но В ведёт в Г, а не в Ж напрямую)

Переосмыслим задачу, используя графовые подходы.

Пути из А в Г:

• А → Б → Г (1 путь)
• А → В → Г (1 путь)
• Всего путей из А в Г = 2.

Пути из Г в И:

• Г → Д → И (1 путь)
• Г → Е → Ж → И (1 путь)
• Г → Е → З → И (1 путь)

Нужно учесть все возможные маршруты из А, которые проходят через Г.

Подсчёт путей из А:

• А: 1
• Б: 1 (из А)
• В: 1 (из А)
• Г: 1 (из Б) + 1 (из В) = 2
• Д: 2 (из Г)
• Е: 2 (из Г)
• Ж: 1 (из Д) + 1 (из Е) = 2
• З: 1 (из Е)
• И: 1 (из Д) + 2 (из Ж) + 1 (из З) = 4

Всего путей из А в И = 4.

Но нам нужны пути, проходящие через Г. Пути, которые идут из А в Г, а затем из Г в И.

Пути из А в Г:

• А → Б → Г (1 путь)
• А → В → Г (1 путь)
• Всего: 2 пути

Пути из Г в И:

Теперь рассмотрим пути, которые начинаются из Г и ведут в И.

• Из Г есть дороги в Д и Е.
• Пути через Д: Г → Д → И (1 путь)
• Пути через Е:
• Г → Е → Ж → И (1 путь)
• Г → Е → З → И (1 путь)
• Всего путей из Г в И = 1 + 1 + 1 = 3 пути.

Теперь умножим количество путей из А в Г на количество путей из Г в И:

2 пути (А → Г) * 3 пути (Г → И) = 6 путей.

Проверим более детально:

Пути из А:

• А → Б → Г → Д → И
• А → Б → Г → Е → Ж → И
• А → Б → Г → Е → З → И
• А → В → Г → Д → И
• А → В → Г → Е → Ж → И
• А → В → Г → Е → З → И

Действительно, получилось 6 путей.

Ответ: 6