Симметричный граф: На рисунке схема дорог N-ского района изображена; 7, 5, 6, 13 · ЕГЭ №1

Подсчитаем степени вершин, то есть число дорог из каждого пункта. На схеме: степень 2 — у А, Г и К; степень 3 — у Б, В, Д и Е. В таблице: степень 2 — у П1, П4 и П7; степень 3 — у П2, П3, П5 и П6.
А — единственная вершина степени 2, соседи которой имеют степени 3 и 3; в таблице так устроен только П7. Значит, А соответствует П7.
Вершины Б и Д на схеме неразличимы по уже известным признакам: обе степени 3, обе связаны с А, соседи каждой имеют степени 2, 3 и 3. В таблице так же устроены П2 и П3. Рассмотрим два варианта.
1. Пусть Б соответствует П2, а Д — П3. В — единственная оставшаяся вершина степени 3, связанная с Б; в таблице из П2 ведёт дорога только в одну оставшуюся вершину степени 3 — П5. Значит, В соответствует П5. Е — единственная оставшаяся вершина степени 3 (Б, В и Д уже найдены), в таблице это П6. Значит, Е соответствует П6.
2. Пусть Б соответствует П3, а Д — П2. В — единственная оставшаяся вершина степени 3, связанная с Б; в таблице из П3 ведёт дорога только в одну оставшуюся вершину степени 3 — П6. Значит, В соответствует П6. Е — единственная оставшаяся вершина степени 3 (Б, В и Д уже найдены), в таблице это П5. Значит, Е соответствует П5.
В 1-м варианте дорога Б–В — это дорога П2–П5 длиной 14, а дорога Д–Е — это дорога П3–П6 длиной 9; во 2-м варианте дорога Б–В — это дорога П3–П6 длиной 9, а дорога Д–Е — это дорога П2–П5 длиной 14. Ответ в обоих вариантах одинаковый. Сумма: 14 + 9 = 23.

$\textbf{Ответ: 23.}$

$\textbf{Решение через Python}$

from itertools import *
t = '45 357 267 16 126 345 23'
s = 'БД АДВ АБЕ БЕГ ДВК ЕГ ВК'
s = {frozenset(x) for x in s.split()}
for p in permutations('АБВГДЕК'):
    a = t
    for x, y in zip('1234567', p):
        a = a.replace(x,y)
    a = {frozenset(x) for x in a.split()}
    if s == a:
        print('1 2 3 4 5 6 7')
        print(*p)
        break