Задание 1. Информатика. ЕГЭ. Статград. Профиль. 12.05.2025-1

Python

from itertools import permutations

graph = {'А': set('БГД'),
         'Б': set('АВД'),
         'В': set('БЕ'),
         'Г': set('АЖ'),
         'Д': set('АБЕЖИ'),
         'Е': set('ВДК'),
         'Ж': set('ГДИ'),
         'И': set('ДЖК'),
         'К': set('ИЕ')}
templ = {1: [3, 8],
         2: [6, 7, 9],
         3: [1, 7, 9],
         4: [5, 6],
         5: [4, 8, 9],
         6: [2, 4, 9],
         7: [2, 3],
         8: [1, 5, 9],
         9: [2, 3, 5, 6, 8]}

for p in permutations('АБВГДЕЖИК'):
    chk = {p[k-1]: set([p[i-1] for i in v]) for k, v in templ.items()}
    if chk == graph:
        print('1 2 3 4 5 6 7 8 9')
        print(*p)

Вывод программы

1 2 3 4 5 6 7 8 9
В И Е Г А Ж К Б Д
1 2 3 4 5 6 7 8 9
К Б Е Г Ж А В И Д

В первом случае дорога ВЕ — это дорога между пунктами \(1\) и \(3\), а ДИ — между пунктами \(2\) и \(9.\) Сумма протяжённостей этих дорог \(12 + 11 = 23.\) Этот случай не подходит. Во втором случае дорога ВЕ — это дорога между пунктами \(3\) и \(7,\) а ДИ — между \(8\) и \(9.\) Сумма их протяжённостей \(14 + 10 = 24.\) В этом случае дорога между А и Б — это дорога между пунктами 2 и 6. Протяжённость этой дороги \(8.\)

Ответ: \(8\)