Задание 1 ЕГЭ: таблица без весов: номера пунктов

Граф и таблица без весов: номера пунктов. Тема номера — граф и таблица дорог. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой (*) отмечено наличие дороги между населёнными пунктами. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует его номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать пунктам A и F на схеме. В ответе запишите эти два номера в порядке возрастания без разделителей.

Решение

Степени вершин на графе: A — 2, B — 1, C — 2, D — 3, E — 2, F — 4, G — 2; в таблице: 1 — 2, 2 — 2, 3 — 4, 4 — 2, 5 — 1, 6 — 2, 7 — 3. Сначала сопоставляем пункты с уникальными степенями, затем остальные — по соседям. Пунктам A и F соответствуют номера 3 и 6.

Ответ: 36.

from itertools import permutations

graph = ["AD", "AF", "BF", "CF", "CG", "DE", "DF", "EG"]      # рёбра по рисунку
table = [(1, 2), (1, 3), (2, 4), (3, 5), (3, 6), (3, 7), (4, 7), (6, 7)]
roads = {frozenset(e) for e in table}
answers = set()
for p in permutations(range(1, 8)):
    num = dict(zip("ABCDEFG", p))
    if {frozenset((num[x], num[y])) for x, y in graph} == roads:
        answers.add(''.join(map(str, sorted((num['A'], num['F'])))))
print(*answers)

Решить такую задачу — новый вариант с проверкой