Как решать задание 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, A—E, B—C, C—D, D—F.
Таблица смежности (звёздочки там, где есть ребро):
| П1 | П2 | П3 | П4 | П5 | П6 | |
|---|---|---|---|---|---|---|
| П1 | * | * | * | |||
| П2 | * | |||||
| П3 | * | * | * | |||
| П4 | * | * | * | * | ||
| П5 | * | |||||
| П6 | * | * |
Шаг 1 — степени. На графе: A=4, B=2, C=3, D=3, E=1, F=1. В таблице: П1=3, П2=1, П3=3, П4=4, П5=1, П6=2.
Две вершины определяются сразу, потому что их степени уникальны: A — единственная со степенью 4, значит A=П4; B — единственная со степенью 2, значит B=П6.
Шаг 2 — пара C и D (обе степени 3). Одних степеней мало, смотрим на соседей. У C соседи A, B, D — их степени 4, 2, 3. У D соседи A, C, F — степени 4, 3, 1. Разница видна: у C есть сосед степени 2, а у D — сосед степени 1. Теперь в таблице: у П1 соседи П3, П4, П6 со степенями 3, 4, 2 — есть сосед степени 2, значит C=П1. У П3 соседи П1, П2, П4 со степенями 3, 1, 4 — есть сосед степени 1, значит D=П3.
Шаг 3 — пара E и F (обе степени 1). У каждой ровно один сосед, и соседи разные: E висит на A (степень 4), F — на D (степень 3). В таблице П5 связана только с П4 (степень 4) — значит E=П5, а П2 связана только с П3 — значит F=П2.
Шаг 4 — проверка. Пройдись по всем семи рёбрам графа и убедись, что каждое есть в таблице: A—B → П4—П6 ✓, A—C → П4—П1 ✓, и так далее. Все семь сошлись — соответствие найдено верно.
Главная мысль: ты чередуешь подсчёт степеней и анализ соседей, пока у каждой вершины не наберётся уникальный набор признаков. Найденные вершины работают якорями для остальных.
Для взвешенных графов: дополнительные приёмы
Уникальные веса рёбер — мощные подсказки. Если только одно ребро имеет вес 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 есть задания на все варианты: однозначное и неоднозначное соотнесение графа с таблицей, взвешенные графы и задачи на кратчайший путь. Тренажёр подбирает сложность под твой уровень и показывает подробный разбор после каждой ошибки.