Разбор задания №1 ЕГЭ по информатике: Сопоставление графа и таблицы (матрицы смежности)

Задание №1 в ЕГЭ по информатике проверяет умение анализировать графическую и табличную форму представления информации, сопоставлять схемы дорог (графы) с весовыми матрицами и извлекать из них числовые данные.
Это базовое задание первой части экзамена, за которое даётся 1 первичный балл. Решается оно за 2–3 минуты при помощи аккуратного подсчёта степеней вершин и анализа их окружения.

1. Теоретический фундамент: что нужно знать

Вся задача строится на понятии графа:

• Вершина графа — это населённый пункт (на схеме обозначается буквами: А, Б, В… или латиницей: A, B, C…).
  
• Ребро графа — это дорога, соединяющая два пункта.
  
• Степень вершины (валентность) — это количество дорог, которые выходят из данной вершины.
  
• Весовая таблица (матрица смежности) — таблица, в которой строки и столбцы соответствуют пунктам, а на их пересечении стоят либо звёздочки * (наличие дороги), либо числа (длина дороги в километрах).
  

Главное свойство:

Таблица и граф описывают одну и ту же схему дорог, но вершины в таблице перепутаны и названы номерами (1, 2, 3… или П1, П2, П3…). Наша цель — однозначно сопоставить каждую букву графа с соответствующим номером в таблице.

2. Универсальный пошаговый алгоритм решения

1. Посчитайте степени всех вершин на схеме графа:
   
   • Подпишите рядом с каждой буквой количество входящих в неё дорог (например: A (2 дороги), B (5 дорог), C (3 дороги)).
     
2. Посчитайте количество дорог для каждого пункта в таблице:
   
   • Сосчитайте количество заполненных ячеек в каждой строке таблицы и запишите полученные числа рядом со строками.
     
3. Найдите уникальные вершины:
   
   • Если на графе есть только одна вершина со степенью 5, а в таблице только одна строка с 5 дорогами — они гарантированно соответствуют друг другу.
     
4. Анализируйте окружение («соседей»):
   
   • Если несколько вершин имеют одинаковую степень (например, три вершины со степенью 2), посмотрите, с какими пунктами они соединены. Соседи у них всегда различаются по своим степеням.
     
5. Внимательно прочитайте вопрос задания:
   
   • Что требуется записать в ответ: длину конкретной дороги (число) или номера пунктов в порядке возрастания (например, 25)?
     

3. Разбор типовых примеров из банка КИМ ЕГЭ

Пример 1. Определение номеров населённых пунктов (невесовой граф)

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

Определите номера населённых пунктов A и G в таблице. В ответе запишите числа в порядке возрастания без разделителей.

Пошаговое решение:

Шаг 1. Считаем степени вершин по графу:

• B — соединена с D, C, E, A, G → степень 5.
  
• D — соединена с C, E, B → степень 3.
  
• C, E — каждая соединена с D и B → степень 2 (соединены с вершиной степени 3 и вершиной степени 5).
  
• A, G — соединены между собой и с B → степень 2 (соединены друг с другом и с вершиной степени 5).
  

Шаг 2. Считаем количество звёздочек в строках таблицы:

• Строка 1: 2 дороги (соседи: 2, 4)
  
• Строка 2: 3 дороги (соседи: 1, 4, 6)
  
• Строка 3: 2 дороги (соседи: 4, 5)
  
• Строка 4: 5 дорог (соседи: 1, 2, 3, 5, 6)
  
• Строка 5: 2 дороги (соседи: 3, 4)
  
• Строка 6: 2 дороги (соседи: 2, 4)
  

Шаг 3. Сопоставляем вершины:

1. Вершина степени 5 всего одна — это B. Значит, B = 4.
   
2. Вершина степени 3 всего одна — это D (строка 2, соединена с 1, 4, 6). Значит, D = 2.
   
3. Посмотрим на строки 3 и 5:
   
   • Пункт 3 соединён с пунктом 5 и пунктом 4 (B).
     
   • Пункт 5 соединён с пунктом 3 и пунктом 4 (B).
     
   • Они соединены друг с другом и с B (пункт 4). Ровно так же на графе устроена пара A и G!
     
4. Значит, пунктам A и G соответствуют номера 3 и 5.
   

По условию требуется записать числа в порядке возрастания без пробелов: 35.
Ответ: 35

Пример 2. Поиск длины дороги во взвешенном графе

Условие:Схема дорог изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах):

Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число.

Пошаговое решение:

Шаг 1. Определяем степени вершин на графе:

• Вершина Е соединена с 5 пунктами (Д, В, Г, К, Б/П6) → степень 5.
  
• Вершина В соединена с 4 пунктами (А, Б, Г, Е) → степень 4.
  
• Вершина Б соединена с 3 пунктами (А, В, Д) → степень 3.
  
• Вершины А, Д, Г, К → имеют степень 2 или 3.
  

Шаг 2. Определяем количество дорог по таблице:

• П1 — 2 дороги
  
• П2 — 3 дороги
  
• П3 — 2 дороги
  
• П4 — 4 дороги
  
• П5 — 2 дороги
  
• П6 — 5 дорог
  
• П7 — 2 дороги
  

Шаг 3. Находим нужные пункты:

1. Пункт со степенью 5 в таблице ровно один — это П6. Значит, Е = П6.
   
2. Пункт со степенью 4 в таблице ровно один — это П4. Значит, В = П4.
   
3. Нам требуется найти длину дороги между пунктами В и Е, то есть между П4 и П6.
   
4. Смотрим на пересечение строки П4 и столбца П6 (или строки П6 и столбца П4): на пересечении стоит число 20.
   

Ответ: 20

Пример 3. Граф с симметрией: как не запутаться

Иногда граф имеет ось симметрии (например, левая и правая ветки выглядят абсолютно одинаково). В таких задачах:

• Невозможно точно сказать, какой именно номер соответствует левой вершине, а какой — правой.
  
• Это не ошибка! В вопросе всегда спрашивают либо:
  
  1. Длину дороги, которая одинакова для обоих симметричных вариантов.
     
  2. Номера пунктов в порядке возрастания (например, «номера пунктов А и Г» — ответом будет 14 независимо от того, кто из них 1, а кто 4).
     
  3. Сумму длин дорог.
     

4. Распространённые ловушки и частые ошибки

1. Ошибки при подсчёте степеней:
   
   • Пропуск ребра на сложном графе — самая частая причина неверного решения. Всегда пересчитывайте общее количество рёбер: сумма степеней всех вершин, делённая на 2, должна строго равняться числу дорог в таблице.
     
2. Невнимательное чтение вопроса:
   
   • Если просят записать длину дороги, а ученик пишет номера пунктов (например, 46 вместо 20), балл будет потерян.
     
3. Игнорирование степеней «соседей»:
   
   • Если у вас есть две вершины степени 3, не угадывайте их наугад. Посмотрите на их соседей: одна может быть соединена с вершинами со степенями (2, 2, 4), а другая — с (2, 3, 5). Это даёт 100% однозначность.

Памятка для ученика

┌─────────────────────────────────────────────────────────────┐
│              ЧЕК-ЛИСТ ДЛЯ ЗАДАНИЯ №1 ЕГЭ                    │
├─────────────────────────────────────────────────────────────┤
│ 1. Подписать степени всех вершин на рисунке графа.          │
│ 2. Посчитать число дорог в каждой строке таблицы.           │
│ 3. Сопоставить уникальные вершины (с редкими степенями).    │
│ 4. Для одинаковых степеней проанализировать соседей.        │
│ 5. Перечитать вопрос: длина дороги или номера пунктов?      │
│ 6. Проверить порядок записи (по возрастанию / без пробелов).│
└─────────────────────────────────────────────────────────────┘