Задание 9 ОГЭ 2027

Задание 9. Анализ информации, представленной в виде схем

Разберём задание 9 — «сколько существует путей из А в К». Считать пути перечислением — верный способ запутаться. Вместо этого подписываем числа у вершин — метод работает за минуту и не ошибается. Разберём все прототипы: обычный подсчёт, «через вершину» и «мимо вершины».

Краткая информация о задании 9

Дана схема дорог с односторонним движением (стрелки). Нужно посчитать количество различных путей из начального города в конечный, иногда — с условием «через город X» или «не проходя через X».

Балл за задание

Уровень сложности

Примерное время (по спецификации ФИПИ)

1 балл

повышенный

4 минуты

Прототипы задания. Все задачи этого номера сводятся к нескольким прототипам — ниже разобран каждый:

  • Прототип 1. Сколько путей из начальной вершины в конечную.

  • Прототип 2. Сколько путей, проходящих через заданную вершину.

  • Прототип 3. Сколько путей, НЕ проходящих через заданную вершину.

Что надо знать для решения

📌 Метод динамического подсчёта

У стартовой вершины пишем 1. Дальше для каждой вершины: её число = сумма чисел всех вершин, ИЗ которых в неё ведёт стрелка.

Обрабатываем вершины слева направо — считать вершину можно, только когда посчитаны все, кто в неё «втекает». Число у конечной вершины и есть ответ.

Разбор прототипа 1 — подсчёт путей

Условие

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

ОГЭ_задание_9_картинка_1.png

Подписываем у каждой вершины число путей из А

Считаем по стрелкам: А = 1; Б = А = 1; Г = А = 1; В = А + Б = 2; Д = Б + В = 3; Е = В + Г = 3; К = В + Д + Е = 2 + 3 + 3 = 8.

Ответ: 8.

Разбор прототипа 2 — пути через вершину

Условие

В том же графе: сколько путей из А в К проходит через город Д?

Путь через Д распадается на две независимые части: (А → Д) и (Д → К). Путей из А в Д — мы уже посчитали: 3. Путей из Д в К: из Д выходит одна стрелка Д→К, то есть 1. Перемножаем: 3 × 1 = 3.

Ответ: 3.

Разбор прототипа 3 — пути мимо вершины

Условие

В том же графе: сколько путей из А в К НЕ проходит через город Д?

Способ 1: все пути минус пути через Д: 8 − 3 = 5. Способ 2 (для проверки): зачеркнуть Д со всеми стрелками и пересчитать заново: К = В + Е = 2 + 3 = 5 ✓.

Ответ: 5.

Шпаргалка по заданию 9

Алгоритм

1) у старта пишем 1
2) вершина = сумма чисел вершин, ОТКУДА ведут стрелки в неё
3) идём слева направо, пока не дойдём до финиша
«через X»: (пути А -> X) * (пути X -> К)
«мимо X»:  все - через X   (или вычеркнуть X и пересчитать)

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

1. Складывают числа вершин, КУДА ведут стрелки, вместо вершин, ОТКУДА они приходят.

2. Считают вершину раньше, чем посчитаны все входящие в неё, — и теряют пути.

3. В «путях через X» складывают две части вместо умножения.

4. Невнимательно переносят стрелки со схемы: пропущенная стрелка — другой ответ.

💡 Последнее напутствие

Метод «подписи у вершин» — это первое настоящее динамическое программирование в твоей жизни. На ЕГЭ оно же решает задание 13, только граф там больше. Освоил здесь — освоил и там.

Удачи на экзамене — Профиматика ждёт тебя и на ЕГЭ!