Разборы · ЕГЭ, задание 1

Задание 1 ЕГЭ по информатике: граф и таблица дорог

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

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

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

• Степень вершины — число дорог, которые из неё выходят. На схеме считаем линии, в таблице — заполненные клетки в строке.
• Таблица симметрична: дорога 1–2 записана и в строке 1, и в строке 2. Это одна дорога, а не две.
• Вершина с уникальной степенью находится сразу. Если степени совпадают, смотрят на соседей: с какими вершинами она соединена.
• Расположение вершин на рисунке ничего не значит — важны только связи.

Как решать

1. Выпишите степени всех вершин схемы и всех пунктов таблицы.
2. Сопоставьте вершины с уникальными степенями.
3. Остальные найдите через соседей: «D соединена с F, а F — это пункт 1, значит D — один из соседей пункта 1».
4. Найдите нужные дороги в таблице. Часто граф симметричен и буквы нельзя восстановить однозначно, но ответ от этого не зависит — так задание и составлено.

Пример из демоверсии 2027

По таблице: пункт 1 соединён с пунктами 2 (39 км), 5 (53 км) и 6 (30 км); пункт 2 — с пунктом 3 (21 км); пункт 3 — с пунктами 4 (8 км) и 5 (3 км); пункт 4 — с пунктами 5 (13 км) и 6 (5 км). Найдите сумму длин дорог E–A и B–C.

Решение. На схеме у A и C по две дороги, у остальных вершин — по три. В таблице по две дороги у пунктов 2 и 6, значит, {A, C} = {2, 6}. Общий сосед A и C на схеме — F, а общий сосед пунктов 2 и 6 — пункт 1: F = 1. Третий сосед F — вершина D, у пункта 1 это пункт 5: D = 5. Соседи D, кроме F, — B и E, у пункта 5 это пункты 3 и 4.

Пусть A = 2. Тогда E — сосед пункта 2, то есть 3, а значит B = 4 и C = 6. Дорога E–A = 3–2 = 21 км, дорога B–C = 4–6 = 5 км. Если взять A = 6, получится зеркальная картина: E–A = 5 км, B–C = 21 км. Сумма в обоих случаях равна 26.

Проверить себя можно перебором: программа пробует все 720 способов раздать буквам номера и оставляет те, при которых дороги на схеме и в таблице совпадают.

from itertools import permutations

graph = ["CB", "CF", "FD", "DB", "DE", "BE", "FA", "AE"]   # дороги по схеме
table = {(1, 2): 39, (1, 5): 53, (1, 6): 30, (2, 3): 21,
         (3, 4): 8, (3, 5): 3, (4, 5): 13, (4, 6): 5}     # дороги из таблицы
roads = {frozenset(k): w for k, w in table.items()}

answers = set()
for p in permutations(range(1, 7)):
    num = dict(zip("ABCDEF", p))                          # буква -> номер пункта
    if {frozenset((num[a], num[b])) for a, b in graph} == set(roads):
        answers.add(roads[frozenset((num["E"], num["A"]))]
                    + roads[frozenset((num["B"], num["C"]))])
print(answers)                                            # {26}

Типичные ошибки

• Считают одну дорогу дважды, потому что она записана в двух клетках таблицы.
• Пытаются сопоставить буквы «по картинке», а не по связям.
• Останавливаются на первом подходящем соответствии и не проверяют, что все дороги совпали.
• Пишут ответ с единицами измерения. В поле ответа — только число.

Потренироваться: задание 1 новые варианты с проверкой ответа