В этой статье мы решим задачу № 1 из проекта демонстрационного варианта ЕГЭ-2023 года по информатике и рассмотрим, какие задачи этого типа встречались раньше. Впервые аналогичная задача была введена в ЕГЭ-2016 под номером 3, под этим номером она встречалась во всех ЕГЭ до 2020 года. В демонстрационном варианте 2023-го года задача не изменилась по сравнению с вариантом 2022-го года. Эта задача является очень простой, и важно научиться решать её быстро и правильно. Оптимальное время на решение этой задачи составляет 2-3 минуты, задача оценивается в 1 балл и имеет базовую сложность. Для решения требуется внимательность и аккуратность. В конце статьи будет ссылка на тест на портале Эрудит.Онлайн, в котором вы сможете потренироваться в решении задач такого типа. Обращайте внимание не только на правильность решения, но и на затраченное время.
Демонстрационный вариант ЕГЭ-2023 по информатике
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт B и из пункта F в пункт A.
В ответе запишите целое число.
Решение
Для решения этой задача нам достаточно знать, что граф – это математический объект, представляющий собой множество вершин и соединяющих их линий, которые называются рёбрами графа. Граф может быть неориентированным как в этой задаче, или ориентированным – такой граф будет в задаче № 13. С точки зрения схемы дорог и её представления в виде графа, если дороги являются двусторонними, то используется неориентированный граф, если дороги односторонние, то используется ориентированный граф.
Если между двумя вершинами графа есть соединяющая их линия, то есть ребро графа, то говорят, что эти вершины смежны. На схеме это означает, что между соответствующими пунктами есть непосредственно соединяющая их дорога. Степенью вершины называется количество вершин, смежных с ней. На схеме это количество дорог, которые выходят из этого пункта, либо количество пунктов, в которые можно попасть непосредственно из данного пункта.
Решим задачу в 3 действия:
- Найдём степени вершин на графе;
- Определим степени вершин по таблице;
- Найдём соответствие вершин на графе и пунктов в таблице.
Приступим к решению.
1. Итак, первым действием мы подписываем степени всех вершин в графе и в таблице. Получаем для графа:
2. То же самое для таблицы:
3. Сопоставляем метки вершин в графе и в таблице. Видим, что все вершины имеют степень 2 или 3. Определим особенные вершины по их окружению, то есть вершинам, с которыми они смежны. Вершина A – единственная вершина степени 3, которая смежна только с вершинами степени 3 (это пункт 5 по таблице), вершина F – единственная вершина степени 3, смежная с двумя вершинами степени 2 и одной вершиной степени 3 (это пункт 2 по таблице), а вершина B – единственная вершина степени 2, смежная с двумя вершинами степени 3 (это пункт 4 по таблице):
Две смежные между собой вершины степени 2 (C и G) могут быть пунктами 1 и 3. Так как вершина F (пункт 2) смежна с C, то получаем, что вершина C – это пункт 1, а G – пункт 3. Наконец, вершина степени 3 (E), смежная с G, – это пункт 2, тогда оставшаяся вершина D – это пункт 7. Получили итоговое соответствие:
Находим ответ. Из пункта D в B (смотрим ячейку 7-4) длина 53, из F в A (смотрим ячейку 2-5) длина 5.
Ответ: 58
Демонстрационный вариант ЕГЭ-2022 по информатике
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта Б в пункт В и из пункта Г в пункт Д.
В ответе запишите целое число.
Решение
Решим задачу в 3 действия:
- Найдём степени вершин на графе;
- Определим степени вершин по таблице;
- Найдём соответствие вершин на графе и пунктов в таблице.
Приступим к решению.
1. Степень вершины К равна 6, так как она смежна со всеми остальными вершинами (кстати, такие вершины называются доминирующими). Степень вершины А равна 2, так как из неё непосредственно можно попасть только в пункт Б и К. Продолжаем и находим степени всех вершин:
2. По таблице мы видим, что в строке 1 есть только два числа, то есть из пункта 1 можно попасть только в пункты 2 и 5. Это означает, что степень соответствующей вершины в графе также будет 2. В строке 5 есть число в каждом столбце, а это означает, что из пункта 5 можно попасть во все остальные пункты. Находим степени всех пунктов в таблице:
3. Сравниваем степени вершин в графе и в таблице. Видим, что только у вершины К степень равна 6, значит, ей соответствует пункт 5 в таблице. Вершины А и Е имеют степень 2, значит, им могут соответствовать пункты 1 и 3.
Небольшая хитрость данной задачи состоит в том, что мы не можем точно сопоставить граф таблице. Действительно, рассмотрим два возможных случая.
Случай 1. Вершина А соответствует пункту 1.
Тогда вершине Е соответствует пункт 3. По таблице видим, что из пункта 1 (то есть вершины А), есть дороги в пункт 2 и 5 (то есть пункт К). Значит, пункт 2 соответствует вершине Б. Аналогично для пункта 3 (то есть вершины Е): есть дороги в пункт 4 и 5 (то есть в К). Значит, пункт 4 соответствует вершине Д. Далее смотрим на пункт 2, который соответствует вершине Б. Видим, что из него есть дороги в пункты 1(А), 5(К) и в 6. Следовательно, пункт 6 соответствует пункту В. Тогда оставшийся пункт 7 соответствует вершине Г. Получили соответствие:
Ответ в этом случае получается 20. Из пункта Б в В (смотрим ячейку 2-6) длина 13, из Г в Д (смотрим ячейку 7-4) длина 7:
Случай 2. Вершина А соответствует пункту 3.
Тогда вершине Е соответствует пункт 1. Рассуждаем аналогично случаю 1. По таблице видим, что из пункта 1 (то есть вершины Е), есть дороги в пункт 2 и 5 (то есть пункт К). Значит, пункт 2 соответствует вершине Д. Аналогично для пункта 3 (то есть вершины А): есть дороги в пункт 4 и 5 (то есть в К). Значит, пункт 4 соответствует вершине Б. Далее смотрим на пункт 2, который соответствует вершине Д. Видим, что из него есть дороги в пункты 1(Е), 5(К) и в 6. Следовательно, пункт 6 соответствует пункту Г. Тогда оставшийся пункт 7 соответствует вершине В. Получили соответствие:
Ответ в этом случае получается также 20. Из пункта Б в В (смотрим ячейку 4-7) длина 7, из Г в Д (смотрим ячейку 6-2) длина 13:
Итак, ответ: 20.
Для тренировки лучше найти все возможные соответствия, но потом это можно будет не делать. Можно заметить, что граф обладает определённой симметрией. На языке теории графов это означает, что существует автоморфизм (то есть отображение вершин графа, при котором граф переходит сам в себя), такой что вершина А подобна вершине Е, вершина Б подобна вершине Д, а вершина В подобна вершине Г. Соответственно, мы не сможем различить подобные вершины.
В другой нашей статье можно посмотреть еще примеры решения аналогичных задач из ЕГЭ предыдущих лет:
Задача № 1 из ЕГЭ-2021 по информатике
Для тренировки на портале Эрудит.Онлайн подготовлен тест из 5 задач. Первая задача - одна из известных задач (демонстрационные варианты ЕГЭ, открытые варианты ЕГЭ и т.п.). Задачи 2-4 - задачи, составленные специально для этого теста. Некоторые задачи являются более сложными, чем задачи из демонстрационных вариантов. Рекомендуемое время для решения теста - 15 минут (по 3 минуты на задачу). После завершения теста показываются правильные ответы:
Тест «ЕГЭ-2023: Задача 1» на портале Эрудит.Онлайн.
Другие полезные материалы по информатике на нашем канале:
#информатика #егэ #егэпоинформатике #школа #подготовкакегэ #егэпоинформатике #учительинформатики