Есть на карте в районе Дмитрова одно интересное место. В широкой пойме реки Яхрома, недалеко от её впадения в Сестру человеком создан настоящий лабиринт из каналов, дренажных канав, а также всевозможных дорог - асфальтовых, грейдерных, грунтовых... Причём дороги и перекрёстки образуют затейливый рисунок, напомнивший мне лекции по дискретной математике и теории графов.

Вот и родилась идея - а что, если взять, да и проехать по этому лабиринту так, чтобы посетить все дороги, причём каждую всего один раз?

Собираюсь в воскресенье эту задумку реализовать. Если вдруг кто-нибудь захочет составить компанию - поехали. (На велосипедах, разумеется.)

Качаем здесь проектный трек и точки мероприятия. Подробности внутри...

Постановка задачи

Имеем сеть дорог. Перекрёстки будут служить вершинами (узлами) графа, а дороги - его дугами (рёбрами). Заглянув в справочники по дискре, вспоминаем, что путь в графе, проходящий через все его дуги, причем по каждой всего один раз, называется Эйлеров путь. (А если он, вдобавок, замкнут, то это уже Эйлеров цикл.)

Значит, надо просто представить дорожную сеть в виде графа и найти в нём эйлеров путь! Благо, реализаций алгоритма поиска - хоть отбавляй.

Решение задачи

Но вот беда. Не всякий граф является эйлеровым. Чтобы в неориентированном графе существовал эйлеров цикл, нужно, чтобы для каждой из вершин число входящих в вершину дуг было чётным. (Кстати, эйлеров путь допускает две вершины с нечетным числом входящих дуг, но тогда закольцевать маршрут не получится, что не очень удобно в нашей ситуации.)

Проблему, очевидно, составляют Т-образные перекрёстки, которые образованы тремя дорогами (нечётное число). К счастью, таких мест на карте не слишком много. А в тех местах, где посещения T-перекрёстков не избежать, пришлось искуственно вводить в граф дополнительные дублирующие рёбра, что на практике означает проезд по одному и тому же участку дважды. Я тем не менее постарался свести дублирование к минимуму. В итоге на маршруте будет всего 5 двойных участков суммарной длиной порядка 5 км. Что при общей длине маршрута в 130 км составляет менее 4%

Итак, граф разработан.

Вот его модель

Вводим модель в программу, расчитываем цикл и выписываем последовательность проезда по дорогам.Дело за малым - взять и проехать! ;)

Что за дороги

Дороги, образующие сеть в Яхромской пойме, самые разные. Есть протяжённые участки хорошего асфальта, но преимущественно это будут грейдеры и полевые грунтовки для проезда сельхозтехники. Многие из них идут вдоль каналов и русел рек Старой и Новой Яхромы и их притоков. Так что время от времени будет возможность при желании искупаться. (А на такой жаре оно, уверяю, появится...)

Бродов и переплывов через водные преграды не предполагается, маршрут специально проложен с использованием многочисленных мостов.

Из достопримов - бескрайние просторы, ровные дороги до горизонта, капустные поля, поливалки, какой-то древний монастырь в п. Луговой, чудом сохранившийся благодаря объекту ПВО островок леса... В общем, что-нибудь интересное обязательно встретится.

Подробности

PS: сразу договоримся - покатушка преследует чисто спортивный интерес. Неготовых целый день крутиться под палящим солнцем по одним и тем же унылым полям непонятно ради чего заранее прошу не беспокоиться и поскорее самостоятельно организовать какую-нибудь классную лесную покатушку по красивым дорожкам мимо лесных озёр ;)

Буду рад участию тех, кому идея кажется интересной. Камон!