Перейти к содержимому

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

Задание 9до 1 баллачисло путей в графе
Раздел
Теоретические основы информатики · часть 1
Максимальный балл
1 балл
Уровень
повышенный
Что проверяет
Умение анализировать информацию, представленную в виде схем
Что нужно сделать
Посчитать число различных путей из одного города в другой по схеме дорог, в том числе через город или в обход города.
Как записать ответ
только число: целое, без единиц измерения и основания системы счисления
Время
Около 4 минут по обобщённому плану ФИПИ
Элемент кодификатора
2.11
Где решается
На бланке, без компьютера: ответ — в бланк № 1
Справляются
74,0 % участников по отчётам Кировской и Иркутской областей и Татарстана за 2025 год
Решать варианты ОГЭ целиком →Практика на этой странице ↓

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

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

Тренажёр задания 9

Десять заданий номера 9 из банка тренажёра. Ответ проверяется по ключу без регистрации: после проверки — верный ответ и разбор, а при ошибке — разбор от ИИ. Кнопка «Ещё 5 таких» у типа задания ниже даёт задания одного типа.

Загружаем задание…

Задание 9 вместе с остальными — в вариантах целиком.

Типы задания 9 с решением

Число путей из одного города в другой

Пример условия

Схема дорог между городами А, Б, В, Г, Д, Е, Ж, З задана списком; по каждой дороге можно ехать только в указанную сторону:

А→Б  А→В  А→Г  Б→В  Б→Д  В→Д  В→Е
Г→Е  Д→Е  Д→Ж  Е→Ж  Е→З  Ж→З

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

Ответ — 15.

1. А — 1. 2. Для каждого следующего города складываем числа городов, откуда в него идут стрелки. 3. Число у конечного города — ответ.

На примере: Б = А = 1; В = А + Б = 2; Г = А = 1; Д = Б + В = 3; Е = В + Г + Д = 6; Ж = Д + Е = 9; З = Е + Ж = 15. Это тип задания из демоверсии 2027 года.

Решение на Python
roads = ['АБ', 'АВ', 'АГ', 'БВ', 'БД', 'ВД', 'ВЕ', 'ГЕ', 'ДЕ', 'ДЖ', 'ЕЖ', 'ЕЗ', 'ЖЗ']
order = 'АБВГДЕЖЗ'  # каждая дорога ведёт из более раннего города в более поздний

ways = {city: 0 for city in order}
ways['А'] = 1  # в начальный город — один путь
for city in order[1:]:
    # складываем числа городов, из которых в city ведёт стрелка
    ways[city] = sum(ways[r[0]] for r in roads if r[1] == city)
    print(city, ways[city])

print(ways['З'])

Ответ: 15

Пути через заданный город

Пример условия

Дороги между городами А, Б, В, Г, Д, Е, Ж, И (только в указанную сторону):

А→Б  А→В  Б→В  Б→Г  В→Г  В→Д
Г→Е  Д→Е  Д→Ж  Е→Ж  Е→И  Ж→И

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

Ответ — 10.

1. Считаем пути из А в Е обычным способом. 2. Считаем пути из Е в И: теперь начальный город — Е, у него 1. 3. Перемножаем: каждый путь до Е можно продолжить любым путём после Е.

На примере: до Е — Б = 1, В = 2, Г = 3, Д = 2, Е = 3 + 2 = 5. После Е — Ж = 1 (только из Е), И = Е + Ж = 2. Ответ: 5 · 2 = 10. Без условия путей было бы 12: два из них идут через Д→Ж и Е минуют.

Решение на Python
roads = ['АБ', 'АВ', 'БВ', 'БГ', 'ВГ', 'ВД', 'ГЕ', 'ДЕ', 'ДЖ', 'ЕЖ', 'ЕИ', 'ЖИ']
order = 'АБВГДЕЖИ'


def count(start, end):
    # число путей из start в end: подписываем города по порядку
    ways = {city: 0 for city in order}
    ways[start] = 1
    for city in order[order.index(start) + 1:]:
        ways[city] = sum(ways[r[0]] for r in roads if r[1] == city)
    return ways[end]


before = count('А', 'Е')  # пути до города Е
after = count('Е', 'И')   # пути от Е до конца
print(before, after)
print(before * after)

Ответ: 10

Пути в обход заданного города

Пример условия

Дороги между городами А, Б, В, Г, Д, Е, Ж, К (только в указанную сторону):

А→Б  А→В  А→Г  Б→Д  В→Г  В→Д
Г→Е  Д→Е  Д→Ж  Е→Ж  Е→К  Ж→К

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

Ответ — 4.

1. Ставим у запрещённого города 0 — все его дороги как будто убраны. 2. Остальные города подписываем как обычно.

На примере: Б = 1, В = 1, Г = А + В = 2, Д = 0, Е = Г + Д = 2, Ж = Д + Е = 2, К = Е + Ж = 4. Проверка: всего путей из А в К 10, а через Д — (Б + В) · 3 = 2 · 3 = 6; 10 − 6 = 4.

Решение на Python
roads = ['АБ', 'АВ', 'АГ', 'БД', 'ВГ', 'ВД', 'ГЕ', 'ДЕ', 'ДЖ', 'ЕЖ', 'ЕК', 'ЖК']
order = 'АБВГДЕЖК'
banned = 'Д'  # этот город обходим

ways = {city: 0 for city in order}
ways['А'] = 1
for city in order[1:]:
    if city == banned:
        continue  # у запрещённого города остаётся 0
    ways[city] = sum(ways[r[0]] for r in roads if r[1] == city)

print(ways['К'])

Ответ: 4

Как выполнять задание

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

Что нужно знать

  • Ориентированный граф — города (вершины) и дороги-стрелки (рёбра) с направлением. Против стрелки ехать нельзя.
  • Главное правило: число путей в город равно сумме чисел путей в те города, из которых в него ведут стрелки.
  • Через город: пути до него умножают на пути после него. В обход города: у него ставят 0.
  • Порядок подсчёта важен: число города можно писать, только когда подписаны все города, откуда в него есть стрелки.

Как оценивается

Проверка по ключу: 1 балл, если ответ записан в той форме, которая указана в инструкции, и полностью совпал с эталоном. Частичного балла нет, черновик не проверяют.

Критерии всех заданий экзамена — на странице критериев ОГЭ.

Разбор задания демоверсии 2027

В демоверсии 2027 года схема связывает города 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.

Подписываем города по порядку. A — 1. В B ведёт только стрелка из A: B — 1. В C — только из B: C — 1. В D ведут дороги из A и B: D = 1 + 1 = 2. В E — из B, C и D: E = 1 + 1 + 2 = 4. В F — из D и E: F = 2 + 4 = 6. В G — из C и F: G = 1 + 6 = 7. Это совпадает с ключом ФИПИ; прямой перебор всех маршрутов (мы сделали его программой) тоже даёт 7.

Где здесь ошибаются: у E три входящие стрелки, и стрелку из C, идущую сверху почти вертикально, легко не заметить — тогда выйдет E = 3 и ответ 6. Вторая ловушка — дорога C→G: кто считает только пути через F, получает 6. Решите демоверсию целиком в разделе вариант ОГЭ 2027 по информатике.

Типичные ошибки

Пропустили входящую стрелку

У города три-четыре входящие дороги, а сложили две. Легко потерять длинную стрелку, идущую через всю схему. Перед сложением пересчитайте наконечники стрелок у города и отметьте каждую, которую учли.

Подписали город раньше времени

Число города пишут только тогда, когда известны числа всех городов, откуда в него идут стрелки. Если в Е ведёт дорога из Д, а Д ещё не посчитан, сумма у Е выйдет меньше и ошибка уйдёт в ответ.

Сложили числа исходящих дорог

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

Сложили вместо умножения

Для условия «через город X» пути до X и после X перемножают: каждый путь до X продолжается любым путём после него. Сумма 5 + 2 вместо 5 · 2 даёт неверный ответ.

Обошли город, но не до конца

Если город запрещён, его нельзя оставлять с обычным числом и просто не писать в итоговую сумму: его 0 должен войти во все города после него. Иначе пути через него вернутся в ответ на следующем шаге.

Вопросы и ответы

Как решать 9 задание ОГЭ по информатике?

Поставьте 1 у начального города и идите по схеме: у каждого города пишите сумму чисел тех городов, из которых в него ведут стрелки. Число у конечного города — ответ. Для условий «через город» и «в обход города» есть два приёма — умножение и ноль: путей через город столько, сколько путей до него, умноженных на пути от него; город, который надо обойти, получает 0.

Можно ли просто перебрать все пути?

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

Какие бывают типы задания 9?

Три: найти все пути между двумя городами, пути через заданный город и пути в обход заданного города. В демоверсиях 2026 и 2027 годов был первый тип.

Нужен ли компьютер или программа для задания 9?

Нет. Задание 9 входит в первую часть, его решают на черновике и записывают число в бланк ответов. Перебор на Python пригодится только дома, для самопроверки при подготовке.

Что делать, если стрелки идут в разные стороны по схеме?

Направление на рисунке (влево или вправо) значения не имеет — важен наконечник стрелки. Подписывайте города не слева направо, а в таком порядке, чтобы все города-источники каждой стрелки были уже посчитаны.

Другие задания раздела «Теоретические основы информатики»

По демоверсии, спецификации и кодификатору ФИПИ 2027
Обновлено:

Все задания ОГЭ по информатике →