|
Вычислительные методы и программирование, 2014, том 15, выпуск 2, страницы 304–316
(Mi vmp250)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Генерация циклов ячеек карты простого планарного графа
Б. Н. Иванов Дальневосточный федеральный университет
Аннотация:
Рассматривается конструктивный метод генерации циклов ячеек (chordless cycles) карты простого планарного графа. Циклы ячеек карты представляются как линейные комбинации циклов {DFS-базиса}. Искомые линейные комбинации строятся явно на основе выделенных свойств структуры вложенности циклов базиса и циклов ячеек карты графа. Карта планарного графа позволила отойти от общепринятого подхода генерации циклов и явно внести геометрию карты в структуру алгоритма. На множестве циклов базиса определяется отношение соседства, которое порождает корневые деревья структуры вложенности циклов. Ячейки карты графа являются результатом обхода данного множества корневых деревьев. Сложность предложенного алгоритма является кубической относительно числа вершин в графе. Рассматривается приложение алгоритма в рамках решения задач на планарном подразбиении.
Ключевые слова:
генерация циклов, перечисление циклов, базис циклов, карта графа, вложенность циклов, фундаментальные циклы.
Поступила в редакцию: 05.04.2014
Образец цитирования:
Б. Н. Иванов, “Генерация циклов ячеек карты простого планарного графа”, Выч. мет. программирование, 15:2 (2014), 304–316
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmp250 https://www.mathnet.ru/rus/vmp/v15/i2/p304
|
Статистика просмотров: |
Страница аннотации: | 189 | PDF полного текста: | 117 |
|