Задание 1 ЕГЭ: соответствие графа и таблицы дорог

Что проверяет задание

Задание 1 проверяет умение работать с двумя способами представления одной и той же информационной модели — графом (схема дорог) и таблицей (матрица смежности). Нужно понять, что вершины графа и строки/столбцы таблицы описывают один и тот же объект, но пронумерованы независимо, и восстановить это соответствие. Ключевая идея — использовать инварианты: характеристики, которые не меняются при переименовании вершин (степень вершины, степени её соседей, наличие особых структур). Отдельная сложность — отличать ситуации, когда соответствие определяется однозначно, от ситуаций, когда возможно несколько вариантов, но конкретные вершины из вопроса всё равно определяются точно.

Как выглядит формулировка и сколько баллов

Типичная формулировка: «На рисунке схема дорог изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами... Так как таблицу и схему рисовали независимо друг от друга, нумерация в таблице не связана с обозначениями на графе. Определите номера населённых пунктов A и G (или Б и В)». Ответ — одна или несколько цифр, записанных в порядке возрастания без пробелов и разделителей. Задание относится к части 1, оценивается в 1 балл, проверяется строго автоматически: любое отклонение в порядке или формате ответа засчитывается как ошибка.

Что нужно знать

• Граф — набор вершин и рёбер между ними; в этих задачах вершины — населённые пункты, рёбра — дороги.
• Степень вершины $\deg(v)$ — количество рёбер, выходящих из вершины (сколько дорог ведёт из пункта).
• Таблица (матрица) смежности — симметричная таблица, где на пересечении строки $i$ и столбца $j$ звёздочка означает наличие ребра между $i$ и $j$; диагональ всегда пустая (петель нет).
• Степень пункта в таблице равна числу звёздочек в его строке, и оно же равно числу звёздочек в его столбце: $\deg(i) = \sum_j a_{ij} = \sum_j a_{ji}$.
• Лемма о рукопожатиях: сумма степеней всех вершин равна удвоенному числу рёбер: $\sum_{i} \deg(v_i) = 2|E|$. Это удобно для проверки — сумма звёздочек по всем строкам всегда чётная.
• Изоморфизм графов — взаимно однозначное соответствие вершин двух графов, при котором смежность сохраняется: если вершины связаны в одном графе, их образы связаны и в другом.
• Инвариант — свойство, сохраняющееся при изоморфизме: степень вершины, число вершин с данной степенью, наличие треугольника (три вершины, попарно связанные рёбрами), расстояние между вершинами.
• Если степени двух вершин одинаковы, для их различения используют инвариант второго порядка — набор степеней их соседей.
• Если после всех проверок остаётся несколько допустимых перестановок вершин — соответствие неоднозначное; но конкретная пара вершин из вопроса может при этом совпадать во всех допустимых вариантах, тогда её всё равно можно указать в ответе.

Методы решения

1. Метод подсчёта степеней. Считаем степень каждой вершины по рисунку (сколько линий выходит) и степень каждого пункта по таблице (сколько звёздочек в строке). Сопоставляем совпадающие числа. Мини-пример: в графе из 4 вершин A, B, C, D дана A–B, A–C, A–D. Тогда $\deg(A)=3$, остальные $\deg=1$. В таблице только у пункта 2 сумма звёздочек равна 3 — значит A соответствует пункту 2, независимо от прочих совпадений.

2. Метод анализа соседей при равных степенях. Если несколько вершин имеют одинаковую степень, сравниваем степени их соседей. Мини-пример: две вершины степени 2 — одна соединена с вершиной степени 4, другая с вершиной степени 3. В таблице у пунктов той же степени 2 звёздочки стоят в столбцах с разными степенями соседей — сопоставляем по совпадению этих чисел.

3. Метод последовательного определения («от простого к сложному»). Сначала фиксируем вершины с уникальной степенью, затем используем уже найденные вершины как «опорные точки» для определения оставшихся через связи с ними. Мини-пример: определили, что вершина степени 5 — это пункт 4. Теперь для оставшихся вершин смотрим, кто из них связан с пунктом 4 в таблице, и сверяем с рисунком.

4. Метод поиска особых подструктур. Если степени совпадают массово (несколько вершин с одной и той же степенью, соседи тоже одинаковы по степеням), ищем на графе и в таблице треугольники, цепочки нужной длины, изолированные вершины — это более тонкие инварианты, помогающие различить внешне одинаковые вершины. Мини-пример: среди четырёх вершин степени 3 только две образуют треугольник с уникальной третьей вершиной — эта пара однозначно определяется по таблице, даже если весь граф в целом допускает несколько изоморфизмов.

5. Метод проверки подстановкой. После построения предполагаемого соответствия подставляем номера во все рёбра графа и проверяем, что в таблице на всех этих местах действительно стоят звёздочки, а на остальных — нет. Это финальная самопроверка, обязательная при неоднозначных случаях.

Алгоритм решения по шагам

1. По рисунку выписать степень каждой вершины графа (посчитать число линий у каждой точки).
2. По таблице посчитать степень каждого пункта — сумма звёздочек в строке.
3. Сравнить полученные наборы чисел: они должны совпадать (это самопроверка правильности подсчёта).
4. Найти вершины и пункты с уникальной (неповторяющейся) степенью — сопоставить их сразу.
5. Для вершин с повторяющейся степенью сравнить степени их соседей с соседями пунктов такой же степени в таблице.
6. Если после шага 5 все совпадения однозначны — соответствие построено полностью.
7. Если остаются несколько допустимых вариантов, проверить, не совпадают ли искомые в вопросе вершины во всех этих вариантах — если да, их можно указать в ответе без полного построения соответствия.
8. Проверить ответ подстановкой всех рёбер графа в таблицу.
9. Записать ответ строго в требуемом формате: цифры по возрастанию, без пробелов и знаков.

Разбор примеров

Пример 1. Таблица 6×6, по строкам считаем звёздочки — получаем степени пунктов: $\deg(1)=2,\ \deg(2)=3,\ \deg(3)=2,\ \deg(4)=5,\ \deg(5)=2,\ \deg(6)=2$. Сумма степеней $2+3+2+5+2+2=16$, значит рёбер $|E|=8$ — число чётное, подсчёт верен. Шаг 1: на рисунке ищем вершину, соединённую со всеми остальными (степень 5) — она единственная, сопоставляем её с пунктом 4. Шаг 2: ищем вершину со степенью 3 — она тоже единственная, сопоставляем с пунктом 2. Шаг 3: остаются четыре вершины со степенью 2 (среди них A и G) — их нельзя различить по одной лишь степени, поэтому смотрим, с кем именно они соединены: часть из них соединена и с пунктом 2, и с пунктом 4 одновременно, часть — только с одним из них. Шаг 4: вершины A и G по рисунку связаны именно с этой уникальной парой опорных вершин так, что их можно однозначно узнать по номерам соседей — в итоге A получает номер 3, G — номер 5. Ответ записываем по возрастанию: 35.

Пример 2. Таблица 7×7 даёт степени: $\deg(1)=3,\ \deg(2)=3,\ \deg(3)=6,\ \deg(4)=2,\ \deg(5)=2,\ \deg(6)=3,\ \deg(7)=3$. Сумма $=22$, рёбер 11. Шаг 1: пункт со степенью 6 связан со всеми остальными вершинами — на графе это тоже легко узнаваемая «центральная» вершина, сопоставляем её с пунктом 3. Шаг 2: два пункта со степенью 2 определяются по тому, с кем именно из «центра» и друг с другом они соединены. Шаг 3: остаются четыре вершины со степенью 3, среди них искомые A и G. Сравниваем их связи с уже определёнными опорными вершинами (степени 6 и 2): у большинства из этих четырёх наборы соседей совпадают частично, но у A и G обнаруживается особое сочетание — они единственные среди вершин степени 3, которые связаны друг с другом напрямую. Шаг 4: это связывает их с конкретными номерами в таблице — A и G получают номера 6 и 7. Ответ: 67.

Пример 3. Таблица 7×7 (П1…П7) даёт степени: $\deg(\Pi1)=2,\ \deg(\Pi2)=3,\ \deg(\Pi3)=2,\ \deg(\Pi4)=3,\ \deg(\Pi5)=2,\ \deg(\Pi6)=3,\ \deg(\Pi7)=3$. Сумма $=18$, рёбер 9. Здесь ни одна степень не является уникальной: степень 2 встречается три раза, степень 3 — четыре раза. Это значит, что полное соответствие между графом и таблицей построить однозначно нельзя — возможны несколько допустимых перестановок вершин, сохраняющих структуру графа (случай неоднозначного соотнесения). Однако вопрос требует найти только вершины Б и В. Проверяем: у части вершин степени 3 соседи — это две вершины степени 2 и одна степени 3; у других — иначе. Оказывается, что Б и В — единственная пара вершин степени 3, которые соединены между собой и при этом обе связаны с одной и той же вершиной степени 2. Такая локальная конфигурация сохраняется во всех допустимых изоморфизмах графа, поэтому, даже не восстанавливая полное соответствие для всех семи вершин, для Б и В можно указать номера однозначно: П2 и П6. Ответ: 26.

Этот пример показывает главное отличие подтемы «неоднозначное соотнесение»: неоднозначность всего графа не мешает точно определить конкретную запрошенную пару, если она обладает уникальной локальной структурой связей.

Типичные ошибки и ловушки

• Путают степень вершины с номером пункта или количеством пунктов в таблице.
• Считают звёздочки только в строке или только в столбце непоследовательно, из-за чего сбивается подсчёт для больших таблиц (7×7 и больше).
• Делают вывод о соответствии сразу по первому совпадению степени, не проверяя соседей — особенно опасно, когда степень повторяется у трёх и более вершин.
• Забывают проверить сумму степеней на чётность — это простой способ поймать ошибку в подсчёте на раннем этапе.
• При неоднозначном графе пытаются построить единственное полное соответствие, хотя в вопросе спрашивают только про конкретные две вершины — тратят время впустую или приходят к неверному выводу «однозначно нельзя определить».
• Не подставляют финальный ответ обратно в таблицу и рисунок для проверки всех рёбер, из-за чего пропускают ошибку в промежуточных рассуждениях.
• Нарушают формат ответа: пишут числа не по возрастанию, добавляют пробел или запятую между цифрами.

Как готовиться

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