📋 Условие
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H.
🔍 Подробное решение
На рисунке схема дорог N‑ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта G в пункт E и из пункта F в пункт H. В ответе запишите целое число.
Решение:
Граф симметричный (линия симметрии будет проходить H, F, E, G — середина CA). Определяем уникальные точки. У нас есть уникальная точка H, она имеет пересечение с тремя двойками. Смотрим горизонталь в таблице там, где тройки, чтобы вертикальные пересечения были двойки. Далее по уникальности не найдём какие-то точки. Пойдём от противного, не будем искать пересечения, а будем искать ту точку, которая не пересекается. Мы уже нашли точку H, она пересекается с тремя двойками, а с точкой Е не пересекается. Найдём её — это будет 2. Из этой информации по таблице получаем, что G — это 1, а F — это 7. Будем использовать свойство уникальности и просто подберём точку, и потом уже от неё будем подбирать остальные. Если мы знаем, что G — 1, то она пересекается с А и С. Нам без разницы, какое значение брать для этих точек. Возьмём любую, допустим А — 5, тогда по связи найдём D — это будет 3, остальные точки: C — 8 и B — 4.
Теперь найдём ответ для задачи. GE и FH (а теперь посмотрите на граф и поймёте, что остальные точки можно было не искать, поэтому всегда смотрите, что нужно найти, а потом уже решайте):
- GE — пункты 1, 2 — смотрим пересечение в таблице — 15
- FH — 6, 7 — 37
Складываем и получаем: 15 + 37 = 52
Ответ: 52
Решение:
Граф симметричный (линия симметрии будет проходить H, F, E, G — середина CA). Определяем уникальные точки. У нас есть уникальная точка H, она имеет пересечение с тремя двойками. Смотрим горизонталь в таблице там, где тройки, чтобы вертикальные пересечения были двойки. Далее по уникальности не найдём какие-то точки. Пойдём от противного, не будем искать пересечения, а будем искать ту точку, которая не пересекается. Мы уже нашли точку H, она пересекается с тремя двойками, а с точкой Е не пересекается. Найдём её — это будет 2. Из этой информации по таблице получаем, что G — это 1, а F — это 7. Будем использовать свойство уникальности и просто подберём точку, и потом уже от неё будем подбирать остальные. Если мы знаем, что G — 1, то она пересекается с А и С. Нам без разницы, какое значение брать для этих точек. Возьмём любую, допустим А — 5, тогда по связи найдём D — это будет 3, остальные точки: C — 8 и B — 4.
Теперь найдём ответ для задачи. GE и FH (а теперь посмотрите на граф и поймёте, что остальные точки можно было не искать, поэтому всегда смотрите, что нужно найти, а потом уже решайте):
- GE — пункты 1, 2 — смотрим пересечение в таблице — 15
- FH — 6, 7 — 37
Складываем и получаем: 15 + 37 = 52
Ответ: 52
📚 Теория
Задача на соответствие графа и таблицы. Ключевой приём — использование перестановок для автоматического перебора всех вариантов соответствия.
🐍 Шаблон Python
Python
from itertools import *
# Тут пишем связи из таблицы (построчно)
a = '478 38 256 15 34 37 168 127'.split()
# Тут пишем связи из графа (в любом порядке)
s = 'DE DG GC GA BC FB FE FH BH AH'.split()
print('1 2 3 4 5 6 7 8') # кол-во столбцов
for p in permutations('AHBCFEDG'): # меняем на буквы/цифры из задания
if all(str(p.index(y) + 1) in a[p.index(x)] for x, y in s):
print(*p)