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

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

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

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

from itertools import *
t = '23 135 124567 36 237 347 356'
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