Задание EGEINF6C5E0F: Графы, таблицы и маршруты

Решение.
Рисунок и таблица описывают одни и те же дороги. Буквенные обозначения нельзя сопоставлять номерам по положению на рисунке: нужно сохранить связи между пунктами. Пустая клетка означает отсутствие прямой дороги.
Степень вершины — число выходящих из неё дорог. На рисунке: A — 2, B — 3, C — 2, D — 3, E — 3, F — 3.
В таблице степени равны: 1 — 3, 2 — 2, 3 — 3, 4 — 3, 5 — 3, 6 — 2.
Сопоставлять можно только вершины одинаковой степени. Затем сравниваем, с какими группами вершин связаны их соседи; если наборы различаются, соответствие исключаем. Повторяем уточнение, пока группы перестанут делиться.
Уточнение 1: A ∈ {2, 6}; B ∈ {3, 4}; C ∈ {2, 6}; D ∈ {5}; E ∈ {3, 4}; F ∈ {1}.
Уточнение 2: A ∈ {2, 6}; B ∈ {3, 4}; C ∈ {2, 6}; D ∈ {5}; E ∈ {3, 4}; F ∈ {1}.
Внутри оставшихся групп перебираем взаимно однозначные соответствия. Всего вариантов: 4. Для каждого проверяем все пары пунктов: и наличие дороги, и её отсутствие должны совпадать.
A=2, B=3, C=6, D=5, E=4, F=1: исключаем — на рисунке нет дороги A–B, а в клетке 2–3 отмечена дорога.
Подходит: A=2, B=4, C=6, D=5, E=3, F=1.
Подходит: A=6, B=3, C=2, D=5, E=4, F=1.
A=6, B=4, C=2, D=5, E=3, F=1: исключаем — на рисунке нет дороги A–B, а в клетке 6–4 отмечена дорога.
Для соответствия 1: E–A соответствует 3–2, длина 21; B–C соответствует 4–6, длина 5.
Сумма длин: 21 + 5 = 26.
Для соответствия 2: E–A соответствует 4–6, длина 5; B–C соответствует 3–2, длина 21.
Сумма длин: 5 + 21 = 26.
Во всех допустимых соответствиях искомая величина одинакова и равна 26. Наличие нескольких соответствий, если они есть, поэтому не создаёт неоднозначности ответа.
Проверка первого допустимого соответствия по всем дорогам рисунка: CF → 6–1; CB → 6–4; BE → 4–3; EA → 3–2; AF → 2–1; FD → 1–5; DB → 5–4; DE → 5–3.
Все перечисленные клетки непусты, а число дорог в таблице равно числу рёбер рисунка. Значит, лишних связей не появилось. Остальные варианты либо прошли ту же проверку, либо исключены указанным противоречием.
Ответ: 26.