Задача № 1 из ЕГЭ-2021 по информатике

20 November

В этой статье мы решим задачу № 1 из демонстрационного варианта ЕГЭ-2021 года по информатике и рассмотрим, какие задачи этого типа встречались раньше. Впервые аналогичная задача была введена в ЕГЭ-2016 под номером 3, под этим номером она встречалась во всех ЕГЭ до 2020 года. Эта задача является очень простой, и важно научиться решать её быстро и правильно. Оптимальное время на решение этой задачи составляет 2-3 минуты. Для решения требуется внимательность и аккуратность. В конце статьи будет ссылка на тест на портале Эрудит.Онлайн. В этом тесте вы сможете потренироваться в решении задач такого типа. Обращайте внимание не только на правильность решения, но и на затраченное время. Видео-разбор задачи можно посмотреть на нашем канале в Youtube.

Задача № 1 из ЕГЭ-2021 по информатике

Демонстрационный вариант ЕГЭ-2021 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.

Решение

Для решения этой задача нам достаточно знать, что граф – это математический объект, представляющий собой множество вершин и соединяющих их линий, которые называются рёбрами графа. Граф может быть неориентированным как в этой задаче, или ориентированным – такой граф будет в задаче № 13. С точки зрения схемы дорог и её представления в виде графа, если дороги являются двусторонними, то используется неориентированный граф, если дороги односторонние, то используется ориентированный граф.
Если между двумя вершинами графа есть соединяющая их линия, то есть ребро графа, то говорят, что эти вершины смежны. На схеме это означает, что между соответствующими пунктами есть непосредственно соединяющая их дорога. Степенью вершины называется количество вершин, смежных с ней. На схеме это количество дорог, которые выходят из этого пункта, либо количество пунктов, в которые можно попасть непосредственно из данного пункта.

Решим задачу в 3 действия:

  1. найдём степени вершин на графе;
  2. определим степени вершин по таблице;
  3. найдём соответствие вершин на графе и пунктов в таблице.

Приступим к решению.

1. Степень вершины А равна 1, так как из неё непосредственно можно попасть только в пункт Б. Продолжаем и находим степени всех вершин:

Степени вершин графа
Степени вершин графа

2. По таблице мы видим, что в строке 3 есть только одно число, то есть из пункта 3 можно попасть только в один пункт 6. Это означает, что степень соответствующей вершины в графе также будет 1. Находим степени всех пунктов в таблице:

Степени пунктов по таблице
Степени пунктов по таблице

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

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

Осталось сопоставить вершины степени 2 и вершины степени 3, где есть несколько возможных вариантов. В условии нам нужно найти протяженность дороги между пунктами Г и Ж. Вершина Ж имеет степень 5, и мы уже нашли, что это пункт 4 в таблице. Вершина Г имеет степень 2 и нам достаточно определить только то, какой пункт в таблице ей соответствует – 1 или 2.

Заметим, что вершина В соединяется рёбрам с вершинами Б и Ж, то есть с пунктами 6 и 4. Значит, вершина В – это пункт 2, тогда Г – это пункт 1. Искомая протяжённость дороги между пунктами Г и Ж, то есть между пунктами 4 и 1, равна 9.

Для тренировки лучше построить полное соответствие:

Итоговое соответствие вершин графа и пунктов таблицы
Итоговое соответствие вершин графа и пунктов таблицы

Ответ: 9.

Для тренировки лучше сначала находить полное соответствие, но потом это можно будет не делать. Для скорости можно было бы заметить, что нас интересует дорога между вершиной степени 5 (Ж) и вершиной степени 2 (Г), которая смежна ещё с вершиной степени 3. Вершин степени 2 у нас только две, поэтому достаточно было бы найти вершину Г, как вершину степени 2, смежную с вершинами степени 3 и 5.

Видео-разбор задачи № 1 на нашем канале в Youtube:

Рассмотрим, какие задачи аналогичного типа встречались в демонстрационных вариантах ЕГЭ прошлых лет. Как уже было сказано, впервые задача такого типа появилась в 2016 году.

Демонстрационный вариант ЕГЭ-2016 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

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

Нужно найти дорогу между вершинами степени 4 и 5, а вершины с такими степенями в этом примере уникальны.

Демонстрационный вариант ЕГЭ-2017 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

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

Задача сложнее предыдущей. Вершина В - единственная, которая имеет степень 4. Нужно найти вершину Б, как вершину, смежную с вершинами степени 2 и 4.

Демонстрационный вариант ЕГЭ-2018 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта А в пункт Г. В ответе запишите целое число – так, как оно указано в таблице.

Задача проще предыдущей. Вершина Д - единственная вершина степени 2, а искомые вершины Г и А - смежные с ней вершины.

Демонстрационный вариант ЕГЭ-2019 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам B и C на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Задача отличается только тем, что нужно написать в ответе номера пунктов, а не длину дороги между ними. В данном графе единственная особенная вершина - вершина D. Вершины B и C различить между собой нельзя (такие вершины называются подобными), также как A и E, F и G. Проще всего найти вершину D, как вершину степени 2, смежные с которой вершины не смежны между собой. Эти вершины и являются искомыми.

Демонстрационный вариант ЕГЭ-2020 по информатике

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

Задача № 1 из ЕГЭ-2021 по информатике

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Д в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Задача отличается от рассмотренной задачи из демонстрационного варианта ЕГЭ-2021 только метками вершин графа.

Для тренировки на портале Эрудит.Онлайн подготовлен тест из 5 задач. Первая задача - одна из известных задач (демонстрационные варианты ЕГЭ, открытые варианты ЕГЭ и т.п.). Задачи 2-4 - задачи, составленные специально для этого теста. Некоторые задачи являются более сложными, чем задачи из демонстрационных вариантов. Рекомендуемое время для решения теста - 15 минут (по 3 минуты на задачу). После завершения теста показываются правильные ответы:

Тест «ЕГЭ-2021: Задача 1» на портале Эрудит.Онлайн

Задача № 1 из ЕГЭ-2021 по информатике