Симметричный граф: На рисунке схема дорог N-ского района; 27, 32, 11, 9 · ЕГЭ №1

Подсчитаем степени вершин, то есть число дорог из каждого пункта. На схеме: степень 2 — у A, D, E и H; степень 3 — у B, C, F и G. В таблице: степень 2 — у П2, П4, П7 и П8; степень 3 — у П1, П3, П5 и П6.
F — единственная вершина степени 3, соседи которой имеют степени 2, 2 и 2; в таблице так устроен только П5. Значит, F соответствует П5. A — единственная вершина степени 2, не связанная с F; в таблице с П5 не связан только П8. Значит, A соответствует П8. B — единственная вершина степени 3, связанная с A; в таблице из П8 ведёт дорога только в одну вершину степени 3 — П3. Значит, B соответствует П3. H — единственная вершина степени 2, связанная с A; в таблице из П8 ведёт дорога только в одну вершину степени 2 — П4. Значит, H соответствует П4.
Тогда дорога B–A — это дорога П3–П8 длиной 42, а дорога H–A — это дорога П4–П8 длиной 27. Сумма: 42 + 27 = 69.

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

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

from itertools import *
t = '367 56 168 58 247 123 15 34'
s = 'BH GCA BCE GF EDH FA GBD CF'
s = {frozenset(x) for x in s.split()}
for p in permutations('ABCDEFGH'):
    a = t
    for x, y in zip('12345678', 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 8')
        print(*p)
        break