Прямой метод вычисления циклов ячеек карты блока простого планарного графа

doi:10.17223/20710410/58/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Прямой метод вычисления циклов ячеек карты блока простого планарного графа	753 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/58/7

#циклы планарного графа

#циклы блока графа

#графы планарные

Title: Прямой метод вычисления циклов ячеек карты блока простого планарного графа
Title: A direct method for calculating cell cycles of a block map of a simple planar graph
Creator: Иванов, Борис Николаевич (математик)
Date: 2022
DOI: 10.17223/20710410/58/7
Description: Предлагаемый алгоритм вычисления циклов ячеек карты блока графа простого планарного является расширением классического алгоритма поиска в глубину циклов DFS-базиса. Ключевой идеей модификации алгоритма является стратегия правого обхода при прохождении графа в глубину. Начальной вершиной при правом обходе назначается вершина с минимальной координатой по оси OY. Выход из начальной вершины выполняется по ребру с минимальным полярным углом. Продолжение обхода из каждой следующей вершины осуществляется по ребру с минимальным полярным углом относительно ребра, по которому пришли в текущую вершину. Вводится двухуровневая структура вложенности циклов — основной и нулевой уровни вложенности. Все циклы базиса относятся к основному уровню. Каждый из циклов может иметь и нулевой уровень вложенности в другом основном для него цикле, если он вложен в него и не вложен ни в какой другой цикл из основного цикла. При правом обходе циклы нулевой вложенности являются смежными основному циклу и не имеют между собой общих вершин вне основного цикла. Указанные два свойства позволили в каждом цикле базиса последовательно выделить и исключить из него все циклы нулевой вложенности, применяя операцию симметрической разности. Показано, что оставшаяся часть базисного цикла является циклом ячейки карты блока. Сложность каждого шага алгоритма не превышает квадратичной относительно числа вершин планарного графа.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2022. № 58. С. 69-83
Language: rus

Created: 08-12-2022

368 Visitors

200 Hits

171 Downloads

Журналы ТГУ Прямой метод вычисления циклов ячеек карты блока простого планарного графа