На рисунке изображена схема дорог N-ского района. В таблице...

Задание:

На рисунке изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.

Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера в таблице могут соответствовать населённым пунктам E и F на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.

Решение (аналитическое)

Заметим, что граф симметричный. Ось симметрии можно провести следующим образом

Населенные пункты E и F расположены относительно симметрично относительно проведенной оси. Начнем восстанавливать вершины парами. Вершины A и B имеют степень 2 (пункты 2 и 6), с ними связаны С со степенью 6 (пункт 1) и D/G со степенью 3 (пункты 4 и 7). Оставшаяся пара вершин соответствует пунктам 3 и 5.

Ответ: 35

Решение (программное - python)

# зададим граф, как наборы вершин и смежных с ними вершин
# ACG – вершина A и смежные с ней C и G
b_str = 'ACG BDC CABDEFG DBCE ECDF FCEG GACF'
# зададим таблицу аналогичным способом
# 217 – пункт 2 и смежные с ним 1 и 7
d_str = '1234567 217 3157 4156 5134 614 7123'
# записываем информацию о графе в словарь
# вершина: смежные вершины
b_graph = {w[0]: set(w[1:]) for w in b_str.split()}
from itertools import permutations
# определяем все вершины
letters = 'ABCDEFG'
print(letters)

# перебираем все перестановки номеров
for perm in permutations('1234567'):
    # преобразуем цифровое представление в буквенное
    new_dstr = d_str
    # заменяя цифры на буквы (первую на 1, вторую на 2 ...)
    for old_d, new_b in zip(perm, letters):
        new_dstr = new_dstr.replace(old_d, new_b)
        # формируем словарь для измененной строки
        new_graph = {w[0]: set(w[1:]) for w in new_dstr.split()}
        # если совпадает с начальным словарем с буквами
        if new_graph == b_graph:
            # выводим перестановку
            print(''.join(perm)) 

Программа выводит следующие строки:

ABCDEFG
2614537
6217354 

Заметим, что вершинам E и F соответствуют пункты 3 и 5 (либо 5 и 3).

Ответ: 35

Источник: Информатика с Джобсом | ЕГЭ