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

Решение:

Для решения этой задачи построим граф и подсчитаем количество путей из А в И, проходящих через В.

Путь из А в И через В состоит из двух частей: А → В и В → И.

1. Пути из А в В:

• А → Б → В
• А → Г → В
• А → Д → В

Всего 3 пути из А в В.

2. Пути из В в И:

• В → Е → Ж → И
• В → Е → З → И
• В → Ж → И

Всего 3 пути из В в И.

3. Общее количество путей из А в И через В:

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

Количество путей = (Количество путей А → В) × (Количество путей В → И)

Количество путей = \( 3 \times 3 = 9 \) путей.

Ответ: 9.