Современные информационные технологии / 2. Вычислительная техника и программирование

Перекопская Мадлена Евгеньевна

Студентка ОСПНАУ Славянского колледжа Национального авиационного университета

Практическое применение теории графов: решение транспортных задач

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

Так, к типовым задачам теории графов относятся:

· задача о кратчайшей цепи (замена оборудования, составление расписания движения транспортных средств, размещение пунктов скорой помощи, размещение телефонных станций);

· задача об упаковках и покрытиях (оптимизация структуры ПЗУ, размещение диспетчерских пунктов городской транспортной сети);

· связность графов и сетей (проектирование кратчайшей коммуникационной сети, синтез структурно-надежной сети циркуляционной связи, анализ надежности стохастических сетей связи) [1].

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

Так, множество всех дорог города или района составляет дорожную сеть. Транспортная сеть − это совокупность дорог региона, пригодных для движения заданных транспортных средств. Транспортная сеть всегда является частным случаем дорожной сети и, как правило, строится для различных типов транспортных средств: легковые автомобили, грузовые полной массой до 3,5 т и т.д. Модель транспортной сети может быть представлена в виде графа.

Для моделирования транспортной сети необходимо иметь:

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

· сведения о размещении основных грузообразующих (ГОП) и грузопоглощающих организаций (ГПП);

· дополнительные сведения из коммунальных и дорожных организаций в виде перечня улиц с характеристикой их проезжей части;

· сведения по организации уличного движения, т.е. схемы организации движения на перекрестках, площадях и транспортных развязках, а также сведения о различных ограничениях движения, связанные с установленными дорожными знаками [3].

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

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

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

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

Литература:

1) Мельников О.И. Занимательные задачи по теории графов / О.И. Мельников. − Минск: ТетраСистемс, 2001. − 144 с.

2) Харари Ф. Теория графов / Ф. Харари / [Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова] − М.: Едиториал УРСС, 2003. − 296 с.

3) Зыков А. А. Основы теории графов / А.А. Зыков. − М.: «Вузовская книга», 2004. − С. 664.

4) Кормен Т. Х. Алгоритмы для работы с графами / Т. Х. Кормен − М.: Вильямс, 2006. − С. 1296.