Каталог: Задание №1. Анализ информационных моделей (Графы и таблицы)

Банк задач: 166 Формат ЕГЭ 2026 Базовый (1 балл) 3-5 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №1

Тема кодификатора Сопоставление весовой матрицы и графа дорог по степеням вершин и маякам

Сложность и баллы Базовый (1 балл)

Рекомендуемое время 3-5 мин

Инструменты решения Степени вершин, Таблица смежности, Вершины-маяки, Анализ окружения

Цель задания — однозначно сопоставить буквенные вершины графа с номерами пунктов (П1–П7) в весовой матрице расстояний и найти длину конкретного ребра или сумму длин маршрутов. Выполняется строго вручную за 3 минуты методом анализа степеней и соседей-маяков.

Основные прототипы и разновидности

Тип 1: Граф с уникальными степенями вершин

Каждая вершина (или большинство) имеет уникальное число дорог (например, 2, 3, 4, 5) — сопоставляется напрямую за 1 минуту.

Тип 2: Граф с зеркальной осевой симметрией

Граф имеет две симметричные ветки (например, вершины A и B имеют одинаковое окружение). Длина искомой дороги инвариантна (одинакова) при любом выборе раскладки.

Тип 3: Поиск суммы длин нескольких ребер / составного пути

Требуется найти сумму протяженностей дорог между несколькими парами пунктов (например, из А в В и из C в F).

Теоретический фундамент и алгоритмы

1. Теоретический фундамент: Степени вершин графа

Степень вершины (валентность) — это количество рёбер (дорог), выходящих из данной вершины.

В таблице смежности степень пункта $П_i$ равна количеству чисел (заполненных ячеек) в строке (или столбце) $П_i$.
На чертеже степень вершины — это количество отрезков дорог, примыкающих к букве.
Лемма о рукопожатиях: сумма степеней всех вершин графа всегда четна и равна удвоенному количеству ребер: $\sum \deg(v) = 2 \cdot |E|$.

2. Пошаговый 4-шаговый алгоритм решения («Метод Маяков»):

Шаг 1. Таблица степеней:
Выпишите степени всех букв с рисунка: например, $A(2), B(3), C(4), D(3), E(2), F(3), G(4)$.
Посчитайте степени всех строк матрицы: например, $П1(3), П2(2), П3(4), П4(3), П5(2), П6(3), П7(4)$.
Шаг 2. Поиск уникальных маяков:
Найдите вершины, степень которых встречается единственный раз. Например, если степень 4 имеют только $C$ и $G$, а степень 2 имеют $A$ и $E$.
Шаг 3. Анализ набора соседей (Окружение):
Если две вершины имеют одинаковую степень (например, обе степени 3), посмотрите на степени их соседей:
• Вершина $B(3)$ соединена с вершинами со степенями {2, 3, 4}.
• Вершина $D(3)$ соединена с вершинами со степенями {4, 4, 3}.
По набору степеней соседей любая вершина определяется со 100% однозначностью!
Шаг 4. Извлечение ответа из матрицы:
Найдите пересечение нужной строки и столбца (например, строка $П3$ и столбец $П5$) и выпишите число на их пересечении.

3. Подробный разбор реальной экзаменационной задачи:

Условие: На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в км). Определите длину дороги из пункта Б в пункт Е.

	П1	П2	П3	П4	П5	П6	П7	Степень
П1			15			9	12	3
П2					24		18	2
П3	15			8			14	3
П4			8		11			2
П5		24		11		17		3
П6	9				17		20	3
П7	12	18	14			20		4

Решение:

Единственная вершина степени 4 — это П7 (степень 4). На графе 4 дороги имеет только пункт В $\implies$ В = П7.
Вершины степени 2 — это П2 и П4. На графе степень 2 имеют пункты А и Г. При этом пункт $А$ соединен с $В (П7)$, а пункт $Г$ соединен с пунктом $Д (П5)$.
Смотрим на строку $П2$: она соединена с $П7 (В)$ и $П5$. Значит, А = П2, а Г = П4!
Сосед $П2$ (кроме $П7$) — это $П5$, значит $Д = П5$.
Смотрим, с кем соединен $П4 (Г)$: с $П3$ и $П5$. Значит, $Е = П3$.
Оставшийся сосед $П7$ — пункт Б = П1.
Нас просили найти длину дороги между Б (П1) и Е (П3): смотрим пересечение строки $П1$ и столбца $П3$ $\implies$ 15.

Ответ: 15

Лайфхаки и фишки для ускорения

Совет

Таблица расстояний всегда строго симметрична относительно главной диагонали — анализируйте только верхний треугольник таблицы!

Совет

Если вершина соединена со всеми остальными (вершина-звезда) — это строка с максимальным числом чисел в таблице.

Совет

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

Совет

Если сомневаетесь между двумя вершинами одинаковой степени, выпишите степени их соседей в порядке возрастания: например, {2, 3, 4} vs {3, 3, 4}.

Частые ошибки и экзаменационные ловушки

Ошибка: Пытаться угадать соответствие на глаз без выписывания степеней
При схожем расположении вершин визуальное сопоставление приводит к ошибке в 60% случаев.

Правильно: Сначала подписать степени всех вершин на рисунке и посчитать непустые ячейки в матрице!

Ошибка: Забыть перепроверить вопрос в конце задачи
Найти длину дороги из А в Б вместо суммы длин дорог из А в Б и из Д в Е.

Правильно: Всегда перечитывать последнее предложение условия перед окончательной записью ответа.

Ошибка: Паниковать при симметричном графе
Думать, что решение неверно, если вершины А и К невозможно различить между собой.

Правильно: При симметрии длина искомого ребра гарантированно одинакова для обоих вариантов сопоставления!

ГРОБ №1: Полная круговая симметрия (все вершины степени 3)

Граф в виде правильной трехмерной призмы или куба, где абсолютно все 8 вершин имеют одинаковую степень 3.

Алгоритм решения: В таких задачах сопоставление букв не единственно, но длина искомого ребра строго инвариантна (одинакова) при любом повороте. Выбирайте произвольную вершину за П1 и последовательно раскручивайте цепочку соседей.

Практические задачи из банка КИМ (Всего: 166)

Решать в песочнице СмартКИМ

Задача #9048 №1 ЕГЭ

Каталог: Задание №1. Анализ информационных моделей (Графы и таблицы)

Спецификация и суть задания №1

Основные прототипы и разновидности

Теоретический фундамент и алгоритмы

1. Теоретический фундамент: Степени вершин графа

2. Пошаговый 4-шаговый алгоритм решения («Метод Маяков»):

3. Подробный разбор реальной экзаменационной задачи:

Лайфхаки и фишки для ускорения

Частые ошибки и экзаменационные ловушки

Практические задачи из банка КИМ (Всего: 166)

Готовьтесь к ЕГЭ эффективно со СмартКИМ