Задача
На рисунке схема дорог N-ского района изображена в виде графа, в таблице содержатся сведения о протяженности каждой из этих дорог (в километрах).
 |
 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяженности дорог из пункта Б в пункт В и из пункта Г в пункт Д. В ответе запишите целое число.
Решение (аналитическое)
Наше решение начнем с анализа схемы дорог (графа). Делаем следующие выводы:
- пункт К уникальный - единственный пункт с 6 дорогами;
- схема дорог симметрична.
Именно симметрия в данной задаче играет огромную роль.
Два крайних пункты схемы (А, Е) имеют по две дороги, остальные пункты (Б, В, Г, Д) - по три дороги. Эти факты не позволяют однозначно определить соответствие пункта на схеме и в таблице. Но...
Выбор соответствия пункта А и Е не имеет значения в связи с тем, что построение схемы сведется к тому, что она замкнется в месте симметрии, а те участки, длину которых необходимо найти, находятся по обе стороны оси симметрии.
Пусть пункт А - 1, Е - 3.
Пункт К - 5 (единственный с 6 дорогами).
Пункт А, пересекается с К, а также с Б. Пункт Е - с К и Д. Следовательно: Б - 2, Д - 4.
Пункты Б и Д, помимо пересечения с пунктом К, пересекаются: Б с В, Д с Г. Следовательно: В - 6, Г - 7.
Мы определили соответствие всех пунктов таблице. Теперь необходимо определить протяженность дорог из пункта Б в пункт В и из пункта Г в пункт Д.
Дорога из пункта Б в пункт В - 13, а из пункта Г в пункт Д - 7. Их сумма - 20.
Ответ: 20.
