Задание 23 на анализ графов: что учить к КЕГЭ 2027

Новое задание 23 — единственная тема КЕГЭ 2027 года, которой в экзамене раньше не было в таком виде. Ниже собрано, что о нём сказано в проекте и в разборах, без догадок о конкретных задачах демоверсии, и какая теория из школьного курса закрывает его целиком.

Что известно о задании 23 по проекту

О задании известны тема, общий тип задач и место в варианте; конкретные формулировки демоверсии на этой странице не пересказываются, а почему проекту пока нельзя доверять полностью, объяснено в материале о статусе демоверсий. В документе ФИПИ «Планируемые изменения в КИМ ЕГЭ 2027 года» тематика сформулирована как «умение решать алгоритмические задачи, связанные с анализом графов»^[4]. Остальное взято из пересказов проекта, и статус у сведений разный.

На позиции 23 в 2026 году стоял анализ хода алгоритма, теперь он переехал в задание 13, а маска подсети — в 10-е. Как сдвинулись номера, показано на странице про задания 10 и 13 и в общем обзоре ЕГЭ по информатике 2027.

Анализ графов против задания 1: в чём разница

Графы в экзамене встречались и раньше, но в задании 1 их нужно было прочитать, а не обработать алгоритмом. По таблице разбора спецификации задание 1 проверяет представление и считывание данных в информационных моделях: схемах, таблицах, графах.

В задании 1 граф обычно сопоставляют с таблицей и ищут, какая вершина какой букве соответствует. Это базовый уровень и несколько минут работы. В задании 23 граф становится входными данными для алгоритма: надо выбрать метод, пройти по вершинам в правильном порядке и получить число.

Отсюда практический вывод. Если задание 1 у вас получается стабильно, это хорошая база, но не подготовка к 23-му. Навык «увидеть граф» есть, навыка «посчитать по графу» пока нет.

Как представить граф перед решением

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

• матрица смежности — таблица N×N, где в ячейке стоит вес ребра или признак его наличия; удобна для небольших графов и для заданий, где граф уже дан таблицей;
• списки смежности — для каждой вершины перечень вершин, в которые из неё ведут рёбра; удобны для обходов и динамики;
• список рёбер — пары или тройки «откуда, куда, вес»; удобен, когда рёбра перечислены в условии подряд.

Тренируйтесь переводить один и тот же граф во все три формы, пока это не начнёт занимать меньше минуты. На экзамене время уходит не на алгоритм, а на то, чтобы аккуратно перенести рёбра и ни одного не потерять. Для ориентированного графа следите за направлением: ребро А→Б не означает ребро Б→А.

Отдельно проверьте, что в условии называется весом. Это может быть длина дороги, стоимость перехода или время, и от этого зависит, ищете вы минимум или максимум. Если вес у ребра не указан, считайте его равным единице, но только при условии, что задача не говорит иного.

Оптимальный путь: какие алгоритмы повторить

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

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

Число путей в ациклическом графе

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

Учебный пример, не из демоверсии. Рёбра: А→Б, А→В, Б→В, Б→Г, В→Г, В→Д, Г→Е, Д→Е. Считаем от А:

1. А = 1.
2. Б = А = 1.
3. В = А + Б = 2.
4. Г = Б + В = 3.
5. Д = В = 2.
6. Е = Г + Д = 5.

Путей из А в Е пять. Если вы раньше решали задачи на подсчёт количества программ для исполнителя, вы уже пользовались той же идеей: каждое число — вершина, каждая команда — ребро.

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

Как тренировать анализ графов до весны

Тренировка анализа графов растягивается на несколько месяцев, потому что тема новая и в сборниках 2026 года её почти нет. Практика извлечения, когда вы решаете без подсказки, а не перечитываете разбор, даёт лучшее отсроченное запоминание^[1], а повторение с интервалами надёжнее занятий подряд^[2].

Пишите код на том языке, которым уже владеете; если занимаетесь без репетитора, пригодятся советы по самостоятельной подготовке. Перечень языков на 2027 год известен только по одному изданию, поэтому полагаться на «особые» языки нельзя, пока не выйдет утверждённая спецификация. Подробнее о распределении тем по месяцам — в генераторе плана подготовки.

Когда углубляться в графы не нужно

Глубокая проработка графов окупается не у всех, и это стоит честно оценить. Вот ситуации, в которых хватит базового уровня.

• Ваша цель — порог для поступления, около 40–46 баллов: одно задание повышенного уровня можно пропустить без потери шансов, если остальная база закрыта.
• Вы до сих пор не решаете задания 1–9 без ошибок: эти девять баллов добрать проще, чем один за 23-е.
• Вы ещё не написали ни одной программы с циклом и массивом: начните с заданий 16–17, без этой базы задание 23 вам пока не подходит.
• До экзамена меньше месяца, а задания 24–25 не освоены: разумнее закрепить их, чем начинать новую тему.

Что повторить из программирования перед графами

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

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

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

Хорошая проверка готовности — написать с нуля, без подсказок, программу подсчёта путей для графа из учебного примера выше. Если получилось за десять минут и ответ совпал с ручным расчётом, база для задания 23 есть.

Чего не стоит делать при решении задания 23

Ошибки в этом задании обычно не в алгоритме, а в аккуратности. Проверяйте себя по списку.

• Нельзя путать направление рёбер в ориентированном графе.
• Нельзя применять динамику по порядку вершин из условия, если он не топологический: сначала постройте порядок.
• Не используйте алгоритм Дейкстры, если в графе есть отрицательные веса.
• Не считайте пути в графе с циклом той же формулой: она работает только для ациклического графа.
• Нельзя записывать в ответ промежуточное значение: проверьте, какую именно вершину спрашивают.
• Не тратьте на задание 23 больше двадцати минут на экзамене, если впереди не решены 24–27; балл за него такой же, как за любое из первых двадцати пяти.

Если хотите сравнить, как устроены другие изменения проекта, посмотрите разбор задания 27 с новым форматом ответа. Эффективные приёмы подготовки сведены в обзоре методов обучения^[3].

Источники

[1] Roediger H. L., Karpicke J. D. Test-Enhanced Learning: Taking Memory Tests Improves Long-Term Retention // Psychological Science. 2006. Vol. 17, № 3. P. 249–255.

[2] Cepeda N. J., Pashler H., Vul E., Wixted J. T., Rohrer D. Distributed Practice in Verbal Recall Tasks: A Review and Quantitative Synthesis // Psychological Bulletin. 2006. Vol. 132, № 3. P. 354–380.

[3] Dunlosky J., Rawson K. A., Marsh E. J., Nathan M. J., Willingham D. T. Improving Students' Learning With Effective Learning Techniques // Psychological Science in the Public Interest. 2013. Vol. 14, № 1. P. 4–58.

[4] ФИПИ. Проект демонстрационного варианта, спецификации и кодификатора КИМ ЕГЭ 2027 года по информатике. 2026.