Эволюционный алгоритм проверки планарности графов (An evolutionary algorithm for checking the planarity of graphs)
ЭВОЛЮЦИОННЫЙ АЛГОРИТМ ДЛЯ ПРОВЕРКИ ПЛАНАРНОСТИ ГРАФОВ
Биданец Александр Владимирович
магистр (прикладная математика и информатика), преподаватель, онлайн-школа «Тетрика»,
РФ, г. Симферополь
AN EVOLUTIONARY ALGORITHM FOR CHECKING THE PLANARITY OF GRAPHS
АННОТАЦИЯ
В работе рассматривается приближенный алгоритм проверки планарности графов. В процессе работы алгоритма строится изображение графа c минимальным количеством пересечений рёбер. Алгоритм эффективно решает перечисленные задачи. Можно сделать обобщенный вывод о том, что эволюционный алгоритм эффективен для решения оптимизационных задач геометрии.
Вычислительная сложность алгоритма определяется как 
, где 
– количество итераций алгоритма, 
– размер популяции (задаётся пользователем), 
– количество рёбер графа.
Ключевые слова: граф, планарность, визуализация графа, алгоритмы на графах, эволюционный алгоритм.
Введение
Для решения прикладных задач, например, при создании систем автоматизации проектирования плоских конструктивов (в частности, при проектировании интегральных схем), а также для визуализации различных производственных задач, необходимо решать задачу проверки графа на планарность и строить изображение планарного графа.[1]
Эволюционный алгоритм проще в реализации, чем любой другой классический алгоритм проверки планарности графа.
Будем рассматривать неориентированные графы без петель и кратных рёбер.
Определение. Неориентированным графом 
называется пара 
, где 
– множество вершин, а 
– множество рёбер.
Определение. Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра геометрически не пересекаются. Граф, изоморфный плоскому графу, называется планарным. [2]
Эволюционный алгоритм
Эволюционный алгоритм строит изображение графа с минимальным числом пересечений рёбер.
К недостаткам алгоритма можно отнести его асимптотическую сложность. Однако, на практике алгоритм находит оптимальное решение достаточно быстро.
К преимуществам данного алгоритма относятся простота реализации и возможность построения изображения планарного графа.
Описание эволюционного алгоритма
Кодирование решения
Каждая особь популяции представляет собой изображение (список координат вершин) графа на плоскости.
Инициализация
Координаты вершин графа на изображениях генерируются случайно в пределах диапазона, заданного пользователем.
Fitness-функция
Fitness-функция определяется как количество пересечений рёбер графа на изображении.
Стратегия отбора
Выполним сортировку особей текущей и предыдущей популяций. Выберем 50% лучших особей из каждой.
Оператор скрещивания
Случайным образом выбираем два рисунка G1, G2 из популяции. Для каждой пары соответствующих вершин G1[i], G2[i] выполняем процесс скрещивания координат. Формула скрещивания координат:
; 
, где 
(1)
В процессе скрещивания координат случайным образом выбирается одно из 3-х направлений скрещивания:
1) 
;
2) 
3) 
;
Оператор мутации
Случайно выбираем любую вершину графа и изменяем её координаты случайным образом (в пределах заданной области).
Рисунок 1. Результат работы программы
Рисунок 2. Результат работы программы
Заключение
Эволюционный алгоритм хорошо решает задачу проверки планарности графа, а также задачу построения рисунка графа с минимальным пересечением рёбер. Можно сделать обобщенный вывод о том, что эволюционные алгоритмы хорошо работают для решения оптимизационных задач геометрии.
Список литературы:
- Проверка планарности графа. — Текст : электронный // Справочник от Автор 24 : [сайт]. — URL: https://spravochnick.ru/informatika/proverka_planarnosti_grafa/ (дата обращения: 20.06.2023). https://ru.wikipedia.org/wiki/Планарный_граф
- Нина, Костюкова Проверка планарности графа / Костюкова Нина. — Текст : электронный // Курс: "Графы и их применение". Лекция 3: Представления о планарном графе : [сайт]. — URL: https://intuit.ru/studies/courses/58/58/info (дата обращения: 20.06.2023).