На рисунке схема дорог N-ского района изображена в виде графа, в таблице звёздочкой обозначено наличие дороги из одного населённого пункта в другой. Отсутствие звёздочки означает, что такой дороги нет.
Каждому населённому пункту на схеме соответствует номер в таблице, но неизвестно, какой именно номер. Определите, какие номера населённых пунктов в таблице могут соответствовать населённым пунктам C и E на схеме. В ответе запишите эти два номера в возрастающем порядке без пробелов и знаков препинания.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | ⁎ | ⁎ | |||||
| П2 | ⁎ | ⁎ | ⁎ | ||||
| П3 | ⁎ | ⁎ | |||||
| П4 | ⁎ | ⁎ | ⁎ | ||||
| П5 | ⁎ | ⁎ | ⁎ | ||||
| П6 | ⁎ | ⁎ | |||||
| П7 | ⁎ | ⁎ | ⁎ | ||||
На схеме имеется 3 населенных пункта степени 2 и 4 населенных пункта степени 3. У населенных пунктов D и A есть дороги с двумя пунктами степени 2 и одним пунктом степени 3. У населенных пунктов E и C общие дороги с двумя пунктами степени 3 и одним пунктом степени 2. По таблице находим, что пункты П2 и П4 (оба степени 3) имеют общие дороги с двумя пунктами степени 3 и одним пунктом степени 2, следовательно, это и есть пункты E и С.
Ответ: 24.
Приведём решение Юрия Красильникова на языке Python.
def алфавит(s): return ''.join(sorted(set(s.replace(' ',''))))
# алфавит - строка из символов строки s в алфавитном порядке (кроме пробела)
def дуги(s): return set(map(алфавит,s.split()))
# дуги - множество дуг графа (пар символов), каждая пара упорядочена по алфавиту
таблица = '14 15 23 24 27 37 45 56 67' # дуги по таблице
граф ='AB AC AF BC CE DE DF DG EG' # дуги по схеме
# Не надо бояться включить одну дугу дважды (напр., БД и ДБ). Главное - ничего не пропустить.
print(алфавит(таблица)) # заголовок
from itertools import permutations
for p in permutations(алфавит(граф)): # все возможные перестановки буквенных обозначений
табтранс = str.maketrans(''.join(p),алфавит(таблица)) # таблица трансляции
if дуги(таблица) == дуги(граф.translate(табтранс)): # если множества дуг совпадают
print(''.join(p),'CE'.translate(табтранс))