Обо мне
Меня зовут Елена, и я занимаюсь подготовкой школьников к ЕГЭ 8 лет. В 2010 году я сдавала ЕГЭ по информатике для поступления (сдавала информатику, когда это еще не было мейнстримом)). Тогда основная часть экзамена была очень легкой: по моим ощущениям, на уровне современного ОГЭ. За 12 лет КИМы сильно усложнились, но я считаю это плюсом – теперь экзамен соответствует формату вступительного для вуза.
Мне нравится заниматься со школьниками информатикой, решать интересные (=сложные) задачи, рассказывать какие-то лайфхаки и слышать «ух ты, а так можно было?».
На этом канале я планирую рассказывать, как решать задачи базового и повышенного уровня. Надеюсь на вашу обратную связь – понятно ли объяснение, получается ли решать задачи из ДЗ. Также приветствую предложения разобрать какое-то конкретное задание.
О задании 1 типа из ЕГЭ по информатике
В данный момент на экзамене представлены задачи, в которых требуется уметь работать с информационными моделями, изображающими схему дорог между населенными пунктами. Несмотря на разные формулировки вопросов, задания можно разбить на две группы. Для получения ответа в задачах из первой группы нужно найти полное или частичное соответствие между графом и таблицей. В задачах второй группы предлагается найти кратчайший (или самый длинный) маршрут между двумя пунктами, опираясь на информационную модель в виде графа или таблицы. Строго говоря, существуют задачи и со смешанными формулировками.
В рамках этой статьи:
- рассмотрим кусочек теории графов (да простит меня мой преподаватель по дискретной математике!), который понадобится для решения задач формата ЕГЭ по информатике. Сразу оговорюсь, что теорию я объясняю больше «на пальцах», чем в академическом формате;
- порешаем задачи из ЕГЭ с двух источников (рассмотрим только задачи на соответствие между графом и таблицей);
- в конце я приведу список задач для самостоятельной отработки.
Немного теории
Что такое граф?
Граф – это геометрическая фигура, состоящая из точек, называемых вершинами, соединенных отрезками – ребрами графа. Для облегчения восприятия можно думать о графе как о городах, соединенных дорогами.
Графы бывают ориентированными и неориентированными (их еще называют направленными и ненаправленными). Ориентированные графы – те, ребра которых имеют направление (оно указывается стрелкой). По таким ребрам можно перемещаться только в одну сторону. Неориентированные графы – те, ребра которых не имеют направления (см. рис. 1).
В рамках первого задания будем рассматривать неориентированные графы.
Соответствие между графом и таблицей
В соответствие графу можно поставить таблицу. Для этого пронумеруем вершины графа с рис. 1(б) буквами. У нас получилось пять вершин (от А до Д).
Теперь построим таблицу, соответствующую нашему графу. Она будет иметь следующий вид:
Ячейки, стоящие на пересечении строк и столбцов, обозначают соответствующие ребра графа. В нашем примере есть ребро АБ (отрезок, соединяющий вершины А и Б). Отметим ячейки таблицы, соответствующие этому ребру, символом «*». Таких ячеек две, так как граф неориентированный, и мы можем передвигаться как из А в Б, так и из Б в А.
Теперь заметим, что нет ребер, соответствующих ячейкам, стоящим на диагонали таблицы (нет ребра АА, ББ и т.д.). Такие ячейки принято заштриховывать:
Отметим в таблице остальные ребра. Заметим, что заштрихованная диагональ является осью симметрии всей таблицы (верхняя половина таблицы симметрична нижней относительно диагонали). Это признак соответствия таблицы неориентированному графу.
Примечание: подобную (но несимметричную) таблицу можно построить и для ориентированного графа.
Посмотрим еще раз на изначальный граф и построенную таблицу. Нужно понимать, что и то, и другое – информационная модель, построенная для одной и той же сети дорог между населенными пунктами. Эти модели равнозначны: все данные, которые можно получить из графа (например, со сколькими пунктами связан пункт А), можно получить и из таблицы.
Степень вершины графа
Дадим нестрогое определение понятию, полезному при решении задач.
Число дорог, выходящих из вершины А неориентированного графа, будем называть степенью вершины А. Степень вершины может быть нулевой, если к этой вершине не ведут дороги, или равной натуральному числу.
Примеры на определение степеней вершин
Пример 1.
Рассмотрим граф на рис. 3 и определим степени для каждой его вершины.
Из вершины А выходит (или входит) две дороги – это вершина степени 2.
Вершина Б – степень 1.
Вершина В – степень 3.
Вершина Г – степень 2.
Вершина Д – степень 0.
Также степени можно определить по таблице. Если данные представлены в табличном виде, мы не можем говорить о степени вершины, так как вершины относятся к графам. Будем эти значения неакадемично называть степенями пунктов.
Пример 2.
В таблице приведены данные о дорогах между населенными пунктами. Найдем степени для каждого пункта.
Чтобы найти степень конкретного пункта, нужно посчитать, со сколькими пунктами он связан дорогой. Считать можно по строкам или столбцам. Для определенности будем считать по строкам.
Чтобы посчитать степень для пункта А, посмотрим, сколько звездочек стоит в соответствующей строке. Их две – на пересечении строки А и столбцов В и Д. Значит, степень вершины А равна 2.
Аналогично считаем степени других вершин.
Задачи ЕГЭ (Тип 1)
Перейдем к заданиям из ЕГЭ. Примеры я беру из двух источников – сайта Решу ЕГЭ и сайта Константина Полякова. По моим наблюдениям, задания из первого источника не всегда близки к тем, что предлагают на экзамене (легкие задачи или устаревшие формулировки), но они подходят для знакомства с темой. На сайте К. Полякова задачи более актуальные, хотя бывают слишком сложного, не егэшного, уровня.
Задание 1 (Решу ЕГЭ, № 9354)
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.
Решение:
Итак, нужно определить номер пунктов В и Е в таблице и посмотреть, какое число стоит в ячейке на пересечении соответствующих строки и столбца.
Первым делом определяем степени вершин пунктов из условия.
Вершина В – степень 5.
Вершина Е – степень 4.
Дальше смотрим, есть ли еще вершины с такими степенями.
Вершины А, Б, Д, К – степень 2; вершина Г – степень 3. Получается, у нас есть только по одной вершине степени 5 и 4, и это В и Е.
Найдем пункты со степенями 4 и 5 в таблице.
Будем считать степени всех пунктов по порядку:
П1 – степень 2, П2 – степень 3, П3 – степень 2, П4 – степень 4 (значит, это Е), П5 – степень 2, П6 – степень 5 (это В).
Ищем число на пересечении столбца П4 и строки П6 (или наоборот, так как граф неориентированный, следовательно, таблица симметрична): 20. Это и будет ответом.
Задание 2 (Решу ЕГЭ, № 15619)
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о дорогах между населенными пунктами (звездочка означает, что дорога между соответствующими городами есть).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите номера населенных пунктов A и G в таблице. В ответе запишите числа в порядке возрастания без разделителей.
Решение:
Первое наше действие – определить степени вершин из вопроса.
Вершина A – степень 2.
Вершина G – степень 2.
Дальше смотрим, если ли еще вершины степени 2?
Да, есть. Это вершины С и Е.
А чем вершины A и G отличаются от вершин C и E?
Из графа видим, что вершины C и E связаны ребром с вершиной D (степени 3), а A и G связаны между собой и с вершиной В. Стоит отметить, что связь с вершиной В не дает нам никакой полезной информации, так как эта вершина связана ребрами со всеми остальными.
Получается, что, найдя в таблице пункт степени 3 (соответствующий вершине D), мы найдем три пункта, с которыми он связан. Два из них будут иметь степень 2 – C и Е, и один – степень 5 (вершина В). После этого мы будем знать, какие пункты соответствуют вершинам B, C, D и E, и методом исключения найдем A и G.
Сделаем это!
- Пункт 2 имеет степень 3, значит, это D.
- Пункт 2 связан с п.1 и п.6 степени 2 – значит, мы нашли С и Е.
- Пункт 4 имеет степень 5 – это В.
- На данном этапе имеем: п.1 и п.6 – это С и Е, п.2 – это D, п.4 – это В. Остаются пункты 3 и 5.
- Читаем вопрос: «в ответе запишите числа в порядке возрастания без разделителей». Значит, ответ 35.
Примечание.
Почему в этой задаче просят найти номера двух пунктов, а не только А, к примеру?
Давайте посмотрим на граф (рис. 4).
В данной задаче граф симметричный (я провела фиолетовым ось симметрии). Это значит, что при поиске соответствий между графом и таблицей мы можем однозначно определить вершины, лежащие на оси симметрии (B и D, если нет дополнительных осей симметрии), и не можем однозначно определить симметричные вершины.
Поэтому в вопросе предлагают найти номера пунктов, соответствующих симметричным вершинам, и записать оба числа.
Это были простые задачи из ЕГЭ 2016 и 2018 года. Рассмотрим еще одну посложнее.
Задание 3 (сайт К. Полякова, № 4841)
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина дороги ЗЕ равна 15 км. Определите длину дороги БГ. В ответе запишите целое число – длину дороги в километрах.
Решение:
По графу видно, что он симметричный, ось симметрии проходит по ребру ЗД. Получается, мы не можем отличить однозначно Е от Ж, А от Б, В от Г, а дорогу БГ, длину которой нужно найти, от дороги АВ. Но составители дают нам дополнительные данные – длину дороги ЕЗ (15 км).
Смотрим в таблицу. Дорог, равных 15, у нас четыре:
- между п1 и п2 (п1 – степень 5, п2 – степень 2);
- между п1 и п7 (п1 – степень 5, п7 – степень 3);
- между п3 и п4 (п3 – степень 2, п4 – степень 3);
- между п4 и п8 (п4 – степень 3, п8 – степень 3).
Какая из них ЕЗ? Смотрим на граф. Вершина Е имеет степень 3, вершина З – степень 3. У нас есть только одна дорога, соединяющая пункты со степенями 3 – дорога между п4 и п8.
Смотрим в таблицу. П4 связан с п1 (степень 5, это Д), п3 (степень 2) и п8 (степень 3). Значит, п4 – это Е, так как З связан с Д и с двумя пунктами степени 3.
Если п4 – это Е, то связанный с ним п3 со степенью 2 – это А. В свою очередь, п3 связан с п2 со степенью 2, значит, п2 – это В.
У нас осталось только два пункта со степенью 2 – п5 и п6. Значит, это Б и Г. Дорога из п6 в п5 (длина ребра БГ) равна 20. Это и будет ответом.
Примечание. Подобное решение может показаться запутанным, однако после некоторой тренировки с подобными задачами вполне можно справляться за три минуты, отведенные на них в спецификации. Ниже я дам список задач для самостоятельного решения. Рекомендую прорешать их все – я привожу примеры задач с разными формулировками, что позволяет посмотреть на одно и то же задание под разными углами.
Домашнее задание:
Сайт К. Полякова: №№ 5360, 5292, 4653, 4145, 3640, 3635, 3200, 2824, 88