На рисунке схема дорог изображена в виде графа, в таблице звёздочкой отмечено наличие дороги между двумя населёнными пунктами. Так как таблицу и схему рисовали независимо друг от друга, нумерация пунктов в таблице никак не связана с буквенными обозначениями на графе. Кроме того, при заполнении таблицы одну дорогу случайно пропустили. Определите два населённых пункта, дорога между которыми есть на графе, но не отмечена в таблице. В ответе запишите номера этих пунктов в таблице в порядке возрастания, без разделителей между ними, как двузначное число. Например, если бы в таблице была пропущена дорога между пунктами П1 и П2, в ответе следовало бы написать число 12.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | П8 | |
| П1 | ⁎ | ⁎ | ⁎ | |||||
| П2 | ⁎ | ⁎ | ||||||
| П3 | ⁎ | ⁎ | ||||||
| П4 | ⁎ | ⁎ | ⁎ | |||||
| П5 | ⁎ | ⁎ | ⁎ | ⁎ | ||||
| П6 | ⁎ | ⁎ | ||||||
| П7 | ⁎ | ⁎ | ⁎ | ⁎ | ⁎ | |||
| П8 | ⁎ | ⁎ | ⁎ | |||||
На рисунке есть один пункт степени 6 - И. В таблице есть пункт степени 5, это пункт П7, следовательно, это и есть населенный пункт И у которого пропущена одна дорога. На графике есть два пункта (Е и Б) степени 4, а в таблице такой пункт только один. Следовательно, пропущена одна из двух дорог И-Е или И-Б. На графике есть два пункта степени 2 имеющие общие дороги с пунктом И, это пункты П2 и П3. Следовательно, пункт В это пункт П6. Так как пункт Е единственный пункт степени 4 имеющий общие дороги с двумя пунктами степени 2, то это пункт П4. Так как в таблице у пункта П4 только 3 дороги, следовательно, пропущена дорога И-Е, П4-П7. Ответ 47.
Ответ: 47.
Приведём решение Юрия Красильникова на языке Python.
def алфавит(s): return ''.join(sorted(set(s.replace(' ',''))))
# алфавит - строка из символов строки s в алфавитном порядке (кроме пробела)
def дуги(s): return set(map(алфавит,s.split()))
# дуги - множество дуг графа (пар символов), каждая пара упорядочена по алфавиту
таблица = '12 17 18 27 34 37 45 46 56 57 58 78' # дуги по таблице
граф ='АБ АГ АИ БВ БЕ БИ ВЕ ГЖ ГИ ЕИ ЕК ЖИ ИК' # дуги по схеме
# Не надо бояться включить одну дугу дважды (напр., БД и ДБ). Главное - ничего не пропустить.
print(алфавит(таблица)) # заголовок
from itertools import permutations
for p in permutations(алфавит(граф)): # все возможные перестановки буквенных обозначений
табтранс = str.maketrans(''.join(p),алфавит(таблица)) # таблица трансляции
if дуги(таблица) <= дуги(граф.translate(табтранс)): # если все дуги таблицы содержатся в графе
print(''.join(p))
print(дуги(граф.translate(табтранс)) - дуги(таблица)) # недостающая в таблице дуга