Как решать задание 1 ЕГЭ по информатике 2026 — графы и таблицы соответствия
Разбор задания 1 ЕГЭ по информатике: графы, таблицы смежности, алгоритм Дейкстры, методы решения и типичные ошибки. Пошаговый алгоритм для всех типов задач.
О чём задание
В задании 1 тебе дают граф (схему дорог, связей между городами) и таблицу смежности, в которой те же вершины пронумерованы по-другому. Нужно определить, какой номер в таблице соответствует какой вершине на графе.
Звучит просто, но подвох в том, что нумерация в таблице не совпадает с буквами на графе — именно это соответствие и нужно найти.
Зачем это вообще нужно? Графы — универсальный язык для описания связей: сеть дорог, схема метро, соцсети, зависимости между задачами. Таблица смежности — компактный способ хранить граф в памяти компьютера. Навигатор в телефоне работает с такой таблицей: ищет маршрут — решает усложнённую версию задания 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 определённых вершин остальные часто находятся автоматически.
Полный разбор: пример с 6 вершинами
Чтобы алгоритм не оставался на словах, разберём типовую задачу. Пусть есть неориентированный граф с вершинами A, B, C, D, E, F и такими связями: A—B, A—C, A—D, B—C, B—E, C—F, D—F, E—F.
Таблица смежности (звёздочки там, где есть ребро):
| П1 | П2 | П3 | П4 | П5 | П6 | |
|---|---|---|---|---|---|---|
| П1 | * | * | ||||
| П2 | * | * | * | * | ||
| П3 | * | * | ||||
| П4 | * | * | * | |||
| П5 | * | * | ||||
| П6 | * | * | * |
Степени на графе: A=3, B=3, C=3, D=2, E=2, F=3. Степени в таблице: П1=2, П2=3, П3=2, П4=3, П5=2, П6=3.
Уникальных степеней нет — две группы: степень 2 (D, E и кто-то третий — значит либо мы ошиблись при чтении графа, либо задача даёт три вершины степени 2). Допустим, пересчитав, получили одинаковое распределение.
Переходим к анализу соседей. У D соседи A и F — обе степени 3. У E соседи B и F — тоже обе степени 3. Одних соседских степеней мало.
Копаем глубже: связаны ли соседи между собой? У D соседи A и F — ребра A—F на графе нет. У C соседи A, B, F — ребро A—B есть, значит соседи C связаны. Это сразу отличает C от остальных вершин степени 3.
Главная мысль: ты чередуешь подсчёт степеней, анализ соседей и связей между соседями, пока не получишь уникальный набор признаков для каждой вершины.
Для взвешенных графов: дополнительные приёмы
Уникальные веса рёбер — мощные подсказки. Если только одно ребро имеет вес 53 — найди его и в графе, и в таблице. Это сразу определит две вершины.
Если в задаче нужно найти кратчайший путь — используй алгоритм Дейкстры (описан выше в разделе «Три типа задач»). Можно также построить дерево возможных путей и выбрать минимальный.
Алгоритм Дейкстры по шагам
Разберём Дейкстру на графе с 5 вершинами A, B, C, D, E и рёбрами: A—B=4, A—C=2, B—C=1, B—D=5, C—D=8, C—E=10, D—E=2. Ищем кратчайший путь из A в E.
Ведём таблицу текущих расстояний. Стартовое состояние: A=0, остальные = ∞.
| Шаг | Обрабатываем | A | B | C | D | E |
|---|---|---|---|---|---|---|
| 0 | — | 0 | ∞ | ∞ | ∞ | ∞ |
| 1 | A (0) | 0 | 4 | 2 | ∞ | ∞ |
| 2 | C (2) | 0 | 3 | 2 | 10 | 12 |
| 3 | B (3) | 0 | 3 | 2 | 8 | 12 |
| 4 | D (8) | 0 | 3 | 2 | 8 | 10 |
| 5 | E (10) | 0 | 3 | 2 | 8 | 10 |
На каждом шаге берём ближайшую непосещённую вершину и обновляем расстояния до её соседей, если новый путь короче. На шаге 2 через C получилось дойти до B за 2+1=3 (короче, чем исходные 4) — обновляем. Ответ: кратчайший путь из A в E равен 10 (маршрут A → C → B → D → E).
Главное правило: никогда не возвращаемся к уже посещённой вершине. Для экзамена достаточно вести такую маленькую таблицу и вычёркивать обработанные вершины.
Нет такого алгоритма — что делать
Иногда попадается задача, где стандартный подход «по степеням» не срабатывает: у всех вершин одинаковая степень, соседи тоже имеют совпадающие степени, и таблица выглядит почти симметрично. Что делать?
- Считай пути длины 2 и 3. Из каждой вершины можно посчитать, в сколько других вершин ведут пути ровно за 2 шага. Часто этот показатель уникален.
- Ищи треугольники. Три вершины, попарно соединённые между собой — это мощный структурный признак. Если в графе только один треугольник, его участники определяются автоматически.
- Считай «соседей соседей». Сумма степеней всех соседей вершины — число, которое часто отличается даже при одинаковых степенях.
- Пробуй гипотезу и проверяй. Если у тебя 2 кандидата на вершину — подставь сначала один вариант и проверь согласованность по всем рёбрам. Не сошлось — значит второй.
Эти приёмы особенно полезны в сложных вариантах. Если ты прошёл типичные ошибки на ЕГЭ по информатике, ты уже знаешь: проверка ответа — это не формальность, а часть решения.
Типичные ошибки
Ошибка 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 минут. Общий тайминг КЕГЭ — 235 минут на 27 заданий, запас понадобится на трудоёмкие задания 25 и 27. Про распределение времени — в статье как набрать 90+ баллов.
Как тренироваться: план на 3 недели
Неделя 1 — базовый навык. По 3-4 задачи в день на однозначное соотнесение. Цель — быстро и без ошибок считать степени. К концу недели задача решается за 2 минуты.
Неделя 2 — неоднозначные случаи. Задачи с одинаковыми степенями у нескольких вершин. Отрабатывай анализ соседей и связей между ними. По 2-3 задачи в день с подробным разбором.
Неделя 3 — взвешенные графы и кратчайшие пути. Сумма длин по маршруту, поиск кратчайшего пути, 5-6 задач на Дейкстру. К концу третьей недели задание 1 уходит стабильно за 3-4 минуты даже в сложных вариантах.
Что поможет в подготовке
Лучший способ научиться — решать много задач разных типов. В TuteMe есть задания на все варианты: однозначное и неоднозначное соотнесение графа с таблицей, взвешенные графы и задачи на кратчайший путь. Тренажёр подбирает сложность под твой уровень и показывает подробный разбор после каждой ошибки.