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

Решение.
Рисунок и таблица описывают одни и те же дороги. Буквенные обозначения нельзя сопоставлять номерам по положению на рисунке: нужно сохранить связи между пунктами. Пустая клетка означает отсутствие прямой дороги.
Степень вершины — число выходящих из неё дорог. На рисунке: A — 2, B — 3, C — 2, D — 2, E — 2, F — 5, G — 2.
В таблице степени равны: 1 — 2, 2 — 3, 3 — 2, 4 — 5, 5 — 2, 6 — 2, 7 — 2.
Сопоставлять можно только вершины одинаковой степени. Затем сравниваем, с какими группами вершин связаны их соседи; если наборы различаются, соответствие исключаем. Повторяем уточнение, пока группы перестанут делиться.
Уточнение 1: A ∈ {5, 6}; B ∈ {2}; C ∈ {5, 6}; D ∈ {1, 7}; E ∈ {1, 7}; F ∈ {4}; G ∈ {3}.
Уточнение 2: A ∈ {5, 6}; B ∈ {2}; C ∈ {5, 6}; D ∈ {1, 7}; E ∈ {1, 7}; F ∈ {4}; G ∈ {3}.
Внутри оставшихся групп перебираем взаимно однозначные соответствия. Всего вариантов: 4. Для каждого проверяем все пары пунктов: и наличие дороги, и её отсутствие должны совпадать.
Подходит: A=5, B=2, C=6, D=1, E=7, F=4, G=3.
Подходит: A=6, B=2, C=5, D=1, E=7, F=4, G=3.
Подходит: A=5, B=2, C=6, D=7, E=1, F=4, G=3.
Подходит: A=6, B=2, C=5, D=7, E=1, F=4, G=3.
Для соответствия 1: D — номер 1, E — номер 7.
Для соответствия 2: D — номер 1, E — номер 7.
Для соответствия 3: D — номер 7, E — номер 1.
Для соответствия 4: D — номер 7, E — номер 1.
По условию номера записываем в порядке возрастания, независимо от порядка букв. После упорядочения в каждом допустимом случае получается 17.
Проверка первого допустимого соответствия по всем дорогам рисунка: GE → 3–7; EF → 7–4; FD → 4–1; DG → 1–3; FA → 4–5; AB → 5–2; BC → 2–6; CF → 6–4; FB → 4–2.
Все перечисленные клетки непусты, а число дорог в таблице равно числу рёбер рисунка. Значит, лишних связей не появилось. Остальные варианты либо прошли ту же проверку, либо исключены указанным противоречием.
Ответ: 17.