Рассмотрена задача визуализации графа с небольшим количеством узлов и разработана его реализация, которая позволяет использовать процедуру при проектировании транспортной сети
граф, транспортная сеть, визуализация
С развитием научно-технического прогресса тесно связано использование математических методов и средств вычислительной техники. Особую важность приобретает их использование при решении задач транспортного моделирования [1,2]. В связи с этим рассмотрим применение методов дискретной математики и ЭВМ на практике.
В настоящее время неуклонно растет интерес к дискретной математике: теории множеств, математической логике, комбинаторике, теории графов. Современные компьютерные технологии являются фундаментом для построения математического обеспечения информационно-технических систем.
Визуализация или отображение графа, как ответвление теории графов, относящееся к топологии и геометрии, — двумерное представление его на плоскости. В данном случае, это визуальное представление укладки графа транспортной сети на плоскость (как правило, допускается пересечение рёбер), направленное на удобное отображение некоторых свойств моделируемого объекта, рассмотренное вне контекста географического местоположения.
В работе для визуализации представления графа рассматривается случай небольшого количества узлов (от 4 до 20). Ввиду этого специализированные алгоритмы не применялись, производилось равномерное размещение узлов по кругу с определением необходимого радиуса.
Угол между узлами определялся по формуле:
(1)
где n – количество узлов.
Рисунок 1 - Решение задачи визуальной перегруженности графа.
Для решения задачи визуальной перегруженности графа и обеспечения эстетичности восприятия, радиус круга, по которому располагаются узлы, выбирается таким образом, чтобы ребра, соединяющие любые пары, не попадали на сам узел, исходя из этого радиус круга, должен удовлетворять условию:
(2)
где H – высота равнобедренного треугольника ABC; r – радиус узла; D - предельно допустимое расстояние между узлом и ребром графа.
(3)
(4)
Причем параметры r и D могут произвольно настраиваться в процессе построения для обеспечения наилучшей визуализации с учётом общего размера области, количества ребер и узлов графа. Исходными данными для построения может выступать матрица смежности или матрица расстояний между узлами.
Для графов большей размерности может быть рассмотрен силовой алгоритм укладки графа на плоскости, например алгоритм Фруштермана-Рейгольда (Frushterman-Reingold).
1. Кулакова И.М. Решение задачи наилучшего расположения транспорт-ного терминала с определением географических координат /Кулакова И.М., Ле-бедева О.А., Полтавская Ю.О.// Сборник научных трудов Ангарского государст-венного технического университета. 2020. Т. 1. № 17. С. 38-42.
2. Лебедева О.А. Моделирование грузовых перевозок в транспортной се-ти // Лебедева О.А., Крипак М.Н./ Вестник Ангарского государственного техни-ческого университета. 2016. № 10. С. 182-184.
