На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | 10 | ||||||
| П2 | 20 | ||||||
| П3 | 10 | 20 | 8 | ||||
| П4 | 8 | 15 | 12 | ||||
| П5 | 15 | ||||||
| П6 | 12 | 18 | |||||
| П7 | 18 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г.
ВНИМАНИЕ! Длины отрезков на схеме не отражают длины дорог.
1. Поскольку E — единственная вершина, из которой ведут 2 дороги, то ей соответствует П6.
2. Из Е можно добраться до Г, в то же время Г — одна из двух вершин, степень которой равна 3. Значит, Г соответствует П4.
3. Из П4 нужна дорога, которая приведет в пункт, откуда больше никуда нельзя добраться (так как другие 2 ребра из Г ведут в вершины, откуда еще можно добраться в другие вершины). Значит, путь из Г в Б соответствует пути из П4 в П5, а его длина — 15.
Ответ: 15.
Приведём решение Фёдора Мизюрёва на языке Python.
from itertools import permutations
def tren_ege_1zad():
routes = 'АВ ДВ ВГ ГБ ГЕ ЕК'
tab = [13, 23, 34, 45, 46, 67]
for perm in permutations('АБВГДЕК'):
temp = [perm[t // 10 - 1] + perm[t % 10 - 1] for t in tab]
if all([m in routes or m[::-1] in routes for m in temp]):
print(perm)
B_index = perm.index('Б')
C_index = perm.index('Г')
print(f"пункт Б на графике соответствует пункту П{B_index + 1} в таблице, а пункт Г на графике соответствует пункту П{C_index + 1} в таблице")
tren_ege_1zad()
По таблице находим расстояние между получившимися пунктами.