Таблицы данных и их графовое представление

Зачем это в ЕГЭ.
Задание 1 ЕГЭ по информатике проверяет умение переводить табличное представление данных в графовую модель и вычислять характеристики графа. За верный ответ начисляется 1 первичный балл. Проверяется навык работы с матрицей смежности, степенями вершин и числом рёбер. Этот подтип (таблица → граф) встречается в 65–75 % реальных вариантов ФИПИ 2022–2025 годов.

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

Алгоритм (чеклист).
1. Выдели объекты из заголовков строк и столбцов — это вершины графа.
2. Проверь симметричность таблицы: если $a_{ij}=a_{ji}$ и диагональ нулевая — граф неориентированный без петель.
3. Построй матрицу смежности $A$ прямо по таблице ($a_{ij}=1$ при наличии связи).
4. Вычисли требуемую характеристику (степень, число рёбер и т.д.) по строкам или столбцам.
5. Нарисуй граф (по желанию) и пересчитай вручную для контроля.
6. Запиши ответ и сравни с вариантами (или проверь сумму степеней).

Опоры (кратко).
- Матрица смежности: $a_{ij}=\begin{cases}1,&\text{есть ребро }i\to j\\0,&\text{иначе}\end{cases}$
- Степень вершины в неориентированном графе: $d(v_i)=\sum_j a_{ij}$
- Число рёбер в неориентированном графе: $\frac{1}{2}\sum_i d(v_i)$
- В ориентированном графе: число дуг $=\sum_{i,j}a_{ij}$, $d_{\text{in}}(v_j)=\sum_i a_{ij}$, $d_{\text{out}}(v_i)=\sum_j a_{ij}$

Пример 1 (подтип «неориентированный граф»)
Дана таблица совместимости 5 участников проекта (А, Б, В, Г, Д): 1 — могут работать вместе, 0 — нет.

Задание: сколько участников имеют ровно двух партнёров?

Шаг 1. Вершины: А, Б, В, Г, Д.
Шаг 2. Таблица симметрична, диагональ нулевая → неориентированный граф без петель.
Шаг 3. Считаем степени:
$d(\text{А})=3$ (Б, В, Д),
$d(\text{Б})=2$ (А, Г),
$d(\text{В})=3$ (А, Г, Д),
$d(\text{Г})=2$ (Б, В),
$d(\text{Д})=2$ (А, В).
Шаг 4. Ровно два партнёра: Б, Г, Д → 3 участника.
Шаг 5. Проверка: сумма степеней = 12, число рёбер = 12/2 = 6 (совпадает с таблицей выше диагонали).

Пример 2 (подтип «ориентированный граф»)
Дана таблица направленных маршрутов между 4 станциями (1, 2, 3, 4): 1 — есть путь в одну сторону.

Задание: сколько станций имеют входящую степень ровно 1?

Шаг 1. Вершины: 1, 2, 3, 4. Таблица несимметрична → ориентированный граф.
Шаг 2. Считаем входящие степени по столбцам:
ст. 1: из 3 → $d_{\text{in}}=1$;
ст. 2: из 1 и 4 → $d_{\text{in}}=2$;
ст. 3: из 2 → $d_{\text{in}}=1$;
ст. 4: из 1 → $d_{\text{in}}=1$.
Шаг 3. Входящая степень 1: станции 1, 3, 4 → 3.
Шаг 4. Проверка: сумма входящих = 5, сумма исходящих = 5 (совпадает).

Типичные ошибки.
1. Забыл разделить сумму степеней на 2 — в неориентированном графе посчитал число рёбер равным сумме степеней вместо $\frac{1}{2}\sum d(v)$.
2. Перепутал строки и столбцы в ориентированном графе — вместо входящей степени посчитал исходящую (или наоборот).
3. Учёл единицы на главной диагонали как рёбра — хотя условие явно говорит об отсутствии петель.
4. Принял несимметричную таблицу за неориентированный граф — применил формулу $\frac{1}{2}\sum d(v)$ к ориентированному случаю.
5. Подсчитал количество вершин вместо требуемой характеристики — ответил «5», хотя спрашивали число вершин с определённой степенью.

Дальше.
Переходи к задачам на списки смежности, поиск путей и компоненты связности (задание 15).