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

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