Задание 9 ОГЭ по информатике: как считать пути в графе

Главный приём: складываем входящие пути

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

Обрабатывайте вершину только после всех её предшественников. Расположение на рисунке помогает, но порядок определяют именно стрелки.

Разбор на схеме

1. A: 1. Это старт.
2. B: 1. В B можно прийти только из A.
3. C: 1 + 1 = 2. В C приходим из A или из B.
4. D: 1 + 2 = 3. В D приходим из B или из C.

Ответ: 3 пути. Для проверки их можно выписать: A–B–D, A–C–D, A–B–C–D.

Если нужно пройти через заданную вершину

В графе выше найдём пути из A в D, проходящие через B.

1. Считаем пути до B: 1.
2. Считаем пути из B в D: 2 — напрямую и через C.
3. Соединяем первую часть со второй: 1 × 2 = 2 пути.

Это приём для ориентированного графа без циклов. Каждый путь до обязательной вершины соединяется с каждым путём после неё.

Если вершина запрещена: исключите её вместе с прилегающими стрелками. Без B остаётся A → C → D — один путь. Проверка: всего 3 пути; через B — 2; без B — 3 − 2 = 1.

Ошибки, которые легко предотвратить

• У старта пишите 1, а не 0: иначе все последующие суммы обнулятся.
• Считайте только входящие стрелки. Линия в обратном направлении не даёт нового пути.
• Пересечение линий без обозначенной вершины не является остановкой.
• В недостижимой вершине будет 0 путей. Не присваивайте единицу каждой вершине.

Удобная привычка: сначала отметить старт и финиш, затем подписывать маленькие числа прямо у вершин. Не смешивайте число путей с длиной самого короткого пути — это разные вопросы.

Более длинный граф: считаем по таблице

Пусть стрелки заданы так: A → B, C; B → D, E; C → D; D → E, F; E → F. Циклов нет. Составим таблицу по входящим стрелкам.

Ответ: 5 путей. Пять входящих в разные вершины стрелок сами по себе не означают пять маршрутов: считаются способы добраться до каждой вершины, а не количество линий.

Запрещённая вершина и проверка кодом

В том же графе запретим проход через D. У D будет 0 путей; из B в E остаётся прямой переход. Поэтому E = 1, F = 1: остаётся только A → B → E → F.

edges = {'A': ['B', 'C'], 'B': ['D', 'E'],
         'C': ['D'], 'D': ['E', 'F'],
         'E': ['F'], 'F': []}
ways = {v: 0 for v in edges}
ways['A'] = 1
blocked = 'D'
for v in ['A', 'B', 'C', 'D', 'E', 'F']:
    if v == blocked:
        continue
    for nxt in edges[v]:
        if nxt != blocked:
            ways[nxt] += ways[v]
print(ways['F'])  # 1

Код нужен для проверки собственного рассуждения. Вершины здесь уже перечислены в подходящем порядке: все стрелки ведут вперёд. Для другого графа алфавитный порядок может не подойти. Если убрать запрет, программа посчитает все 5 путей.

Когда складывать, а когда умножать?

Все правила в этом разборе относятся к графам без циклов. Авторские примеры помогают освоить приём; состав экзамена проверяйте по материалам ФИПИ нужного года.

Сохраните алгоритм решения

Открыть памятку «Пути в графе» для печати →

Схема, три правила и две задачи для самостоятельной проверки. Затем можно решить задания 9 ОГЭ или посмотреть как проходят занятия по ОГЭ с Никитой Саралашвили.

Перенесите способ на экзаменационный граф

Теперь попробуйте схему с семью вершинами из демоверсии. Сначала подпишите количество путей у начала, затем считайте вершины по направлению стрелок.

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

Решить задание 9 ОГЭ из демоверсии →

Если ответ не совпал, сравните промежуточные значения. Пересчитывать весь граф обычно не требуется.

Закрепите приём на новых задачах

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.