Задание 1: Анализ информационных моделей

Типичная формулировка: «На рисунке схема дорог изображена в виде графа, в таблице звёздочкой обозначено наличие дороги между населёнными пунктами... Так как таблицу и схему рисовали независимо друг от друга, нумерация в таблице не связана с обозначениями на графе. Определите номера населённых пунктов A и G (или Б и В)». Ответ — одна или несколько цифр, записанных в порядке возрастания без пробелов и разделителей. Задание относится к части 1, оценивается в 1 балл, проверяется строго автоматически: любое отклонение в порядке или формате ответа засчитывается как ошибка.

• Граф — набор вершин и рёбер между ними; в этих задачах вершины — населённые пункты, рёбра — дороги.
• Степень вершины $\deg(v)$ — количество рёбер, выходящих из вершины (сколько дорог ведёт из пункта).
• Таблица (матрица) смежности — симметричная таблица, где на пересечении строки $i$ и столбца $j$ звёздочка означает наличие ребра между $i$ и $j$; диагональ всегда пустая (петель нет).
• Степень пункта в таблице равна числу звёздочек в его строке, и оно же равно числу звёздочек в его столбце: $\deg(i) = \sum_j a_{ij} = \sum_j a_{ji}$.
• Лемма о рукопожатиях: сумма степеней всех вершин равна удвоенному числу рёбер: $\sum_{i} \deg(v_i) = 2|E|$. Это удобно для проверки — сумма звёздочек по всем строкам всегда чётная.
• Изоморфизм графов — взаимно однозначное соответствие вершин двух графов, при котором смежность сохраняется: если вершины связаны в одном графе, их образы связаны и в другом.
• Инвариант — свойство, сохраняющееся при изоморфизме: степень вершины, число вершин с данной степенью, наличие треугольника (три вершины, попарно связанные рёбрами), расстояние между вершинами.
• Если степени двух вершин одинаковы, для их различения используют инвариант второго порядка — набор степеней их соседей.
• Если после всех проверок остаётся несколько допустимых перестановок вершин — соответствие неоднозначное; но конкретная пара вершин из вопроса может при этом совпадать во всех допустимых вариантах, тогда её всё равно можно указать в ответе.

1. По рисунку выписать степень каждой вершины графа (посчитать число линий у каждой точки).
2. По таблице посчитать степень каждого пункта — сумма звёздочек в строке.
3. Сравнить полученные наборы чисел: они должны совпадать (это самопроверка правильности подсчёта).
4. Найти вершины и пункты с уникальной (неповторяющейся) степенью — сопоставить их сразу.
5. Для вершин с повторяющейся степенью сравнить степени их соседей с соседями пунктов такой же степени в таблице.
6. Если после шага 5 все совпадения однозначны — соответствие построено полностью.
7. Если остаются несколько допустимых вариантов, проверить, не совпадают ли искомые в вопросе вершины во всех этих вариантах — если да, их можно указать в ответе без полного построения соответствия.
8. Проверить ответ подстановкой всех рёбер графа в таблицу. …