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

Задание №5

В этой задаче нужно посчитать количество путей из города А в город К, обязательно проходящих через город Г.

Рассмотрим возможные пути, двигаясь от города к городу:

• Из А в Г:
• А -> Б -> Г
• А -> В -> Г
• А -> Г

Получается, что есть 3 пути из А в Г.

• Из Г в К:
• Г -> Д -> Ж -> К
• Г -> Д -> И -> К
• Г -> Е -> Ж -> К
• Г -> Е -> И -> К

Получается, что есть 4 пути из Г в К.

Чтобы найти общее количество путей из А в К через Г, нужно перемножить количество путей из А в Г и количество путей из Г в К.

\[ 3 \times 4 = 12 \]

Ответ: 12