МУМ5 → ОГЭ → Информатика → разборы → демоверсия 2027 → № 9

Задание 9 демоверсии ОГЭ 2027 по информатике

Количество путей в графе. Реши сам, потом открой решение.

Задание 9

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

Схема дорог со стрелками: A→B, A→D, B→C, B→D, B→E, C→E, C→G, D→E, D→F, E→F, F→G

Источник: ФИПИ, проект демоверсии ОГЭ 2027, с. 8

Решение и ответ

  1. Для каждого города считаем число путей из A: оно равно сумме чисел для городов, из которых в него ведут стрелки. Идём по порядку, чтобы входящие города были уже посчитаны.

  2. A = 1. B: только из A — 1. C: только из B — 1. D: из A и B — 1 + 1 = 2.

  3. E: из B, C, D — 1 + 1 + 2 = 4. F: из D и E — 2 + 4 = 6.

  4. G: из C и F — 1 + 6 = 7.

Ответ: 7