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

Решение:

Будем считать количество путей, исходящих из города А, идущих последовательно через города схемы, и приходящих в город З.

Пути из А:

1. А → Б → В → Ж → З
2. А → Б → В → Д → Е → Ж → З
3. А → Б → В → Д → Е → З
4. А → Б → Г → Д → Е → Ж → З
5. А → Б → Г → Д → Е → З
6. А → Б → Г → Ж → З
7. А → В → Ж → З
8. А → В → Д → Е → Ж → З
9. А → В → Д → Е → З
10. А → Г → Д → Е → Ж → З
11. А → Г → Д → Е → З
12. А → Г → Ж → З

Подсчитаем количество путей, используя метод графов:

• Из А можно попасть в Б (1 путь).
• Из А можно попасть в В (1 путь).
• Из А можно попасть в Г (1 путь).
• Из Б можно попасть в В (1 путь) и в Г (1 путь).
• Из В можно попасть в Д (1 путь) и в Ж (1 путь).
• Из Г можно попасть в Д (1 путь) и в Ж (1 путь).
• Из Д можно попасть в Е (1 путь).
• Из Е можно попасть в Ж (1 путь) и в З (1 путь).
• Из Ж можно попасть в З (1 путь).

Теперь посчитаем пути из А в З:

Пути через Б:

• А → Б → В → Ж → З (1)
• А → Б → В → Д → Е → Ж → З (1)
• А → Б → В → Д → Е → З (1)
• А → Б → Г → Д → Е → Ж → З (1)
• А → Б → Г → Д → Е → З (1)
• А → Б → Г → Ж → З (1)

Всего через Б: 6 путей.

Пути через В:

• А → В → Ж → З (1)
• А → В → Д → Е → Ж → З (1)
• А → В → Д → Е → З (1)

Всего через В: 3 пути.

Пути через Г:

• А → Г → Д → Е → Ж → З (1)
• А → Г → Д → Е → З (1)
• А → Г → Ж → З (1)

Всего через Г: 3 пути.

Общее количество путей из А в З = (пути через Б) + (пути через В) + (пути через Г) = 6 + 3 + 3 = 12.

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