Задание 9 ОГЭ 2027
Задание 9. Анализ информации, представленной в виде схем
Разберём задание 9 — «сколько существует путей из А в К». Считать пути перечислением — верный способ запутаться. Вместо этого подписываем числа у вершин — метод работает за минуту и не ошибается. Разберём все прототипы: обычный подсчёт, «через вершину» и «мимо вершины».
Краткая информация о задании 9
Дана схема дорог с односторонним движением (стрелки). Нужно посчитать количество различных путей из начального города в конечный, иногда — с условием «через город X» или «не проходя через X».
Балл за задание | Уровень сложности | Примерное время (по спецификации ФИПИ) |
|---|---|---|
1 балл | повышенный | 4 минуты |
Прототипы задания. Все задачи этого номера сводятся к нескольким прототипам — ниже разобран каждый:
Прототип 1. Сколько путей из начальной вершины в конечную.
Прототип 2. Сколько путей, проходящих через заданную вершину.
Прототип 3. Сколько путей, НЕ проходящих через заданную вершину.
Что надо знать для решения
📌 Метод динамического подсчёта У стартовой вершины пишем 1. Дальше для каждой вершины: её число = сумма чисел всех вершин, ИЗ которых в неё ведёт стрелка. Обрабатываем вершины слева направо — считать вершину можно, только когда посчитаны все, кто в неё «втекает». Число у конечной вершины и есть ответ. |
Разбор прототипа 1 — подсчёт путей
Условие Города А, Б, В, Г, Д, Е, К соединены дорогами с односторонним движением: А→Б, А→В, А→Г, Б→В, Б→Д, В→Д, В→Е, В→К, Г→Е, Д→К, Е→К. Сколько существует путей из А в К? |
Подписываем у каждой вершины число путей из А
Считаем по стрелкам: А = 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, только граф там больше. Освоил здесь — освоил и там. Удачи на экзамене — Профиматика ждёт тебя и на ЕГЭ! |