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

Решение:

Для решения задачи будем использовать метод подсчета количества путей, идущих из каждой вершины.

Начинаем с вершины А, так как из нее исходят пути.

• A: 1 путь (начало)
• C: Из A в C ведет 1 путь.
• D: Из A в D ведет 1 путь.
• B: Из A в B ведет 1 путь.
• E: Из B в E ведет 1 путь.
• F: Из E в F ведет 1 путь.
• G: Из D в G ведет 1 путь.
• H: Чтобы попасть в H, нужно пройти через F или G.
• Пути из F в H: Из A->B->E->F->H (1 путь).
• Пути из G в H: Из A->D->G->H (1 путь).
• Из A->C (1 путь) нет выхода в H.
• Из A->B->E->F (1 путь)
• Из A->D->G (1 путь)
• Количество путей в H = количество путей через F + количество путей через G.
• Пути через F: A->B->E->F->H = 1 путь
• Пути через G: A->D->G->H = 1 путь
• Общее количество путей в H = 1 + 1 = 2

Ответ: 2