Разбор задания №9 ОГЭ по информатике: Количество путей в ориентированном графе

Задание №9 в ОГЭ по информатике проверяет умение анализировать информацию, представленную в виде ориентированных графов (схем дорог со стрелками), и находить общее количество различных путей между двумя населёнными пунктами.

За правильный ответ даётся 1 первичный балл. Задание решается за 1–2 минуты прямо на экзаменационном листе с помощью простого метода динамического программирования — последовательного сложения входящих путей.

1. Теоретический фундамент: что нужно знать

Вся задача строится на анализе ориентированного графа:

• Вершины — это населённые пункты (обозначаются буквами: А, Б, В, Г, Д и т.д.).
• Направленные рёбра (дуги со стрелками) — дороги с односторонним движением. Двигаться можно строго по направлению стрелки.
• Путь — непрерывная последовательность дорог, соединяющая начальный и конечный пункты, в которой ни одна вершина не повторяется.

Главное правило подсчёта путей:

Количество способов добраться до любого пункта V равно сумме способов добраться до всех пунктов, из которых стрелки ведут напрямую в пункт V:

Количество путей в V = Сумма путей во все входящие в V вершины

• Начальной вершине (старту) всегда присваивается значение 1 (в неё есть ровно один способ прийти — просто находиться на старте).

2. Универсальный пошаговый алгоритм решения

1. Стартовая точка: рядом с начальной вершиной (обычно это пункт А) поставьте число 1.
2. Порядок просчёта вершин:
   • Считайте число путей только для тех вершин, у которых уже посчитаны все входящие стрелки.
   • Если в вершину входит стрелка из пункта, значение которого ещё неизвестно — переходите к другой вершине.
3. Формула для каждой вершины: сложите числа во всех вершинах, откуда в неё идут стрелки.
4. Учёт дополнительных условий (если они есть):
   • «Проходящих через город N»: найдите пути из Старта в N, затем из N в Финиш и перемножьте их (либо вычеркните все дороги, которые минуют город N).
   • «НЕ проходящих через город N»: перед началом счёта зачеркните вершину N и все входящие и выходящие из неё стрелки.
5. Финиш: число, получившееся у конечной вершины, является ответом.

3. Разбор типовых примеров из банка ФИПИ и Решу ОГЭ

Пример 1. Базовый подсчёт всех путей из города А в город К

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Решение:
Нужно подсчитать количество путей от начальной точки А до конечной точки К.

Техника:
Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б "перетекает" 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку "перетекает" 1 из А.

В точку В входят две стрелки. Значит, в точку В "втекает" сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.

И продолжаем в том же духе.

Число в конечной точке показывает правильный ответ!

Ответ: 17

Пример 2. Подсчёт путей, проходящих через заданный город

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Ж?

Решение:

Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.

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

Ответ: 51

Пример 3. Подсчёт путей, НЕ проходящих через заданный город

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

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

Зачеркнём те дороги, которые поведут наши пути через пункт E.

Далее, применим старый метод, который использовали ранее.

Получается ответ 27.

Ответ: 27

4. Типичные ловушки и частые ошибки

1. Пропуск входящих стрелок:
   • Всегда внимательно проверяйте, сколько именно стрелок острием входит в данную вершину. Если в вершину входит 3 стрелки, а вы сложили только 2 — ответ собьётся для всех последующих пунктов.
2. Преждевременный подсчёт:
   • Нельзя считать значение вершины, пока не посчитаны все вершины, из которых к ней ведут стрелки.
3. Игнорирование стрелок между пунктами одного уровня:
   • Очень часто на схемах есть вертикальные стрелки (например, из Б в В или из Г в Д). Их легко случайно не заметить.
4. Условия «проходит через» / «не проходит через»:
   • Обязательно перечитайте условие в конце. Если требовалось найти пути через конкретный город, а вы посчитали все дороги графа, ответ будет неверным.

Памятка для ученика

┌─────────────────────────────────────────────────────────────┐
│              ЧЕК-ЛИСТ ДЛЯ ЗАДАНИЯ №9 ОГЭ                    │
├─────────────────────────────────────────────────────────────┤
│ 1. Поставить начальной вершине А значение 1.                │
│ 2. Если есть условие «НЕ через город N» — сразу вычеркнуть  │
│    вершину N и все прилегающие стрелки.                     │
│ 3. Считать вершины последовательно: V = сумма всех входов.  │
│ 4. Не считать вершину, пока не найдены все входящие узлы.   │
│ 5. Для условия «через город N»: перемножить пути (А→N)·(N→K)│
│ 6. Итоговое число у финишной вершины записать в ответ.      │
└─────────────────────────────────────────────────────────────┘