Прямой метод вычисления циклов ячеек карты блока простого планарного графа | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/7

Предлагаемый алгоритм вычисления циклов ячеек карты блока графа простого планарного является расширением классического алгоритма поиска в глубину циклов DFS-базиса. Ключевой идеей модификации алгоритма является стратегия правого обхода при прохождении графа в глубину. Начальной вершиной при правом обходе назначается вершина с минимальной координатой по оси OY. Выход из начальной вершины выполняется по ребру с минимальным полярным углом. Продолжение обхода из каждой следующей вершины осуществляется по ребру с минимальным полярным углом относительно ребра, по которому пришли в текущую вершину. Вводится двухуровневая структура вложенности циклов - основной и нулевой уровни вложенности. Все циклы базиса относятся к основному уровню. Каждый из циклов может иметь и нулевой уровень вложенности в другом основном для него цикле, если он вложен в него и не вложен ни в какой другой цикл из основного цикла. При правом обходе циклы нулевой вложенности являются смежными основному циклу и не имеют между собой общих вершин вне основного цикла. Указанные два свойства позволили в каждом цикле базиса последовательно выделить и исключить из него все циклы нулевой вложенности, применяя операцию симметрической разности. Показано, что оставшаяся часть базисного цикла является циклом ячейки карты блока. Сложность каждого шага алгоритма не превышает квадратичной относительно числа вершин планарного графа.
  • Title Прямой метод вычисления циклов ячеек карты блока простого планарного графа
  • Headline Прямой метод вычисления циклов ячеек карты блока простого планарного графа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 58
  • Date:
  • DOI 10.17223/20710410/58/7
Ключевые слова
циклы планарного графа, циклы блока графа, планарный граф
Авторы
Ссылки
Оре О. Теория графов. М.: Наука, 1980. 336 с.
Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989. 478с.
Welch J. A mechanical analysis of the cyclic structure of undirected linear graphs //j. Assoc.Comput. Mech. 1966. V. 13. P. 205-210.
Gibbs N. W. A cycle generation algorithm for finite undirected linear graphs //j. Assoc.Comput. Mech. 1969. V. 16. P. 564-568.
Tarjan R. Enumeration of the elementary circuits of a directed graph // SIAM J.Comput. 1973. V. 2. P.211-216.
Jonson D. B. Finding all the elementary circuits of a directed graph // SIAM J.Comput. 1975. V. 4. P.77-84.
Mateti P. and Deo N. On algorithms for enumerating all circuits of a graph // SIAM J.Comput. 1976. V. 5. No.1. P.90-99.
Tarjan R. Depth-first search linear graph algorithms // SIAM J.Comput. 1972. V. 1. P. 146-160.
Mahdi F., Safar M., and Mahdi K. Detecting cycles in graphs using parallel capabilities of GPU // Digital Inform.Commun. Techn. Appl. (DISTAP). 2011. V. 167. P.193-205.
Kavitha T., Mehlhorn K., and Michail D. New approximation algorithms for minimum cycle bases of graphs //j. Algorithmica. 2011. V. 59. No.4. P.471-488.
Pfaltz J. L. Chordless cycles in networks // IEEE 29th Intern. Conf. ICDEW. 2013. P. 223-228.
Иванов Б. Н. Генерация циклов ячеек карты простого планарного графа // Вычислительные методы и программирование. 2014. №15. С. 304-316.
Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Структуры. Н. Новгород: Изд-во ННГУ, 2005. 307c.
Paton K. An algorithm for finding a fundamental set of cycles of a graph // Comm. ACM. 1969. V. 12. No. 9. P.514-518.
Рейнголд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 476 с.
 Прямой метод вычисления циклов ячеек карты блока простого планарного графа | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/7
Прямой метод вычисления циклов ячеек карты блока простого планарного графа | Прикладная дискретная математика. 2022. № 58. DOI: 10.17223/20710410/58/7