Моделирование и обработка данных

Сопоставление таблицы и графа по степеням вершин

№ 1Обновлено 19.10.2026Версия 1

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

Идея

Таблица и граф описывают одну и ту же сеть, поэтому у соответствующих вершин совпадает всё, что не зависит от названия:

степень — число дорог, выходящих из пункта (число заполненных клеток в строке);
веса — длины дорог, выходящих из пункта;
соседи — через какие пункты пункт связан с другими.

Порядок действий

Посчитайте степени всех вершин графа и всех строк таблицы.
Вершины с уникальной степенью сопоставьте сразу.
Для остальных сравните длины выходящих дорог или посмотрите на соседей уже найденных вершин.
Проверьте результат: для каждой пары вершин длина дороги в таблице должна совпасть с длиной на схеме.

Пример

Граф: дороги A–B (4), A–C (6), B–C (3), C–D (7). Таблица:

	1	2	3	4
1		6	7	3
2	6			4
3	7
4	3	4

Степени в таблице: пункт 1 — три дороги, пункты 2 и 4 — по две, пункт 3 — одна. Степени в графе: C — 3, A и B — по 2, D — 1.

Уникальные степени: 1 = C, 3 = D.
Для A и B степени одинаковые. У A дорога к C длиной 6, у B — длиной 3. В таблице дорога от пункта 1 (то есть от C) к пункту 2 равна 6, а к пункту 4 равна 3. Значит, 2 = A, 4 = B.

Проверка: A–B = 4 в таблице на пересечении 2 и 4 (4) ✔, C–D = 7 на пересечении 1 и 3 (7) ✔.

Если спросят, например, сумму номеров пунктов A и D, ответ 2 + 3 = 5.

Программная проверка

Когда пунктов много, соответствие можно найти перебором всех перестановок и сверкой с таблицей:

from itertools import permutations

edges = {('A', 'B'): 4, ('A', 'C'): 6, ('B', 'C'): 3, ('C', 'D'): 7}
table = {(1, 2): 6, (1, 3): 7, (1, 4): 3, (2, 4): 4}

def key(a, b):
    return (a, b) if a < b else (b, a)

for p in permutations([1, 2, 3, 4]):
    m = dict(zip('ABCD', p))
    mapped = {key(m[a], m[b]): w for (a, b), w in edges.items()}
    if mapped == table:
        print(m)          # {'A': 2, 'B': 4, 'C': 1, 'D': 3}

Типичные ошибки

Считают степень по столбцу, но смотрят на строку другого пункта: таблица симметрична, пользуйтесь одной строкой.
Забывают, что пустая клетка означает «дороги нет», а не нулевую длину.
Сопоставляют по одной степени, не проверяя веса: при равных степенях ответ неоднозначен.
Не делают итоговую проверку по всем дорогам.

from itertools import permutations edges = {('A', 'B'): 4, ('A', 'C'): 6, ('B', 'C'): 3, ('C', 'D'): 7} table = {(1, 2): 6, (1, 3): 7, (1, 4): 3, (2, 4): 4} def key(a, b): return (a, b) if a < b else (b, a) for p in permutations([1, 2, 3, 4]): m = dict(zip('ABCD', p)) mapped = {key(m[a], m[b]): w for (a, b), w in edges.items()} if mapped == table: print(m) # {'A': 2, 'B': 4, 'C': 1, 'D': 3}