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

Решение:

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

• Из города A:
  • В город B: 1 путь
  • В город E: 1 путь
  • В город G: 1 путь
• Из города B:
  • В город C: 1 путь (из A в B = 1, значит из B = 1)
  • В город E: 1 путь (из A в B = 1, значит из B = 1)
• Из города C:
  • В город D: 1 путь (из A в B -> C = 1, значит из C = 1)
  • В город E: 1 путь (из A в B -> C = 1, значит из C = 1)
• Из города G:
  • В город E: 1 путь (из A в G = 1, значит из G = 1)
• Из города E:
  • Из города A в E: 1 путь
  • Из города B в E: 1 путь
  • Из города C в E: 1 путь
  • Из города G в E: 1 путь
  • Всего путей в E: 1 (A->E) + 1 (A->B->E) + 1 (A->B->C->E) + 1 (A->G->E) = 4 пути
• Из города D:
  • В город F: 1 путь (из A -> B -> C -> D = 1, значит из D = 1)
• Из города F:
  • В город D: 1 путь (из A -> B -> C -> D -> F = 1, значит из F = 1)
• Подсчет путей в город D:
  • Пути через E: Из города E ведет 3 дороги в город D (E->D, E->F, E->G). Но так как дороги в D ведут только из E, F, G, мы должны посчитать пути до E, F, G, а затем до D.
  • Пути через E в D: 4 (пути до E) * 1 (E->D) = 4 пути.
  • Пути через F в D: 1 (A->B->C->D->F) * 1 (F->D) = 1 путь.
  • Пути через C в D: 1 (A->B->C) * 1 (C->D) = 1 путь.
  • Итого путей в город D: 4 (через E) + 1 (через F) + 1 (через C) = 6 путей.

Финальный подсчет:

• Пути из A в D:
• A → E → D: 1 путь
• A → B → E → D: 1 путь
• A → G → E → D: 1 путь
• A → B → C → E → D: 1 путь
• A → B → C → D: 1 путь
• A → B → C → D → F → D: 1 путь
• Всего: 1 + 1 + 1 + 1 + 1 + 1 = 6 путей.

Ответ: 6