Задание 1

Как решать задание 1 из ЕГЭ по информатике?

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

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

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

Что такое граф?

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

Графы бывают ориентированными и неориентированными. Ориентированные имеют ребра с определенным направлением, оно обозначается стрелкой, по ним можно перемещаться только в одном направлении. Неориентированные не имеют направления.

Решение 1 прототипа

Рассмотрим задачу, где нам дана только таблица. Чтобы решить задание, нам необходимо построить дерево.

Мы видим, что граф будет неориентированным, поскольку таблица симметрична относительно диагонали, то есть значения А → B = B → А и так далее.

Можно попасть из A в Z напрямую, в таком случае длина между точками составит 21 условную единицу. Но нам нужно найти кратчайший путь, для этого построим дерево, где укажем все возможные пути (рис.1)

рис. 1

Поскольку путь A → B → C = 7 меньше A → C = 9, дальше в сторону C мы не идем, продолжаем путь через B. Когда доходим до C, у нас есть три пути – сразу в Z, через D и через F. Путь A → B → C → Z = 27, а это больше, чем прямая дорога А → Z – не подходит. A → B → C → F → Z = 20, уже лучше, но нужно рассмотреть последний вариант: A → B → C → В → E → Z = 17. Это самый короткий путь, его и выбираем.

В ответе пишем: 17.

Решение 2 прототипа

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

Уже по табличке мы видим, что это так: если проведем диагональ по закрашенным клеточкам, половинки таблицы не будут симметричными.

Рисуем дерево в соответствии с задачей (рис. 2)

рис. 2

Поскольку по условию курьеру нужно посетить не менее 6 пунктов, пути A → Z, A → C → E → F → Z, A → C → D → F → Z и A → B → D → F → Z нам не подходят. Остается шесть дорог. Самый короткий путь – A → B → D → E → F → Z = 22.

В ответе пишем: 22.

Решение 3 прототипа

В этой задаче есть и таблица, и граф.

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

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

Чтобы решить эту задачу, для начала нужно определить степени каждой вершины – кол-во дорог, выходящих из одной точки. Степень может быть нулевой в том случае, если к ней не ведут никакие дороги. Таким образом, получается

Степень вершины А – 2, Б – 2, В – 5, Г – 3, Д – 2, Е – 4, К – 2.

Теперь сверяемся с табличкой: П1 – 2, П2 – 3, П3 – 2, П4 – 4, П5 – 2, П6 – 5, П7 – 2.

На графе проставляем уникальные пункты (те, степени которых не повторяются), у нас таких три – П2, П4 и П6.

Так как у остальных вершин степени одинаковые, мы не можем так же легко определить пункты, которым они соответствуют. Смотрим на то, с какими пунктами связаны уже определенные вершины. Так, к К идут две известные нам дороги – из П4 и П2. В эти две точки есть двухдорожный путь только от П1, поэтому делаем вывод, что К = П1.

Переходим к следующему пункту, который связан с известными нам точками – Д. Ищем двухдорожный пункт, который ведет в В (П6) и Е (П4). Он единственный – П7, то есть Д = П7.

Разобраться с вершинами А и Б невозможно, поскольку они обе имеют 2 степень и связаны только друг с другом и с В. Но нам это и не нужно, так как по условию задачи важно определить длину кратчайшего пути между пунктами В и К, а они нам уже известны. Рисуем дерево и прописываем все значения между точками (рис. 4)

рис. 4

Подсчитав все возможные расстояния, мы получаем такой результат. Самый короткий путь из В в К – 45.

В ответе пишем: 45.

Решение 4 прототипа

Рассмотрим задачу, где не нужно ничего считать. В ответе надо будет прописать последовательность букв с графа в зависимости от того, каким пунктам они соответствуют.

Как и в предыдущей задаче, сначала определяем степени вершин: А – 3, Б – 4, В – 3, Г – 4, Д – 5, Е – 3, Ж – 2. Уникальные степени у Д и Ж – можно определить, каким пунктам они соответствуют: Д = П2, Ж = П7. Так как Ж связана с Д и Е, а по таблице – с П2 и П4, то Е = П4. Точка Е связана с Б, Д и Ж, из них мы не знаем только одну: Б = П3. Остался только один четырехдорожный пункт – П6 = Г. Точка А связана с Б, В и Г = П5, а из В можно попасть в А, Г и Д = П1.

Что у нас получилось?
П1 = В, П2 = Д, П3 = Б, П4 = Е, П5 = А, П6 = Г, П7 = Ж.

В ответе пишем: ВДБЕАГЖ

Решение 5 прототипа

Мы имеем дело симметричным графом, соответственно не так-то легко будет сопоставить вершины с пунктами в таблице, чтобы решить задачу.

Но у нас есть один козырь – точка Д – единственная имеет степень 5, поэтому соответствует пункту 8.

Еще один момент, который может помочь нам, упоминается в условии: мы знаем, что отрезок ЗЕ = 15 км, поэтому ищем в таблице пункт с тремя дорогами, одна из которых ведет в П8 (Д). Это П3.

Чтобы узнать, где Е, надо посмотреть на строчку / столбик П3 и найти значение 15 – П2. А = П4, так как она связана с Е (П2), а остальные пункты, в которые можно попасть из Е, мы уже определили.

Ж = П7, поскольку из трех точек, связанных с З (П3), она осталась единственной.

Теперь узнаем Б: так как Ж (П7) имеет дороги к Д (П8), З (П3) и к Б, то Б = П6, а Г = П1, потому что у Б всего две дороги, одну из которых мы уже определили.

Таким образом, Б → Г = 17. Так и запишем в ответе.