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

Решение:

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

1. Город А:

• Из А можно попасть только в B и C.
• Количество путей из А в А = 1 (начальная точка).

2. Город B:

• Из А ведет 1 путь в B.
• Из B ведет 1 путь в G.
• Всего путей в B: 1.

3. Город C:

• Из А ведет 1 путь в C.
• Из C можно попасть в G.
• Всего путей в C: 1.

4. Город G:

• Из B ведет 1 путь в G.
• Из C ведет 1 путь в G.
• Всего путей в G: 1 + 1 = 2.

5. Город E:

• Из A ведет 1 путь в E.
• Из E можно попасть в F.
• Всего путей в E: 1.

6. Город F:

• Из E ведет 1 путь в F.
• Из F можно попасть в H.
• Всего путей в F: 1.

7. Город H:

• Из G ведет 2 пути в H.
• Из F ведет 1 путь в H.
• Всего путей в H: 2 + 1 = 3.

Важно: Мы не рассматривали пути, ведущие через D (например, A -> D, C -> D, D -> E, D -> G), так как по условию их нужно исключить.

Ответ: 3