Задание 1 ЕГЭ: весовая матрица и граф

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

Пример

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

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта B в пункт G и из пункта B в пункт A.

В ответе запишите целое число.

Решение

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

Сначала сопоставляем пункты с редкими степенями, затем уточняем по соседям: у соответствующих пунктов должны совпадать и степени соседей. Для нужных пунктов получаем: A — пункт 2; B — пункт 4; G — пункт 5.

Дорога B–G — клетка «4–5», 53 км; дорога B–A — клетка «2–4», 23 км. Сумма равна 76.

Ответ: 76.

Проверить себя можно перебором всех соответствий «буква → номер пункта»: подходят те, при которых множества дорог совпадают.

from itertools import permutations

graph = ["AB", "BD", "BF", "BG", "CD", "CE", "DF", "DG", "EG"]      # рёбра по рисунку
table = {(1, 4): 4, (1, 5): 42, (1, 6): 20, (1, 7): 39, (2, 4): 23, (3, 5): 58, (3, 6): 22, (4, 5): 53, (4, 7): 46}
roads = {frozenset(k): w for k, w in table.items()}

answers = set()
for p in permutations(range(1, 8)):
    num = dict(zip("ABCDEFG", p))                  # буква -> номер пункта
    if {frozenset((num[a], num[b])) for a, b in graph} == set(roads):
        ws = [roads[frozenset((num[a], num[b]))] for a, b in ["BG", "BA"]]
        answers.add(sum(ws))
print(*answers)               # одно число — ответ определён однозначно

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