E-catalog        

Библиогр.: 15 назв.

Предлагаемый алгоритм вычисления циклов ячеек карты блока графа простого планарного является расширением классического алгоритма поиска в глубину циклов DFS-базиса. Ключевой идеей модификации алгоритма является стратегия правого обхода при прохождении графа в глубину. Начальной вершиной при правом обходе назначается вершина с минимальной координатой по оси OY. Выход из начальной вершины выполняется по ребру с минимальным полярным углом. Продолжение обхода из каждой следующей вершины осуществляется по ребру с минимальным полярным углом относительно ребра, по которому пришли в текущую вершину. Вводится двухуровневая структура вложенности циклов — основной и нулевой уровни вложенности. Все циклы базиса относятся к основному уровню. Каждый из циклов может иметь и нулевой уровень вложенности в другом основном для него цикле, если он вложен в него и не вложен ни в какой другой цикл из основного цикла. При правом обходе циклы нулевой вложенности являются смежными основному циклу и не имеют между собой общих вершин вне основного цикла. Указанные два свойства позволили в каждом цикле базиса последовательно выделить и исключить из него все циклы нулевой вложенности, применяя операцию симметрической разности. Показано, что оставшаяся часть базисного цикла является циклом ячейки карты блока. Сложность каждого шага алгоритма не превышает квадратичной относительно числа вершин планарного графа.