The problem of visualization of a graph with a small number of nodes is considered and its implementation is developed, which allows using the procedure in the design of a transport network
graph, transport network, visualization
С развитием научно-технического прогресса тесно связано использование математических методов и средств вычислительной техники. Особую важность приобретает их использование при решении задач транспортного моделирования [1,2]. В связи с этим рассмотрим применение методов дискретной математики и ЭВМ на практике.
В настоящее время неуклонно растет интерес к дискретной математике: теории множеств, математической логике, комбинаторике, теории графов. Современные компьютерные технологии являются фундаментом для построения математического обеспечения информационно-технических систем.
Визуализация или отображение графа, как ответвление теории графов, относящееся к топологии и геометрии, — двумерное представление его на плоскости. В данном случае, это визуальное представление укладки графа транспортной сети на плоскость (как правило, допускается пересечение рёбер), направленное на удобное отображение некоторых свойств моделируемого объекта, рассмотренное вне контекста географического местоположения.
В работе для визуализации представления графа рассматривается случай небольшого количества узлов (от 4 до 20). Ввиду этого специализированные алгоритмы не применялись, производилось равномерное размещение узлов по кругу с определением необходимого радиуса.
Угол между узлами определялся по формуле:
(1)
где n – количество узлов.
Рисунок 1 - Решение задачи визуальной перегруженности графа.
Для решения задачи визуальной перегруженности графа и обеспечения эстетичности восприятия, радиус круга, по которому располагаются узлы, выбирается таким образом, чтобы ребра, соединяющие любые пары, не попадали на сам узел, исходя из этого радиус круга, должен удовлетворять условию:
(2)
где H – высота равнобедренного треугольника ABC; r – радиус узла; D - предельно допустимое расстояние между узлом и ребром графа.
(3)
(4)
Причем параметры r и D могут произвольно настраиваться в процессе построения для обеспечения наилучшей визуализации с учётом общего размера области, количества ребер и узлов графа. Исходными данными для построения может выступать матрица смежности или матрица расстояний между узлами.
Для графов большей размерности может быть рассмотрен силовой алгоритм укладки графа на плоскости, например алгоритм Фруштермана-Рейгольда (Frushterman-Reingold).
1. Kulakova I.M. Reshenie zadachi nailuchshego raspolozheniya transport-nogo terminala s opredeleniem geograficheskih koordinat /Kulakova I.M., Le-bedeva O.A., Poltavskaya Yu.O.// Sbornik nauchnyh trudov Angarskogo gosudarst-vennogo tehnicheskogo universiteta. 2020. T. 1. № 17. S. 38-42.
2. Lebedeva O.A. Modelirovanie gruzovyh perevozok v transportnoy se-ti // Lebedeva O.A., Kripak M.N./ Vestnik Angarskogo gosudarstvennogo tehni-cheskogo universiteta. 2016. № 10. S. 182-184.
