RUS  ENG
Полная версия
ЖУРНАЛЫ // Вычислительные методы и программирование // Архив

Выч. мет. программирование, 2014, том 15, выпуск 2, страницы 304–316 (Mi vmp250)

Эта публикация цитируется в 1 статье

Генерация циклов ячеек карты простого планарного графа

Б. Н. Иванов

Дальневосточный федеральный университет

Аннотация: Рассматривается конструктивный метод генерации циклов ячеек (chordless cycles) карты простого планарного графа. Циклы ячеек карты представляются как линейные комбинации циклов {DFS-базиса}. Искомые линейные комбинации строятся явно на основе выделенных свойств структуры вложенности циклов базиса и циклов ячеек карты графа. Карта планарного графа позволила отойти от общепринятого подхода генерации циклов и явно внести геометрию карты в структуру алгоритма. На множестве циклов базиса определяется отношение соседства, которое порождает корневые деревья структуры вложенности циклов. Ячейки карты графа являются результатом обхода данного множества корневых деревьев. Сложность предложенного алгоритма является кубической относительно числа вершин в графе. Рассматривается приложение алгоритма в рамках решения задач на планарном подразбиении.

Ключевые слова: генерация циклов, перечисление циклов, базис циклов, карта графа, вложенность циклов, фундаментальные циклы.

УДК: 519.17:519.6

Поступила в редакцию: 05.04.2014



© МИАН, 2024