XIII Международная студенческая научная конференция Студенческий научный форум - 2021

Язык математики всегда ценился своей точностью и лаконичностью. При этом для лучшего его понимания в математике широко применяются наглядные методы решения. Графическое представление (граф) это может сделать в полной мере, также данный метод является многовариантным, что дает возможность выбрать наиболее оптимальный вариант, подходящий под условие, что в том числе и обуславливает важность изучения теории графов. Данный метод имеет большой потенциал для его применения в практических задачах разного характера: от игровых математических, до задач прикладного характера из других сфер жизнедеятельности человека.

Цель нашего исследования: научиться видеть граф в условии задачи и рассмотреть возможность применения теории графов при решении практических задач в других сферах деятельности человека.

Результаты. Рассмотренные первой части работы задачи были форматизированны, то есть мы построили их математические модели при помощи графов, что дало возможность, пользуясь логикой схожих умозаключений, прийти к общим решениям как схожих задач, так и различных.

Теорию графов можно применять не только в теоретических задачах (т.е. исключительно в рамках изучения науки математики), но и в бытовых ситуациях, которые касаются разных сфер жизнедеятельности человека, например, хозяйственной ([1]; [2] и др.). Мы рассматривали вариант применения теории графов в практической (хозяйственной) деятельности на примере решения задачи по оптимизации работы служб жилищно-коммунального хозяйства города по уборке снега.

Погодные условия, характерные для нашего региона, каждый год ставят перед жилищно-коммунальными службами города проблему уборки снега. В связи с состоянием автопарка жилищно-коммунальных служб, со сложностями с горюче-смазочными материалами, нехваткой кадров в данной сфере актуальной является задача оптимизации деятельности данного направления хозяйствования коммунальных служб города. Одной из форм такой оптимизации может быть составление оптимальной схемы движения снегоуборочных машин на определенном участке города, что мы и попробуем сделать при помощи метода графов. Для этого возьмем карту Восточных кварталов города Луганска, где обозначена транспортная развязка (см. Рис. 1 ).

Рис. 1. Транспортная развязка улиц Восточных кварталов г. Луганска

Теперь изобразим эту карту схематически, используя метод графов (на местах пересечения дорог у нас будут располагаться вершины графа, следовательно, сами дороги — ребра графа, см. Рис.2.).

Рис.2. Графическое изображение транспортной развязки

Так как нам нужно составить схему по оптимизации движения снегоуборочных машин, это означает, что нам необходимо составить такой маршрут, по которому одна машина должна проехать по каждой дороге только 1 раз (что решит вопрос экономии топлива и рабочего времени). По Эйлеру (цит. по [3]), если ровно две вершины графа нечётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом нужно начинать с одной из нечётных вершин и завершить его в другой. В получившемся графе есть 2 нечетные вершины. Следовательно, можно составить схему движения снегоуборочных машин так, чтобы они не проезжали дважды по одной дороге. Исходя из этого и полученного рисунка можно сделать вывод, что начинать движение нужно в точке А1 и закончить в А10, или же наоборот. Но, т.к. мы составляем задачу для построения маршрута с учетом инфраструктуры города, то нужно учитывать то, что начинать движение в точке А10 будет проблематично, следовательно начинаем движение из точки А1. Построенный маршрут выглядит следующим образом: А1-А6-А7-А15-А10-А19-А16-А12-А17-А4-А12-А11-А18-А5-А4-А3-А2-А6-А9-А5-А2-А13-А1-А14-А7-А8-А19-А11-А9-А8-А10 (см рис 3.).

Рис.3. Маршрут движения снегоуборочной машины

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

Еще одним допустимым может быть маршрут: А1-А13-А2-А5-А9-А6-А2-А3-А4-А12-А11-А18-А5-А4-А17-А12-А16-А19-А10-А8-А19-А11-А9-А8-А7-А14-А1-А6-А7-А15-А10. Или же: А1-А14-А7-А8-А19-А11-А9-А8-А10-А15-А7-А6-А1-А13-А2-А5-А9-А6-А2-А3-А4-А12-А11-А18-А5-А4-А17-А12-А16-А19-А10. Путь, который проходит снегоуборочная машина можно назвать периметром этого графа, а т.к. в обоих случаях построения маршрута по каждой дороге эта машина проезжает один раз, то эти периметры равны. Значит, с точки зрения математики, неважно, какой из этих путей выбирать (здесь уже надо ориентироваться на другие параметры, например, расположение тех самых жилищно-коммунальных участков города).

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Березина Л.Ю. Графы и их применения/ Л.Ю. Березина. – М.: Просвещение, 1979. – 143с.

Берж К. Теория графов и ее применения/ К. Берж. – М.: Иностранная литература, 1958.

Зыков А.А. Основы теории графов/ А.А. Зыков. - М.: Вузовская книга, 2001. – 664 с.