Задание 1 ЕГЭ информатика

1. Введение

В задании № 1 дана схема дорог между населёнными пунктами и таблица расстояний. На схеме пункты обозначены буквами, а в таблице — номерами: П1, П2, П3 и так далее.

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

В задании используются следующие элементы:

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

Если в ячейке таблицы записано число, между соответствующими пунктами есть прямая дорога, а число показывает её длину. Пустая ячейка означает, что прямой дороги между пунктами нет.

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

2. Как работать с графом

Первое, на что нужно обратить внимание, — количество дорог, выходящих из каждой вершины. Это количество называется степенью вершины.

Например, если пункт соединён с тремя другими пунктами, его степень равна 3. В таблице соответствующая ему строка также будет содержать три заполненные ячейки.

Граф без выраженной симметрии

В таком графе вершины можно однозначно различить по их положению:

• они имеют разное количество дорог;
• соединены с вершинами разных степеней;
• имеют разное окружение.

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

Граф с симметрией

В графе с симметрией несколько вершин могут иметь одинаковое положение:

• одинаковую степень;
• одинаковые степени соседей;
• одинаковые связи с остальной частью графа.

Такие вершины можно поменять местами, и структура графа не изменится. Поэтому у задания может быть несколько правильных вариантов сопоставления букв и номеров.

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

Важно: речь идёт о нескольких правильных сопоставлениях вершин, а не о нескольких путях.

3. Алгоритм решения

Шаг 1. Посчитать степени вершин на схеме

Рядом с каждой вершиной запишите количество выходящих из неё дорог. Это число называется степенью вершины.

Шаг 2. Посчитать заполненные ячейки в таблице

Для каждой строки таблицы посчитайте количество чисел. Оно равно степени соответствующей вершины.

После этого сопоставьте вершины и строки с одинаковыми степенями.

Шаг 3. Найти первую опорную вершину

Сначала найдите вершину, которую проще всего сопоставить со строкой таблицы. От неё можно будет постепенно переходить к соседним вершинам.

Действуйте по порядку.

Случай 1. Есть уникальная степень

Проверьте, встречается ли какая-либо степень только один раз.

Например, если на схеме только одна вершина имеет степень 4, а в таблице только одна строка содержит четыре числа, эта вершина и строка точно соответствуют друг другу.

Пример: вершина А — единственная вершина степени 4, а П5 — единственная строка с четырьмя числами. Значит, А = П5.

Случай 2. Уникальных степеней нет

Если каждая степень встречается несколько раз, сравните степени соседей.

Для этого рядом с каждой подходящей вершиной выпишите степени всех вершин, с которыми она соединена.

Например, две вершины могут иметь степень 2, но:

• первая соединена с вершинами степеней (2, 2);
• вторая соединена с вершинами степеней (2, 3).

Собственные степени этих вершин одинаковы, но их окружение различается.

В таблице действуем так же: берём строки с двумя числами и определяем степени строк, с которыми они соединены.

Если только вершина А имеет окружение (2, 2) и только строка П4 соединена с двумя строками степени 2, то А = П4.

Случай 3. Отличий найти не удалось

Если совпадают и степени вершин, и степени их соседей, сделайте пробное предположение: сопоставьте одну из подходящих вершин с одной из подходящих строк и продолжайте расстановку от неё.

Это не случайный выбор ответа, а обычный перебор вариантов:

1. Предположите, например, что А = П2.
2. По связям начните определять соседние вершины.
3. Если появляется несостыковка — не совпадает степень, отсутствует нужная дорога или возникает лишняя, — первоначальное предположение неверно.
4. Вернитесь к первой вершине, замените П2 на другого кандидата и повторите расстановку.

Если противоречий не появилось, сопоставление подходит.

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

После нахождения первой опорной вершины определяйте остальные пункты по её связям: смотрите, с какими вершинами она соединена, сравнивайте их степени и постепенно двигайтесь по графу.

Шаг 4. Проверить результат и найти ответ

Перед тем как брать расстояние из таблицы, убедитесь, что:

• степени сопоставленных вершин совпадают;
• каждая дорога на схеме присутствует в таблице;
• лишних дорог в таблице нет;
• при симметрии ответ совпадает во всех допустимых вариантах сопоставления.

После проверки найдите в таблице ячейку на пересечении нужных пунктов и запишите указанное в ней расстояние.

4. Решение автоматическим перебором на Python

Если вручную сопоставить вершины сложно, можно перебрать все возможные соответствия между пунктами П1–П8 и буквами графа. Разберем код Python на примере данной задачи

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

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите, какова сумма протяжённостей дорог из пункта B в пункт H и из пункта A в пункт E.

В ответе запишите целое число.

from itertools import permutations

table = '567 348 278 27 168 15 134 235'.split()
graph = 'AB BH AH AE HF FG EG EC GC CD FD'.split()

print('1 2 3 4 5 6 7 8')

for i in permutations('ABCDEFGH'):
    if all(str(i.index(x) + 1) in table[i.index(y)] for x, y in graph):
        print(*i)

Запись таблицы

table = '567 348 278 27 168 15 134 235'.split()

В строке записываются не расстояния, а номера пунктов, с которыми соединена каждая строка таблицы:

• 567 — пункт П1 соединён с П5, П6 и П7;
• 348 — пункт П2 соединён с П3, П4 и П8;
• 278 — пункт П3 соединён с П2, П7 и П8;
• 27 — пункт П4 соединён с П2 и П7.

И так далее для всех восьми пунктов.

После выполнения split() получается список:

['567', '348', '278', '27', '168', '15', '134', '235']

Индекс элемента соответствует номеру пункта минус один:

table[0] — связи пункта П1
table[1] — связи пункта П2
...
table[7] — связи пункта П8

Расстояния в код не переносятся, потому что сначала программе нужно только восстановить соответствие между номерами и буквами.

Запись рёбер графа

graph = 'AB BH AH AE HF FG EG EC GC CD FD'.split()

Здесь перечисляются все дороги на графе:

• AB — дорога между A и B;
• BH — дорога между B и H;
• AH — дорога между A и H;
• AE — дорога между A и E.

Каждую дорогу достаточно записать один раз. Например, если записано AB, отдельно добавлять BA не нужно.

Перебор вариантов

for i in permutations('ABCDEFGH'):

Функция permutations() перебирает все возможные способы сопоставить восемь букв пунктам П1–П8.

Всего программа проверяет:

8! = 40 320 вариантов

Например, перестановка:

('H', 'C', 'G', 'D', 'A', 'B', 'F', 'E')

означает:

П1 = H
П2 = C
П3 = G
П4 = D
П5 = A
П6 = B
П7 = F
П8 = E

Проверка каждой перестановки

if all(str(i.index(x) + 1) in table[i.index(y)] for x, y in graph):

Для каждой дороги графа программа проверяет, существует ли такая же дорога в таблице.

Рассмотрим отдельные части выражения:

i.index(x)

Находит позицию буквы x в перестановке. Эта позиция соответствует номеру пункта, но отсчёт индексов начинается с нуля.

Поэтому прибавляется единица:

i.index(x) + 1

Так получается настоящий номер пункта, соответствующего букве x.

Выражение:

table[i.index(y)]

получает список соседей пункта, которому соответствует буква y.

Например, программа проверяет дорогу AB. Если в текущей перестановке:

A = П5
B = П6

то она проверяет, содержится ли номер 5 среди соседей пункта П6.

В таблице:

П6 соединён с П1 и П5

Следовательно, дорога между A и B существует.

Функция all() возвращает True только в том случае, если совпали все дороги графа. Если хотя бы одной дороги в таблице нет, программа переходит к следующей перестановке.

Результат работы программы

Программа выводит:

1 2 3 4 5 6 7 8
H C G D A B F E

Следовательно:

П1 = H
П2 = C
П3 = G
П4 = D
П5 = A
П6 = B
П7 = F
П8 = E

Теперь возвращаемся к исходной таблице расстояний:

• дорога B–H соответствует дороге П6–П1, её длина равна 15;
• дорога A–E соответствует дороге П5–П8, её длина равна 11.

Находим сумму:

15 + 11 = 26

Ответ: 26

Видео разбор задания: