ЕГЭ по информатике 2027: новое задание на графы
В проекте ЕГЭ по информатике 2027 года на месте 23 стоит новое задание: дан ориентированный граф без циклов, нужно найти кратчайший путь между двумя вершинами или посчитать, сколько всего разных путей между ними. Звучит страшно, но обе задачи решаются одним приёмом. Разбираем его на примерах.
По проекту демоверсии ФИПИ на 2027 год. Примеры составлены нами в формате нового задания.
Что такое граф без циклов
Граф это точки (вершины) и стрелки между ними (рёбра). Ориентированный значит, что по стрелке можно идти только в одну сторону. Без циклов значит, что, выйдя из вершины, в неё уже не вернуться.
Из-за этого вершины можно выстроить в ряд так, что все стрелки смотрят вперёд. Это и есть ключ к заданию: если идти по вершинам слева направо, к моменту, когда мы дошли до вершины, всё, что в неё ведёт, уже посчитано.
Считаем число путей
Правило одно: число путей в вершину равно сумме чисел путей во все вершины, из которых в неё ведут стрелки. В стартовую вершину ставим 1.
Задача
Стрелки графа: А→Б, А→В, Б→Г, В→Г, Б→Д, Г→Д, Г→Е, Д→Е, Д→Ж, Е→Ж. Сколько существует разных путей из А в Ж?
А: 1 (стартовая вершина).
Б: ведёт только А, значит, 1. В: тоже только А, 1.
Г: ведут Б и В, 1 + 1 = 2.
Д: ведут Б и Г, 1 + 2 = 3.
Е: ведут Г и Д, 2 + 3 = 5.
Ж: ведут Д и Е, 3 + 5 = 8.
Ответ: 8 путей.
Заметили 1, 1, 2, 3, 5, 8? Это числа Фибоначчи: граф специально так устроен, что каждая вершина складывает две предыдущие. На экзамене граф будет больше, и считать удобнее программой.
paths[v] = sum(paths[u] for u in parents[v])
Строка на Python: для каждой вершины в порядке обхода складываем ответы её «родителей». Так же решалась задача 23 прошлых лет про исполнителя с командами.
Ищем кратчайший путь
Здесь у стрелок есть длины. Идея та же, только вместо суммы берём минимум: длина кратчайшего пути до вершины равна наименьшему из чисел «путь до родителя плюс длина стрелки».
Задача
Длины стрелок: А→Б 3, А→В 1, В→Б 1, Б→Г 4, В→Г 6, Б→Д 7, Г→Д 2. Найдите длину кратчайшего пути из А в Д.
А: 0.
В: только из А, 0 + 1 = 1.
Б: из А (0 + 3 = 3) или из В (1 + 1 = 2). Минимум 2.
Г: из Б (2 + 4 = 6) или из В (1 + 6 = 7). Минимум 6.
Д: из Б (2 + 7 = 9) или из Г (6 + 2 = 8). Минимум 8.
Ответ: 8, путь А → В → Б → Г → Д.
Обратите внимание: прямая стрелка А→Б длиной 3 проигрывает обходу через В длиной 2. Именно на таких местах теряют баллы, когда ищут путь на глаз.
Как готовиться
- Научиться выстраивать вершины так, чтобы стрелки смотрели вперёд (топологическая сортировка).
- Решить вручную десяток маленьких графов на число путей и кратчайший путь.
- Написать обе программы на своём языке и держать их как заготовку.
- Повторить задачи про исполнителей: идея подсчёта путей там та же.
Разберём на занятии
Готовим к ОГЭ и ЕГЭ на живых занятиях в мини-группе до шести человек или один на один, с пробниками в формате экзамена и разбором каждой ошибки.
Первое занятие бесплатное: можно посмотреть формат вместе с ребёнком и решить, подходит ли он.
Частые вопросы
Нужно ли знать алгоритм Дейкстры?
Для графа без циклов не обязательно: хватает обхода по порядку, который мы показали. Дейкстра пригодится, если граф с циклами, но в проекте задания речь именно о графе без них.
Куда делось старое задание 23?
Анализ работы алгоритма с командами исполнителя переехал на место 13 без изменений.