Задание 6: Работаем с графом. Перед тобой схема дорог, связывающая города. По каждой дороге можно двигаться только в направлении указанном стрелкой. Сосчитай, сколько существует различных путей из города А в город К.

Решение:

Чтобы найти количество путей из города А в город К, будем двигаться по графу, считая количество путей до каждой следующей вершины.

1. Город А: из него начинается 1 путь.
2. Город Б: из А ведет 1 путь.
3. Город Г: из А ведет 1 путь.
4. Город Д: из А ведет 1 путь.
5. Город В: из Б приходит 1 путь.
6. Город Е: из Д приходит 1 путь.
7. Город Ж: из В приходит 1 путь.
8. Город К: из Е приходит 1 путь, из Ж приходит 1 путь.

Теперь просуммируем пути, ведущие в К:

• Пути, ведущие в К, приходят из Е и Ж.
• Количество путей до Е = 1 (через Д).
• Количество путей до Ж = 1 (через В, который получил 1 путь из Б, который получил 1 путь из А).
• Таким образом, общее количество путей из А в К = 1 (через Е) + 1 (через Ж) = 2.

Визуализация графа для наглядности:

Ответ: Существует 2 различных пути из города А в город К.