Исследование эффективности силовых алгоритмов визуализации непланарных графов

Abstract

Задача визуализации непланарных графов с помощью силовых алгоритмов является актуальной в настоящее время. Алгоритмы визуализации графов используются во многих областях. Цель данной выпускной квалификационной работы магистра состоит в исследовании эффективности уже существующих силовых алгоритмов визуализации графов и анализе получаемых укладок в зависимости от характеристик графов. Были выбраны эстетические критерии оценки полученных изображений укладок для алгоритмов Идеса, Фрюхтермана-Рейнгольда и модифицированного алгоритма Идеса. Также был предложен критерий оценки полученных укладок, основанный на расстоянии между вершинами по графу. Для достижения поставленной цели была разработана программная реализация алгоритмов Идеса и Фрюхтермана-Рейнгольда, позволяющая получать укладки графов, а также возможностью наблюдения за ходом эксперимента в реальном времени. Предложены модификации, оптимизирующие вычисления. Предложена модификации алгоритма Идеса, позволяющая использовать дополнительную метрику для повыше