Задание 1 ЕГЭ по информатике: таблица и граф — как сопоставить вершины, разбор и примеры

Задание 1 открывает экзамен и считается одним из самых «дешёвых» по времени: при аккуратном подходе оно решается за 3–5 минут. Проверяется умение работать с информационными моделями: одна и та же система дорог описана двумя способами — таблицей (матрицей смежности) и схемой (графом). Ваша задача — понять, какой вершине графа соответствует какой номер в таблице, и по этому соответствию найти нужную величину.

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

• понимание, что такое граф, вершина, ребро и степень вершины (число рёбер, выходящих из вершины);
• умение читать матрицу смежности: число на пересечении строки i и столбца j — длина дороги между пунктами i и j, пустая клетка — дороги нет;
• умение находить вершины с «уникальными» свойствами и по ним восстанавливать соответствие.

Буквы на схеме и номера в таблице выбраны независимо: пункт «А» на схеме вовсе не обязан быть пунктом 1 в таблице. Именно это и делает задание задачей на сопоставление.

Типичные формулировки

1. «Определите длину дороги из пункта Б в пункт Д» — самый частый вариант.
2. «Найдите сумму длин дорог Б–Г и В–Д» — встречается, когда граф симметричен и отдельные дороги однозначно не определяются, а сумма определяется.
3. «Определите, какие номера в таблице могут соответствовать пунктам Е и Ж; в ответе запишите их в порядке возрастания без разделителей».
4. Вариант без длин: в таблице стоят только отметки «есть дорога», а спрашивают номер пункта или количество дорог.

Во всех вариантах схема и таблица описывают один и тот же граф, поэтому количество вершин, рёбер и набор степеней у них совпадают. Это удобно использовать как самопроверку.

Пошаговый метод

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

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

Между семью пунктами проложены дороги. Длины дорог даны в таблице (П1–П7 — номера пунктов, пустая клетка — дороги нет).

На схеме те же пункты обозначены буквами, дороги на схеме: А–Б, А–В, Б–В, Б–Г, В–Д, Г–Д, Г–Е, Д–Ж, Е–Ж.

Вопрос 1. Какова длина дороги Г–Д? Вопрос 2. Чему равна сумма длин дорог Б–Г и В–Д?

Шаг 1. Степени по таблице. П1 — 3, П2 — 2, П3 — 2, П4 — 2, П5 — 3, П6 — 3, П7 — 3.

Шаг 2. Степени по схеме. А — 2, Б — 3, В — 3, Г — 3, Д — 3, Е — 2, Ж — 2. Набор совпадает: три вершины степени 2 и четыре степени 3.

Шаг 3. Ищем отличительный признак. Вершин степени 2 три: А, Е, Ж. Но только у А оба соседа (Б и В) имеют степень 3 и соединены между собой. В таблице среди П2, П3, П4 таким свойством обладает только П3: её соседи П1 и П6 — степени 3, и дорога П1–П6 есть. Значит, А = П3, а {Б, В} = {П1, П6}.

Шаг 4. Соседи. Тогда {Е, Ж} = {П2, П4}, а {Г, Д} = {П5, П7}. Вершина Г соединена с Б и Е; П5 соединена с П6 и П2, а П7 — с П1 и П4. Получаем два согласованных варианта:

• Б = П6, Г = П5, Е = П2, В = П1, Д = П7, Ж = П4;
• Б = П1, Г = П7, Е = П4, В = П6, Д = П5, Ж = П2.

Это и есть симметрия схемы: отражение меняет местами Б↔В, Г↔Д, Е↔Ж.

Шаг 5. Ответы. Дорога Г–Д в обоих вариантах — это дорога П5–П7, её длина 14. Сумма Б–Г и В–Д: в первом варианте 9 + 11, во втором 11 + 9, то есть 20 в обоих случаях. Обратите внимание: длину одной дороги Б–Г определить нельзя (это 9 или 11), поэтому в таких графах и спрашивают сумму.

Ответы: 14; 20.

Проверка перебором на Python

На экзамене есть компьютер, и сопоставление можно проверить полным перебором: перебираем все перестановки номеров и оставляем те, при которых рёбра схемы совпадают с рёбрами таблицы. Для 7–8 вершин это мгновенно (8! = 40 320 вариантов).

from itertools import permutations

# рёбра таблицы: (пункт, пункт): длина
table = {(3, 6): 12, (1, 3): 8, (1, 6): 15, (5, 6): 9, (1, 7): 11,
         (5, 7): 14, (2, 5): 6, (4, 7): 10, (2, 4): 7}
graph = ['АБ', 'АВ', 'БВ', 'БГ', 'ВД', 'ГД', 'ГЕ', 'ДЖ', 'ЕЖ']
letters = 'АБВГДЕЖ'
edges = {frozenset(k): w for k, w in table.items()}

answers = set()
for p in permutations(range(1, len(letters) + 1)):
    m = dict(zip(letters, p))
    if {frozenset((m[a], m[b])) for a, b in graph} == set(edges):
        answers.add(edges[frozenset((m['Г'], m['Д']))])
print(answers)  # {14}

Если в множестве answers оказалось несколько значений — вы ошиблись при переносе данных или задаёте не тот вопрос. Если множество пустое — ребро списано неверно.

Частые ошибки

• Путают букву и номер. «А» на схеме и П1 в таблице — разные вещи, пока соответствие не доказано.
• Считают степени по столбцам и строкам дважды. Таблица симметрична: степень — это число заполненных клеток в одной строке.
• Останавливаются на первом подходящем варианте. Если степени повторяются, проверьте все варианты — иначе легко дать ответ, который верен лишь «в одном из отражений».
• Ошибаются при чтении таблицы. Длина дороги i–j стоит и в строке i, и в строке j; сверяйте оба места.
• Записывают лишнее в ответ. Ответ — одно число без единиц измерения.

Как экономить время

Начните с самой «редкой» степени: единственная вершина степени 1 или 4 сразу даёт опору. Дальше идите по соседям, как по цепочке. Подробно про степени вершин и признаки соответствия — в статье «Сопоставление таблицы и графа по степеням вершин».

Потренируйтесь

Закрепите метод на заданиях банка: задания № 1 в банке. Решите 5–7 задач подряд, засекая время: цель — не больше 4 минут на задачу. Следующее задание экзамена — задание 2: таблицы истинности.