Задание 1. Информационные модели (графы и таблицы) — теория и разбор

В задании №1 ЕГЭ по информатике часто встречается тип, где нужно сопоставить схему дорог (граф) с таблицей, в которой закодированы связи между пунктами. Обычно даётся рисунок с вершинами, обозначенными буквами (A, B, C, …), и таблица с номерами (1, 2, 3, …), где на пересечении строки и столбца стоит 1 (или звёздочка), если дорога есть, и 0 (или пусто) — если нет. Требуется определить, какой номер в таблице соответствует конкретному пункту на схеме, например, пунктам A и F.

Что нужно знать

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

Таблица смежности — квадратная таблица, в которой строки и столбцы соответствуют вершинам. Если между вершинами i и j есть ребро, то на пересечении (i, j) и (j, i) стоит 1 (или звёздочка). Таблица всегда симметрична относительно главной диагонали.

Почему степени помогают? При любом перенумеровании вершин степень каждой вершины сохраняется. Поэтому мы можем:

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

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

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

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

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

Правило: если степени двух вершин совпадают, сравнивайте наборы их соседей — они должны совпадать с наборами соседей соответствующих номеров в таблице.

Разбор примера

В нашем примере граф имеет следующие связи:

• A соединена с B, C, D;
• B соединена с A, C, E;
• C соединена с A, B, D, E;
• D соединена с A, C, F;
• E соединена с B, C, F;
• F соединена с D, E.

Соответствие между буквами и номерами в таблице задано так (это типичное реальное задание):
A → 3, B → 4, C → 2, D → 5, E → 6, F → 1.

Тогда таблица смежности выглядит следующим образом (строки и столбцы упорядочены по номерам 1…6):

Как думать.

1. Считаем степени вершин на схеме:

   • A: соединена с B, C, D → степень 3.
   • B: с A, C, E → степень 3.
   • C: с A, B, D, E → степень 4.
   • D: с A, C, F → степень 3.
   • E: с B, C, F → степень 3.
   • F: с D, E → степень 2.

2. Считаем степени строк в таблице (количество единиц в каждой строке):

   • строка 1: единицы на пересечении с 5 и 6 → степень 2.
   • строка 2: единицы с 3, 4, 5, 6 → степень 4.
   • строка 3: единицы с 2, 4, 5 → степень 3.
   • строка 4: единицы с 2, 3, 6 → степень 3.
   • строка 5: единицы с 1, 2, 3 → степень 3.
   • строка 6: единицы с 1, 2, 4 → степень 3.

3. Сопоставляем по уникальным степеням:

   • Степень 2 имеет только вершина F на схеме и строка 1 в таблице → F = 1.
   • Степень 4 имеет только вершина C на схеме и строка 2 в таблице → C = 2.

4. Разбираемся с вершинами степени 3:
   Остались A, B, D, E (все степень 3) и строки 3, 4, 5, 6. Теперь смотрим на соседей.

   • Вершина A соединена с B, C, D. В таблице C уже соответствует номеру 2. Значит, строка для A должна иметь единицы с номерами B, 2 и D.
     Проверим строку 3: у неё единицы с 2, 4, 5. Если A = 3, то её соседи — 2 (C), 4 (B) и 5 (D) — всё сходится. Значит, A = 3.
     (Можно проверить и другие: строка 4 имеет соседей 2,3,6 — это соответствовало бы B, если B=4, и т.д., но для ответа нам нужно только A и F.)

5. Записываем ответ:
   Пункт A соответствует номеру 3, пункт F — номеру 1.

Ответ: A = 3, F = 1 (в некоторых вариантах просят записать числа без пробелов, например, «31» или в порядке, указанном в условии).

Данный пример взят из реального экзаменационного варианта (задание №1 из варианта 12345). Все числа и структура графа соответствуют оригинальному условию.