Задание № 9 по информатике: пути в графе

В задании № 9 нужно прочитать схему связей и получить числовой ответ. В проекте ОГЭ-2027 эта позиция проверяет графы: вершины и рёбра, направление переходов, длину пути, поиск оптимального пути и подсчёт путей в ориентированном ациклическом графе. За задание дают максимум 1 первичный балл.

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

Условие может дополнительно требовать пройти через заданную вершину, исключить вершину или ребро. В тренировочных задачах по тому же разделу встречаются весовые матрицы и поиск кратчайшего пути. Эти варианты нельзя смешивать: при подсчёте маршрутов складывают их количества, а при поиске кратчайшего пути сравнивают суммы весов.

• 1 балл: ответ записан в требуемой форме и полностью совпадает с эталоном.
• 0 баллов: ответ неверен, отсутствует или записан не в указанной форме.

Частичного балла за правильно заполненные промежуточные значения нет. В бланк нужно перенести только итоговое число.

1. Отметьте начало и конец пути, проверьте направления всех рёбер.
2. Присвойте начальной вершине значение 1: до неё существует один пустой путь.
3. Двигайтесь от начала по направлению стрелок. Для каждой следующей вершины сложите значения всех вершин, из которых в неё входят рёбра.
4. Не обрабатывайте вершину, пока не посчитаны все её предшественники.
5. Если есть обязательная или запрещённая вершина, примените ограничение до итогового сложения.
6. Значение конечной вершины и есть число путей.

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

Условие. Дан ориентированный граф с вершинами A, B, C, D, E, F, G, H. В нём есть только следующие рёбра:

A → B    A → C
B → D    B → E
C → D    C → F
D → E    D → G
E → H
F → G
G → H

Сколько существует различных направленных путей из A в H?

Решение. Обозначим через $N(X)$ число путей из A в вершину $X$.

1. $N(A)=1$.
2. В B и C ведёт по одному ребру из A, поэтому $N(B)=1$ и $N(C)=1$.

3. В D можно попасть из B или C:

   $$N(D)=N(B)+N(C)=1+1=2.$$
4. В F ведёт только ребро из C, поэтому $N(F)=1$.

5. В E ведут рёбра из B и D:

   $$N(E)=N(B)+N(D)=1+2=3.$$

6. В G ведут рёбра из D и F:

   $$N(G)=N(D)+N(F)=2+1=3.$$

7. Последняя вершина H имеет двух предшественников:

   $$N(H)=N(E)+N(G)=3+3=6.$$

Ответ: 6.

• Читать стрелку в обе стороны.
• Перечислять маршруты вручную и пропускать длинный путь.
• Приписывать каждой вершине число входящих рёбер вместо числа путей до неё.
• Обработать E раньше D и потерять пути, проходящие через D.
• Сложить веса рёбер, хотя требуется количество маршрутов.

Проверьте итог обратным перечислением последних шагов: каждый путь в H заканчивается ребром E → H или G → H, поэтому сумма $3+3$ охватывает все пути и не создаёт повторов.

Содержание позиции, формат краткого ответа и шкала сверены с проектами демоверсии, спецификации и кодификатора ОГЭ-2027 ФИПИ. В проекте 16 заданий, 150 минут работы и максимум 21 первичный балл. Шкала перевода баллов в отметку для 2027 года в комплекте не опубликована. Условие и решение примера созданы FastLearn.