Тип 1 № 55797 
Анализ информационных моделей. Неоднозначное соотнесение таблицы и графа
i
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 |
| П1 | | | 3 | 4 | | 10 | |
| П2 | | | | | 9 | | 8 |
| П3 | 3 | | | 6 | | | |
| П4 | 4 | | 6 | | | | 7 |
| П5 | | 9 | | | | 11 | 8 |
| П6 | 10 | | | | 11 | | |
| П7 | | 8 | | 7 | 8 | | |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Д в пункт Е. В ответе запишите целое число — так, как оно указано в таблице.
Решение. Заметим, что в таблице имеется 3 пункта степени 2 (П2, П3, П6) и 4 пункта степени 3 (П1, П4, П5 и П7).
Населенный пункт П1 связан с двумя населенными пунктами степени 2 (П3, П6) и одним степени 3 (П4), следовательно, пункт П1 может быть или Б, или Г.
Населенный пункт П4 связан с двумя населенными пунктами степени 3 (П1, П7) и одним — степени 2 (П3), следовательно, пункт П4 может быть или Д, или Е.
Населенный пункт П5 связан с двумя населенными пунктами степени 2 (П2, П6) и одним — степени 3 (П7), следовательно, пункт П5 может быть или Б, или Г.
Населенный пункт П7 связан с двумя населенными пунктами степени 3 (П4, П5) и одним — степени 2 (П2), следовательно, пункт П7 может быть или Д, или Е.
Поскольку пунктам Д и Е соответствуют пункты П4 и П7, то расстояние между ними равно 7.
Ответ: 7.
Приведём решение Евгения Джобса (графическое).
Построим по таблице граф. Начнем с П1: есть дороги в П3, П4 и П7. И продолжим пристраивать граф от полученных вершин.
По построенному графу видно два треугольника, которые есть на графе из задания, которые соединены через пункты П4 и П7. Следовательно, это и есть города Д и Е.
Приведём решение Евгения Джобса на языке Python.
С помощью переборного алгоритма найдем все возможные соответствия вершинам графа пунктов из таблицы. Граф представим как строку, где подстроки, разделенные пробелом, будут представлять собой пункт (первый символ) и пункты, в которые можно из него попасть, — остальные символы.
from itertools import permutations
s = 'абд бавд вбг гвеж дабе егдж жег'
s_g = {c[0]:set(c[1:]) for c in s.split()}
s1 = '1346 257 314 4137 5267 615 7245'
print('1234567')
for x in permutations(set(s) - {' '}):
s2 = s1
for a1, a2 in zip('1234567', x):
s2 = s2.replace(a1, a2)
s2_g = {c[0]: set(c[1:]) for c in s2.split()}
if s2_g == s_g:
print(*x, sep='')
Получим вывод:
1234567
гажебвд
бжадгве
Пункты Д и Е — пункты 4 и 7 (или 7 и 4). Следовательно, ответ 7.
Ответ: 7
PDF-версии: