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

Задание 9 ОГЭ по информатике — задание повышенного уровня: по схеме односторонних дорог нужно найти, сколько существует различных путей из начального города в конечный. В кодификаторе ОГЭ 2026 года это элемент 2.11 — ориентированный граф, начальная вершина (источник) и конечная вершина (сток), вычисление количества путей в направленном ациклическом графе. Перебирать пути «вручную» здесь рискованно: при девяти городах и тринадцати дорогах путей бывает больше десяти, и один пропущенный путь стоит балла.

Материал учит надёжному способу — правилу сложения: число путей в город равно сумме чисел путей в города, из которых в него ведут дороги. Все графы в квизе заданы полным списком дорог вида «А→Б, А→В, …», поэтому задача читается целиком без рисунка. Кроме обычного подсчёта путей из А в К, в квизе есть задачи на путь через обязательный город (правило произведения), на пути, не проходящие через город (город вычёркивается вместе с дорогами), на число путей в промежуточный город и на ловушку, когда дорога ведёт «назад по алфавиту» и порядок подсчёта не совпадает с порядком букв. Два вопроса проверяют понимание метода: почему пути складываются и почему правило не работает при наличии цикла.

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

Материал рассчитан на 9 класс. Все графы составлены специально для этого материала и не повторяют задания открытого банка.

Как работать с материалом: решить квиз, записывая числа путей рядом с каждым городом на черновике, и после ошибки найти в пояснении первый город, где значение разошлось. Затем повторить карточки и выполнить письменную работу — её можно распечатать и сдать на проверку по фотографии. Для экзамена полезно всегда проверять, не ведёт ли какая-нибудь дорога «назад по алфавиту», и считать город только после всех его предшественников.

  • Считать число путей в ориентированном графе без циклов по правилу сложения
  • Определять правильный порядок подсчёта, когда он не совпадает с порядком букв
  • Решать задачи с условиями «через город» и «не через город»
  • Объяснять, почему правило неприменимо к графу с циклом

Кодификатор ОГЭ 2026 по информатике, элемент 2.11 (ориентированные графы; начальная вершина (источник) и конечная вершина (сток); вычисление количества путей в направленном ациклическом графе). Спецификация: задание 9, повышенный уровень, 1 балл.

Пример вопроса

Схема односторонних дорог между городами А, Б, В, Г, Д, Е, Ж, И, К; стрелки: А→Б, А→В, А→Г, Б→Д, В→Д, В→Е, Г→Е, Д→Ж, Е→Ж, Е→И, Ж→К, И→К.

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

Показать ответ

6

Считаем число путей в каждый город, двигаясь от А по направлению дорог: число путей в город равно сумме чисел путей в города, из которых в него ведут дороги. - А = 1 - Б = А = 1 - В = А = 1 - Г = А = 1 - Д = Б + В = 1 + 1 = 2 - Е = В + Г = 1 + 1 = 2 - Ж = Д + Е = 2 + 2 = 4 - И = Е = 2 - К = Ж + И = 4 + 2 = 6 Ответ: 6.

← Информатика

↑ ОГЭ