Статья Автор: Лебедев Дмитрий

Решаем задание 1

Решение задачи рассмотрим на примере задания демоверсии 2025 года

На рисунке схема дорог N-ского района изображена в виде графа,
в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице
никак не связана с буквенными обозначениями на графе.
Определите, какова сумма протяжённостей дорог из пункта D в пункт G и из пункта A в пункт C.

Для каждой вершины графа и таблицы определим её степень. Получим
Степень Вершины графа Вершины таблицы
2 A, B, E 2, 4, 7
3 C, D, F, G 1, 3, 5, 6

На основании этих данных ещё нельзя установить соответствие

Добавим к степени вершины степени смежных вершин. Получим
Степень вершины Степени смежны Вершины графа Вершины таблицы
2 3, 3 E 7
2 3, 2 A, B 2, 4
3 3, 3, 3 G 5
3 3, 3, 2 D, F 3, 6
3 3, 2, 2 C 1

Теперь видно, что появились "уникальные" вершины и можно установить соответствия
E=7; G=5; C=1
Так как вершина E соединена с вершинами C,F и вершина A соединена с вершиной C
можно утверждать, что F=3; A=4. Тогда B=2; D=6
 

Ответ==DG+AC=(6-5)+(4-1)=8+30=38

В некоторых заданиях однозначного соответствия может и не быть.
Тогда надо перебрать варианты и выбрать нужный
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать