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

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

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

Название статьи, аннотация и ключевые слова на английском языке

  • Иванов Б.Н. – Дальневосточный федеральный университет, Школа естественных наук, ул. Суханова, 8, 690091, г. Владивосток; доцент, e-mail: ibn8826@mail.ru