зад1

Задание 1 ЕГЭ по информатике направлено на проверку навыков учащихся представлять, считывать и анализировать данные в разных типах информационных моделей.

Информационные модели могут быть разными: схемы, карты, таблицы, графики или формулы. Что из себя представляет каждая модель мы рассмотрим далее в этой статье. В последнее время в заданиях ЕГЭ в качестве информационной модели используются графы, работе с которыми и будет посвящена значительная часть данной статьи.

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

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

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

Информационные модели

Информационные модели — это упрощённые представления реальных объектов, процессов или явлений, которые используются для анализа, прогнозирования и принятия решений.

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

Основная цель информационной модели — описать объект или систему с помощью данных, которые можно обрабатывать с помощью компьютера. Для этого используются различные способы структурирования информации, такие как линейные списки, таблицы, деревья и графы. Рассмотрим эти понятия подробнее.

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

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

Теперь представьте себя на месте завуча, которому нужно сделать анализ успеваемости 11 «А» класса по предмету «Информатика». Искать среди этого огромного списка всех одиннадцатиклассников и выбирать их оценки только по одному предмету будет проблематично.

Гораздо эффективней было бы изначально структурировать список учеников: разделить их по классам, в каждом классе добавить разделение по предметам и успеваемости.

Для данных такого типа идеально подошла бы таблица. Таблица — это структура данных, которая представляет информацию в виде строк и столбцов. Каждая строка соответствует отдельному объекту, а каждый столбец — определённому свойству объекта.

Например, представим, что у нас есть следующая иерархия таблиц:

Ученики школы → Параллель 11 классов → 11 «А» класс → Оценки по информатике.

Тогда данные об оценках наших учеников можно представить в виде такой таблицы:

Задание 1 1 2

А что за иерархия таблиц? Откуда она у нас взялась и как её представить?

В этом нам помогут иерархичные структуры данных, например — дерево.

Дерево — это иерархическая структура данных, в которой каждый элемент (узел) имеет одного родителя и может иметь несколько потомков. Корневой узел — это вершина дерева, а листья — узлы, не имеющие потомков

С деревьями, в частности бинарными, мы уже работали, когда разбирали задание 4 ЕГЭ по информатике.

Представленную выше иерархию можно визуализировать следующим образом:

Задание 1 2 2

Оранжевым цветом здесь выделен наш «путь» от корня — «Ученики» — до интересующей нас таблицы «Оценки по информатике».

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

Граф — это математическая абстракция, состоящая из двух основных компонентов:

  1. Множество вершин, которые представляют объекты
  2. Множество рёбер, которые описывают связи между этими объектами.

Рёбра могут быть ориентированными (иметь направление) или неориентированными (без направления). Также граф может быть взвешенным, если каждому ребру присвоено числовое значение (вес).

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

Задание 1 3

Давайте дадим определение основным терминам, связанным с графами.

Вершина — это основной элемент графа, который представляет объект или сущность. Вершины могут быть пронумерованы или иметь буквенные метки для идентификации. В графическом представлении вершины обычно изображаются точками или кружками.

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

Ребро — это связь между двумя вершинами. Ребро может быть направленным (иметь направление, обозначается стрелкой) или ненаправленным (не имеет направления, обозначается линией).

У нас ребра графа — зелёные линии между оранжевыми точками. Они обозначают дороги между населёнными пунктами. Здесь ребра ненаправленные: дороги эти ведут в обе стороны, то есть как из Колыбельки можно попасть в Петрово, так и обратно вернуться можно по той же дороге.

Если бы дороги были односторонними, то есть из Колыбельки можно было бы попасть только в Петрово, а приехать в неё только из Жогино, то такие ребра, как и сам граф, назывались бы направленными.

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

Задание 1 4 1

Такая таблица называется весовой матрицей графа. Весовая матрица — это квадратная матрица, где элемент wij указывает вес ребра между вершинами i и j. Если ребра между вершинами нет, то в матрице может быть указано бесконечное значение или нуль.

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

Здесь в первом столбце и первой строке находятся названия населённых пунктов (вершин), а на пересечении строки и столбца находится длина дороги между этими населёнными пунктами, если она существует.

Иными словами, можем так описать эту таблицу:

  1. Между Колыбелькой и Петрово есть дорога длиной 20
  2. Между Колыбелькой и Жогино также есть дорога, её длина 8
  3. Между Петрово и Васюками находится дорога длиной 10
  4. А длина дороги между Васюками и Жогино составляет 25

Вся остальная информация в таблице просто дублирует уже известную нам. Также можем нанести длину каждой дороги на изображение графа:

Задание 1 5 1

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

И последний термин, которым мы будем пользоваться при решении задания 1 — это степень вершины. Степенью вершины называется количество рёбер, которые выходят из данной вершины. Так, на рассматриваемом графе у каждой вершины степень 2.

Представим теперь, что между Жогино и Васюками построили новый населённый пункт — Озерки. Также из него проложили дорогу в Петрово, а дороги между Васюками и Жогино больше не существует. Получим такой граф:

Задание 1 6 1

Теперь у нас есть 3 вершины со степенью 3 (Петрово и Озерки) и 3 вершины со степенью 2 (Колыбелька, Васюки и Жогино).

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

У задания 1 ЕГЭ по информатике существует 3 разных типа формулировок. Во всех вариантах вам даётся схема дорог какого-либо района, изображённая в виде графа. Рядом со схемой располагается таблица. Это может быть либо весовая матрица, либо матрица смежности. Как их определить?

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

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

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

Третий же тип самый объёмный: он включает в себя действия из двух предыдущих типов. То есть сначала нужно сопоставить номера с обозначениями, затем расставить протяжённость каждой дороги. А в ответ же требуется дать длину кратчайшего пути между двумя пунктами.

Давайте рассмотрим решения заданий каждого типа подробнее.

Тип 1

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

Имеем такую формулировку:

Задание 100

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

Задание 1 7 1

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

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

Задание 1 8 1

Здесь у нас одна вершина D со степенью 5, одна вершина A со степенью 3 и все остальные вершины со степенью 2.

Анализ графа начинаем с выявления «особенных» вершин. Поскольку здесь у нас только одна вершина со степенью 5, то находим в таблице строку, в которой 5 звёзд. Следовательно, вершина D имеет номер 7.

Аналогично поступаем и с вершиной А, которая единственная со степенью 3. Ей будет соответствовать номер 3.

Задание 1 9 1

Теперь можем найти номера вершин C и G. На деле мы не сможем однозначно определить какой именно номер у выбранных вершин, поскольку тут граф симметричный и никаких признаков, отличающих эти две вершины у нас нет.

Единственное, что мы можем сказать, так это то, что у обеих вершин есть два соседа: A и D.

Смотрим по таблице какие два столбца пересекаются с номерами 3 и 7. Это столбцы с номерами 1 и 4. Следовательно, у C и G номера 1 и 4 или наоборот.

Задание 1 10 1

Теперь можем рассмотреть вершину F. Она единственная, которая не соединена с уже известными вершинами под номерами 3, 7, 4, 1.  Значит её номер будет 5.

А с ней и с вершиной D соединяются две оставшиеся — B и E, с номерами 2 и 6.

Задание 1 11

Это и есть искомые номера вершин. В ответ даём два этих номера в порядке возрастания: 26.

Пример 1

Задание 101

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

Задание 1 12

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

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

Здесь же все гораздо запутанней. Для того, чтобы верно определить номер «особенных» вершин (здесь G, C и E) нужно анализировать не только их соседние вершины, но и соседей этих соседних вершин. Это может занять много времени (помним же про рекомендуемое время выполнения этого задания в три минуты?).

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

Для решения можно использовать такую программу:

from itertools import permutations

graph = 'BE EF FD DC CA AG GB BA CF'.split()
matrix = '246 26 57 15 347 127 356'.split()

print(*range(1, 8))

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

Давайте разберёмся, что происходит в этой программе. Работать мы будем с перестановками, следовательно импортируем функцию permutations из модуля itertools.

Далее в переменной graph перечисляем все рёбра графа. Это можно делать в произвольном порядке, главное — не упустить ни одного ребра. Методом split() разделяем эту строки на несколько и помещаем их в список. Каждая строка в списке — это пара вершин, соединенных ребром (например, «BE» означает, что вершина B связана с вершиной E)

В переменной matrix мы помещаем матрицу смежности таким образом: идем по строкам сверху вниз и, если есть пересечение строки и столбца, записываем номера этих столбцов. То есть каждый элемент матрицы содержит номера вершин, с которыми соответствующая вершина связана (например, «246» означает, что вершина 1 связана с вершинами 2, 4 и 6).

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

  • Для каждой пары (x, y) из списка graph:
    • i.index(x) + 1: Находим позицию буквы x в текущей перестановке i и добавляем 1 (так как индексы начинаются с 0, а нам нужны номера от 1 до 7).
    • matrix[i.index(y)]: Находим строку в матрице, соответствующую букве y.
    • Проверяем, содержится ли номер str(i.index(x) + 1) в строке matrix[i.index(y)].

Если для всех пар (x, y) из graph это условие выполняется, то текущая перестановка является корректной.

Давайте рассмотрим, как этот код будет работать в нашем случае.

  1. Генерируются все перестановки букв 'ABCDEFG'.
  2. Для каждой перестановки проверяется, соответствует ли она графу:
    • Например, если i = ('A', 'B', 'C', 'D', 'E', 'F', 'G'), то:
      • Буква A соответствует позиции 1, B — позиции 2 и так далее.
      • Для ребра BE (x='B', y='E'), проверяется, содержится ли число 2 (позиция B) в строке matrix[4] (строка для E).
  1. Если все ребра удовлетворяют условиям, перестановка выводится.

Данный код нам выдаст следующие строки:

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

Сверху у нас номера из таблицы, а снизу соответствующие им названия вершин графа.

Следовательно, искомым нам населённым пунктам G и D соответствуют номера 2 и 3. Их и пишем в ответ: 23.

Тип 2

В заданиях этого типа нам предстоит не просто определить номера вершин, но и вычислить сумму протяжённости дорог (вес рёбер) на основе весовой матрицы.

Начнём с такой формулировки:

Задание 102

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

Задание 1 13

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C»

Решим эту задачу полностью ручным способом. Как обычно, начинаем с расстановки степеней вершин.

Здесь три вершины со степенью 2E, A и B. И четыре вершины со степенью 3F, C, D и G.

Задание 1 14

Примечательными тут являются сразу две вершины: E, которая соединяется с двумя тройными вершинами и G, соединяющаяся с тремя тройными.

Для вершины E подходит номер 7. Давайте сразу будем подписывать буквы вершин в первой строке весовой матрицы.

Задание 1 15

Теперь определим вершину G. Поскольку она соединяется с тремя тройными вершинами, то ей подходит номер 5.

Задание 1 16

Зная вершины G и E можем найти вершины F и С, которые соседствуют с двумя уже известными нам. Это должны быть тройные вершины, каждая из которых имеет пересечение с 5-ой и 7-ой вершиной. Причем вершина C должна пересекаться с двумя двойными и одной тройной вершиной. А F — наоборот, с двумя тройными и одной двойной.

Видим, что первая вершина имеет два двойных соседа и одного тройного. Следовательно, это вершина C.

Для вершины F подходит номер 3: она пересекается с тройной вершиной G (5), тройной вершиной 6 и двойной вершиной E (7).

Задание 1 17

Оставшуюся единственную тройную вершину сразу видно: она под номером 6.

Теперь определимся с вершинами A и B. B должна пересекаться с только что найденной вершиной D (6), а A —с вершиной C под номером 1.

Задание 1 18

Анализ графа завершён. Теперь найдем вес рёбер AC и DG. Ищем числа на пересечении этих вершин в весовой матрице.

Задание 1 19

Получаем вес ребра AC 30, а DG8. Складываем два числа и пишем в ответе 38.

Пример 2

Задание 103

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

Задание 1 20

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

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

Здесь мы снова имеем довольно неприятный для анализа граф. Так что решим это заданием, используя программу на Python.

Код будет следующий:

from itertools import permutations

graph = 'BD DG GA AF FH HC CB BE ED EH GF'.split()
matrix = '234 157 147 138 268 58 23 456'.split()

print(*range(1,9))

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

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

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

Переносим названия вершин в весовую матрицу и ищем числа на пересечениях A с G и D с E.

Задание 1 21

Находим два числа: 7 и 4. Складываем их и пишем в ответ число 11.

Тип 3

Задания данного типа в реальном ЕГЭ встречаются крайне редко. В таких заданиях помимо анализа графа предстоит еще и определить кратчайший путь от одной вершины до другой.

Делать это лучше путём перебора нескольких вариантов. Благо, обычно кратчайший путь находится среди 3-4 всех путей. Использовать какие-либо программные алгоритмы тут нежелательно, все же написать за 3 минуты программу в несколько десятков строк под силу не каждому.

Рассмотрим такую формулировку задания:

Задание 104

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

Задание 1 22

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

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

Программа у нас следующая:

from itertools import permutations

graph = 'AB BD DG EA BC CD CE EF DF FG'.split()
matrix = '245 136 2567 16 137 234 35'.split()

print(*range(1,8))

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

На экран выведутся такие строки:

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

Заменим номера в весовой матрице на названия вершин:

Задание 1 23

И давайте теперь рассматривать различные комбинации дорог, ведущих от пункта A до пункта C.

Самая очевидная здесь, а вместе с тем и короткая на графе, дорога A-B-C.

Задание 1 24

Длина ребра AB равна 10, а ребра BC9. Значит длина всей дороги будет составлять 19 километров.

Рассмотрим другой вариант: дорогу A-E-C.

Задание 1 25

Ребро AE весит 11, а EC8. Следовательно, длина дороги A-E-C все те же 19 километров.

Давайте тогда рассмотрим еще одну дорогу, которая состоит из 4 рёбер: A-B-D-C.

Задание 1 26

Выпишем длину каждой дороги:

  1. AB = 10
  2. BD = 5
  3. DC = 2

Следовательно, протяжённость всей дороги A-B-D-C составляет всего 17 километров.

Других дорог, не включающих уже рассмотренные, тут быть не может. Следовательно, ответом будет 17 километров.

Это должно навести вас на следующую мысль: даже если путь содержит в себе меньше всего рёбер, это еще не означает, что он будет самым коротким. Рассматривайте все возможные пути, которые не содержат в себе уже рассмотренные (т.е. которые не содержат в себе все рёбра каждого рассмотренного пути)!