
Навигация по странице
О задании
Задание 1 ЕГЭ по информатике направлено на проверку навыков учащихся представлять, считывать и анализировать данные в разных типах информационных моделей.
Информационные модели могут быть разными: схемы, карты, таблицы, графики или формулы. Что из себя представляет каждая модель мы рассмотрим далее в этой статье. В последнее время в заданиях ЕГЭ в качестве информационной модели используются графы, работе с которыми и будет посвящена значительная часть данной статьи.
В заданиях данного типа вам предстоит проанализировать представленный рисунок графа и таблицу к нему. Тем самым, однозначно соотнести значения в таблице с информацией, представленной на графе.
Задание 1 базового уровня сложности и на его решение отводится порядка трёх минут. Причем решается оно всегда ручным способом. Правда, стоит отметить, что существует и программное решение части этого задания, которое мы и рассмотрим далее. Оно значительно упрощает работу с анализом графа, но помните, что программное решение не заменяет вам анализ, а лишь позволяет убедиться в его корректности.
Во вступлении мы уже использовали несколько терминов, с которыми могут быть не знакомы некоторые читатели. Так что, прежде чем перейти к разбору алгоритма решения задания 1, давайте углубимся в теоретические основы информационных моделей.
Информационные модели
Информационные модели — это упрощённые представления реальных объектов, процессов или явлений, которые используются для анализа, прогнозирования и принятия решений.
Они позволяют структурировать информацию, выделяя ключевые свойства и взаимосвязи, и представлять её в удобной для обработки форме. Информационные модели широко применяются в информатике, математике, физике, экономике и других областях.
Основная цель информационной модели — описать объект или систему с помощью данных, которые можно обрабатывать с помощью компьютера. Для этого используются различные способы структурирования информации, такие как линейные списки, таблицы, деревья и графы. Рассмотрим эти понятия подробнее.
Давайте определим, что такое структурирование информации. Можно сказать, что это некоторый процесс организации данных в определённом порядке. Такой процесс позволяет эффективно хранить, обрабатывать и анализировать информацию.
Допустим, у нас есть список учащихся школы. По умолчанию он представляет собой просто перечисление имён учеников, их классов и оценок по каждому предмету.
Теперь представьте себя на месте завуча, которому нужно сделать анализ успеваемости 11 «А» класса по предмету «Информатика». Искать среди этого огромного списка всех одиннадцатиклассников и выбирать их оценки только по одному предмету будет проблематично.
Гораздо эффективней было бы изначально структурировать список учеников: разделить их по классам, в каждом классе добавить разделение по предметам и успеваемости.
Для данных такого типа идеально подошла бы таблица. Таблица — это структура данных, которая представляет информацию в виде строк и столбцов. Каждая строка соответствует отдельному объекту, а каждый столбец — определённому свойству объекта.
Например, представим, что у нас есть следующая иерархия таблиц:
Ученики школы → Параллель 11 классов → 11 «А» класс → Оценки по информатике.
Тогда данные об оценках наших учеников можно представить в виде такой таблицы:

А что за иерархия таблиц? Откуда она у нас взялась и как её представить?
В этом нам помогут иерархичные структуры данных, например — дерево.
Дерево — это иерархическая структура данных, в которой каждый элемент (узел) имеет одного родителя и может иметь несколько потомков. Корневой узел — это вершина дерева, а листья — узлы, не имеющие потомков
С деревьями, в частности бинарными, мы уже работали, когда разбирали задание 4 ЕГЭ по информатике.
Представленную выше иерархию можно визуализировать следующим образом:

Оранжевым цветом здесь выделен наш «путь» от корня — «Ученики» — до интересующей нас таблицы «Оценки по информатике».
Но, порой, отношения между объектами нашей информационной модели могут быть очень сложными и запутанными. В таком случае можно использовать графы.
Граф — это математическая абстракция, состоящая из двух основных компонентов:
- Множество вершин, которые представляют объекты
- Множество рёбер, которые описывают связи между этими объектами.
Рёбра могут быть ориентированными (иметь направление) или неориентированными (без направления). Также граф может быть взвешенным, если каждому ребру присвоено числовое значение (вес).
В качестве примера рассмотрим граф, которые представляет собой некоторую схему дорог между четырьмя населёнными пунктами.

Давайте дадим определение основным терминам, связанным с графами.
Вершина — это основной элемент графа, который представляет объект или сущность. Вершины могут быть пронумерованы или иметь буквенные метки для идентификации. В графическом представлении вершины обычно изображаются точками или кружками.
На нашем изображении вершины графа представляют собой населённые пункты: Колыбелька, Петрово, Васюки и Жогино.
Ребро — это связь между двумя вершинами. Ребро может быть направленным (иметь направление, обозначается стрелкой) или ненаправленным (не имеет направления, обозначается линией).
У нас ребра графа — зелёные линии между оранжевыми точками. Они обозначают дороги между населёнными пунктами. Здесь ребра ненаправленные: дороги эти ведут в обе стороны, то есть как из Колыбельки можно попасть в Петрово, так и обратно вернуться можно по той же дороге.
Если бы дороги были односторонними, то есть из Колыбельки можно было бы попасть только в Петрово, а приехать в неё только из Жогино, то такие ребра, как и сам граф, назывались бы направленными.
Логично предположить, что дороги между населёнными пунктами имеют какую-то протяжённость, которую было бы неплохо добавить к нашему графу. Например, можно записать длину каждой дороги в виде таблицы:

Такая таблица называется весовой матрицей графа. Весовая матрица — это квадратная матрица, где элемент wij указывает вес ребра между вершинами i и j. Если ребра между вершинами нет, то в матрице может быть указано бесконечное значение или нуль.
В задании 1 мы часто будем работать с весовыми матрицами, так что давайте подробнее разберёмся, как её следует понимать.
Здесь в первом столбце и первой строке находятся названия населённых пунктов (вершин), а на пересечении строки и столбца находится длина дороги между этими населёнными пунктами, если она существует.
Иными словами, можем так описать эту таблицу:
- Между Колыбелькой и Петрово есть дорога длиной 20
- Между Колыбелькой и Жогино также есть дорога, её длина 8
- Между Петрово и Васюками находится дорога длиной 10
- А длина дороги между Васюками и Жогино составляет 25
Вся остальная информация в таблице просто дублирует уже известную нам. Также можем нанести длину каждой дороги на изображение графа:

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

Теперь у нас есть 3 вершины со степенью 3 (Петрово и Озерки) и 3 вершины со степенью 2 (Колыбелька, Васюки и Жогино).
Алгоритм решения
У задания 1 ЕГЭ по информатике существует 3 разных типа формулировок. Во всех вариантах вам даётся схема дорог какого-либо района, изображённая в виде графа. Рядом со схемой располагается таблица. Это может быть либо весовая матрица, либо матрица смежности. Как их определить?
В весовой матрице расположены числа, обозначающие протяжённость дороги — длина ребра графа. В матрице смежности расположены только звезды, которые обозначают наличие дороги между двумя населёнными пунктами — вершинами графа.
Типы заданий разделяются по сложности, а равно и по времени и объёму выполнения задания. В первом типе даётся матрица смежности и требуется однозначно сопоставить номер пункта в таблице с его обозначением на графе.
Второй тип уже требует не только сопоставить номер с обозначением, но и подсчитать сумму протяжённостей дорог между некоторыми пунктами.
Третий же тип самый объёмный: он включает в себя действия из двух предыдущих типов. То есть сначала нужно сопоставить номера с обозначениями, затем расставить протяжённость каждой дороги. А в ответ же требуется дать длину кратчайшего пути между двумя пунктами.
Давайте рассмотрим решения заданий каждого типа подробнее.
Тип 1
Как уже было сказано, задания этого типа самые простые. Вам даны граф и матрица смежности. Необходимо проанализировать граф и сопоставить номера пунктов с их буквенными обозначениями на графе.
Имеем такую формулировку:
Задание 100
«На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

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

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

Теперь можем найти номера вершин C и G. На деле мы не сможем однозначно определить какой именно номер у выбранных вершин, поскольку тут граф симметричный и никаких признаков, отличающих эти две вершины у нас нет.
Единственное, что мы можем сказать, так это то, что у обеих вершин есть два соседа: A и D.
Смотрим по таблице какие два столбца пересекаются с номерами 3 и 7. Это столбцы с номерами 1 и 4. Следовательно, у C и G номера 1 и 4 или наоборот.

Теперь можем рассмотреть вершину F. Она единственная, которая не соединена с уже известными вершинами под номерами 3, 7, 4, 1. Значит её номер будет 5.
А с ней и с вершиной D соединяются две оставшиеся — B и E, с номерами 2 и 6.

Это и есть искомые номера вершин. В ответ даём два этих номера в порядке возрастания: 26.
Пример 1
Задание 101
«На рисунке справа схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам 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
это условие выполняется, то текущая перестановка является корректной.
Давайте рассмотрим, как этот код будет работать в нашем случае.
- Генерируются все перестановки букв
'ABCDEFG'
. - Для каждой перестановки проверяется, соответствует ли она графу:
- Например, если
i = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
, то:- Буква
A
соответствует позиции 1,B
— позиции 2 и так далее. - Для ребра BE (
x='B'
,y='E'
), проверяется, содержится ли число 2 (позицияB
) в строкеmatrix[4]
(строка дляE
).
- Буква
- Например, если
- Если все ребра удовлетворяют условиям, перестановка выводится.
Данный код нам выдаст следующие строки:
1 2 3 4 5 6 7
B G D E F A C
Сверху у нас номера из таблицы, а снизу соответствующие им названия вершин графа.
Следовательно, искомым нам населённым пунктам G и D соответствуют номера 2 и 3. Их и пишем в ответ: 23.
Тип 2
В заданиях этого типа нам предстоит не просто определить номера вершин, но и вычислить сумму протяжённости дорог (вес рёбер) на основе весовой матрицы.
Начнём с такой формулировки:
Задание 102
«На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C»
Решим эту задачу полностью ручным способом. Как обычно, начинаем с расстановки степеней вершин.
Здесь три вершины со степенью 2 — E, A и B. И четыре вершины со степенью 3 — F, C, D и G.

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

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

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

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

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

Получаем вес ребра AC 30, а DG — 8. Складываем два числа и пишем в ответе 38.
Пример 2
Задание 103
«На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта 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.

Находим два числа: 7 и 4. Складываем их и пишем в ответ число 11.
Тип 3
Задания данного типа в реальном ЕГЭ встречаются крайне редко. В таких заданиях помимо анализа графа предстоит еще и определить кратчайший путь от одной вершины до другой.
Делать это лучше путём перебора нескольких вариантов. Благо, обычно кратчайший путь находится среди 3-4 всех путей. Использовать какие-либо программные алгоритмы тут нежелательно, все же написать за 3 минуты программу в несколько десятков строк под силу не каждому.
Рассмотрим такую формулировку задания:
Задание 104
«На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт 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
Заменим номера в весовой матрице на названия вершин:

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

Длина ребра AB равна 10, а ребра BC — 9. Значит длина всей дороги будет составлять 19 километров.
Рассмотрим другой вариант: дорогу A-E-C.

Ребро AE весит 11, а EC — 8. Следовательно, длина дороги A-E-C все те же 19 километров.
Давайте тогда рассмотрим еще одну дорогу, которая состоит из 4 рёбер: A-B-D-C.

Выпишем длину каждой дороги:
- AB = 10
- BD = 5
- DC = 2
Следовательно, протяжённость всей дороги A-B-D-C составляет всего 17 километров.
Других дорог, не включающих уже рассмотренные, тут быть не может. Следовательно, ответом будет 17 километров.
Это должно навести вас на следующую мысль: даже если путь содержит в себе меньше всего рёбер, это еще не означает, что он будет самым коротким. Рассматривайте все возможные пути, которые не содержат в себе уже рассмотренные (т.е. которые не содержат в себе все рёбра каждого рассмотренного пути)!