На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город G?

Решение:

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

1. Город А: Из города А можно попасть только в B и D.
2. Город B: В B ведет 1 путь из А. Из B можно попасть в C и E.
3. Город D: В D ведет 1 путь из А. Из D можно попасть в C и F.
4. Город C: В C можно попасть из B (1 путь) и из D (1 путь). Итого: 1 + 1 = 2 пути в C. Из C можно попасть в F и G.
5. Город E: В E можно попасть из B (1 путь). Из E можно попасть в G.
6. Город F: В F можно попасть из D (1 путь) и из C (2 пути). Итого: 1 + 2 = 3 пути в F. Из F можно попасть в G.
7. Город G: В G можно попасть из C (2 пути), из E (1 путь) и из F (3 пути). Итого: 2 + 1 + 3 = 6 путей в G.

Ответ: 6