Как решать задание 1 ЕГЭ по информатике 2026 — графы и таблицы соответствия
О чём задание
В задании 1 тебе дают граф (схему дорог, связей между городами) и таблицу смежности, в которой те же вершины пронумерованы по-другому. Нужно определить, какой номер в таблице соответствует какой вершине на графе.
Звучит просто, но подвох в том, что нумерация в таблице не совпадает с буквами на графе — именно это соответствие и нужно найти.
Три типа задач
1. Однозначное соотнесение графа и таблицы
Самый частый вариант. Дан неориентированный граф (все связи двусторонние) и таблица смежности. Каждая вершина имеет уникальную степень (количество рёбер), поэтому соответствие находится напрямую по степеням.
Иногда встречаются ориентированные графы — рёбра имеют направление (если из A есть дорога в B, это не значит, что из B есть дорога в A). В таблице это видно — она несимметрична относительно диагонали. Такие задачи попадаются редко, но знать про них стоит.
2. Неоднозначное соотнесение графа и таблицы
Граф неориентированный, но несколько вершин имеют одинаковую степень. Одних только степеней недостаточно — нужно анализировать соседей и их связи, чтобы различить вершины. Этот тип сложнее первого.
3. Взвешенный граф — соответствие и кратчайший путь
Каждое ребро имеет вес (длину в км). Вместо звёздочек в таблице стоят числа. Вопросы могут быть:
- «Какой номер соответствует вершине X?»
- «Найдите длину маршрута A → B → C»
- «Найдите сумму длин дорог DC + GF»
- «Найдите кратчайший путь из A в B»
Для задач на кратчайший путь удобно использовать алгоритм Дейкстры: выбираешь стартовую вершину, помечаешь расстояние до неё как 0, а до всех остальных — как бесконечность. Затем на каждом шаге берёшь ближайшую непосещённую вершину и обновляешь расстояния до её соседей. Повторяешь, пока не дойдёшь до нужной вершины.
Пошаговый алгоритм решения
Шаг 1: Посчитай степени вершин
Степень — это количество рёбер, выходящих из вершины.
- На графе посчитай, сколько связей у каждой вершины (A → 3, B → 2, C → 2, D → 1...)
- В таблице посчитай количество заполненных ячеек в каждой строке (строка 1 → 3, строка 2 → 2...)
- Совпали? Значит, вершина с уникальной степенью сразу определена
Пример: Если на графе только вершина A имеет 4 связи, а в таблице только строка 3 имеет 4 заполненные ячейки — значит, A = 3.
Шаг 2: Ищи уникальные признаки
Если степени совпадают у нескольких вершин, смотри глубже:
- Какие именно вершины связаны с данной?
- Связаны ли соседи между собой?
- Есть ли петли или тупики (вершины степени 1)?
Шаг 3: Анализ соседей (метод второго порядка)
Когда нашёл одну вершину — используй её как якорь:
- Вершина A = строка 3 (уже знаем)
- A связана с B, C, D на графе
- Строка 3 связана со строками 1, 5, 7 в таблице
- Значит, B, C, D — это строки 1, 5, 7 (осталось понять кто есть кто)
Шаг 4: Метод исключения
Каждая найденная вершина сужает варианты для оставшихся. После 2-3 определённых вершин остальные часто находятся автоматически.
Для взвешенных графов: дополнительные приёмы
Уникальные веса рёбер — мощные подсказки. Если только одно ребро имеет вес 53 — найди его и в графе, и в таблице. Это сразу определит две вершины.
Если в задаче нужно найти кратчайший путь — используй алгоритм Дейкстры (описан выше в разделе «Три типа задач»). Можно также построить дерево возможных путей и выбрать минимальный.
Типичные ошибки
Ошибка 1: Путаница с направлением. В асимметричном графе A → B ≠ B → A. Всегда проверяй, ориентированный ли граф.
Ошибка 2: Одинаковые степени = одинаковые вершины. Нет! Две вершины со степенью 3 могут быть связаны с совершенно разными наборами вершин.
Ошибка 3: Арифметика в маршрутах. При подсчёте длины маршрута A → B → C нужно сложить два отдельных ребра: AB + BC. Не забывай проверять сумму дважды.
Ошибка 4: Не проверять ответ. После того как определил соответствие — подставь обратно в таблицу и убедись, что все связи совпадают, а не только те, по которым ты решал.
Сколько времени тратить
- Уровень 1 (однозначное соотнесение, уникальные степени): 2-3 минуты
- Уровень 2 (неоднозначное соотнесение, одинаковые степени): 4-5 минут
- Уровень 3 (взвешенный граф, найти вершины или кратчайший путь): 5-7 минут
Если за 7 минут не получается — пропусти и вернись позже. Задание 1 стоит 1 первичный балл, не стоит тратить на него 15 минут.
Что поможет в подготовке
Лучший способ научиться — решать много задач разных типов. В TuteMe есть задания на все варианты: однозначное и неоднозначное соотнесение графа с таблицей, взвешенные графы и задачи на кратчайший путь. Тренажёр подбирает сложность под твой уровень и показывает подробный разбор после каждой ошибки.