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

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