Задание 1: Графы и таблицы. Справка

Задания: https://ya.cc/8kSTNE

Типы заданий

Тип 1: Сопоставление графа и таблицы

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

Особенности:

• Граф и таблица созданы независимо
• Нумерация в таблице не связана с буквами на графе
• Нужно найти соответствие между буквами и номерами

Тип 2: Определение длины дорог

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

Особенности:

• В таблице указаны длины дорог между пунктами
• Могут быть дополнительные условия (например, "длина дороги АГ больше, чем длина дороги ВГ")
• Нужно найти длину конкретной дороги

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

Шаг 1: Анализ графа

1. Определить степени вершин (количество рёбер, выходящих из каждой вершины)
2. Найти вершины с одинаковыми степенями: они могут соответствовать одинаковым номерам в таблице
3. Проанализировать структуру графа:
   • Изолированные вершины (степень 0)
   • Вершины степени 1 (концевые точки)
   • Вершины степени 2 (промежуточные)
   • Вершины степени 3 и более (узлы)

Шаг 2: Анализ таблицы

1. Подсчитать количество дорог для каждого пункта (аналог степени вершины)
2. Сопоставить степени вершин графа с количеством дорог в таблице
3. Использовать дополнительные условия (если есть)

Шаг 3: Сопоставление

1. Начать с уникальных вершин: Вершины с уникальной степенью легче всего сопоставить Например, если в графе есть вершина степени 5, а в таблице только один пункт с 5 дорогами
2. Использовать связи между вершинами: Если вершина А соединена с вершинами Б, В, Г, то соответствующий номер должен иметь дороги к тем же пунктам
3. Проверить дополнительные условия: Если дано условие типа "длина дороги АГ больше, чем длина дороги ВГ", использовать его для уточнения

Шаг 4: Проверка

1. Проверить все связи: Убедиться, что все рёбра графа соответствуют звёздочкам (или длинам) в таблице Проверить, что отсутствующие рёбра в графе соответствуют пустым ячейкам в таблице
2. Проверить дополнительные условия (если есть)

Пример решения

Дано: Граф с вершинами А, Б, В, Г, Д, Е, К и таблица с номерами 1-7. Нужно найти, какой номер соответствует Б.

1. Подсчитываем степени вершин в графе.
   1. У нас симметричный граф, поэтому вершин с максимальным количеством ребер несколько.
   2. В данном случае 4 вершины, каждая с 3 ребрами (дорогами).
2. Подсчитываем количество дорог для каждого номера в таблице.
   1. 3 дороги имеют пункты: П2, П4, П6, П7.
3. Сопоставляем уникальные значения.
   1. Начнем с вершины К.
   2. Видим, что он соединен с вершинами Е (2 ребра), А (2 ребра) и Б (3 ребра).
4. Используем связи для уточнения.
   1. Ищем в таблице пункт, который имеет 3 связи с другими пунктами, а другие пункты имеют по 2 связи (ребра), 2 связи и 3 связи.
   2. Рассмотрим пункт П2. У его связей П3, П4 и П6 количество связей 2, 3 и 3 соответственно. Нам нужно 2, 2 и 3. Не подходит.
   3. Рассмотрим пункт П4. Он имеет связи с П2 (3), П3 (2) и П5 (2). Отлично, нам подходит. Значит, вершина К это П4.
5. Проверяем результат
   1. Сопоставляем остальные вершины с пунктами, используя таблицу и количество связей.
   2. К - П4

Видео с решением

![[N1-video.mp4]]

Составлено: Лилия С.
Источники: КИМ ЕГЭ 2026, открытый банк ФИПИ, спецификация ЕГЭ по информатике, яндекс учебник

Удачи на экзамене! 🎓