DOI: https://doi.org/10.26089/NumMet.v22r419

Математическая модель и алгоритм вычисления циклов ячеек карты графа

Авторы

  • Б. Н. Иванов

Ключевые слова:

карта графа
ячейки карты
циклы графа
свойства циклов

Аннотация

Выделенные свойства циклов DFS-базиса блока карты простого графа позволили составить математическую модель вычисления циклов ячеек карты графа. По данной модели предложен практический алгоритм вычисления циклов ячеек карты графа. Алгоритм имеет квадратическую сложность относительно числа вершин в графе.

Загрузки

Опубликован

2021-11-30

Выпуск

Том 22 (2021): Выпуск 4.

Раздел

Методы и алгоритмы вычислительной математики и их приложения

Автор

Б. Н. Иванов

Дальневосточный федеральный университет (ДВФУ),
Институт математики и компьютерных технологий,
ул. Суханова, 8, 690091, Владивосток
• доцент

Библиографические ссылки

  1. B. N. Ivanov, “Solution of the Optimal Ship Route Problem in the Framework of the OKEAN Geoinformation System,” Vychisl. Metody Programm. 13 (1), 226-234 (2012).
  2. J. T. Welch, “A Mechanical Analysis of the Cyclic Structure of Undirected Linear Graphs,” J. Assoc. Comput. Mach. 13 (2), 205-210 (1966).
  3. N. E. Gibbs, “A Cycle Generation Algorithm for Finite Undirected Linear Graphs,” J. Assoc. Comput. Mach. 16 (4), 564-568 (1969).
  4. R. Tarjan, “Enumeration of the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 2 (3), 211-216 (1973).
  5. D. B. Jonson, “Finding all the Elementary Circuits of a Directed Graph,” SIAM J. Comput. 4 (1), 77-84 (1975).
  6. P. Mateti and N. Deo, “On Algorithms for Enumerating all Circuits of a Graph,” SIAM J. Comput. 5 (1), 90-99 (1976).
  7. R. Tarjan, “Depth-First Search Linear Graph Algorithms,” SIAM J. Comput. 1 (2), 146-160 (1972).
  8. F. Mahdi, M. Safar, and K. Mahdi, “Detecting Cycles in Graphs Using Parallel Capabilities of GPU,” in Digital Information and Communication Technology and Its Applications (Springer, Berlin, 2011), Vol. 167, pp. 193-205.
  9. T. Kavitha, K. Mehlhorn, and D. Michail, “New Approximation Algorithms for Minimum Cycle Bases of Graphs,” Algorithmica 59 (4), 471-488 (2011).
  10. J. L. Pfaltz, “Chordless Cycles in Networks,” in Proc. IEEE 29th Int. Conf. on Data Engineering Workshops, Brisbane, Australia, April 8-12, 2013 (IEEE Press, New York, 2013), pp. 223-228.
  11. B. N. Ivanov, “Generation of Cycles of Map Cells for a Simple Planar Graph,” Vychisl. Metody Programm. 15 (2), 304-316 (2014).
  12. O. Ore, Theory of Graphs (AMS Press, Providence, 1962; Nauka, Moscow, 1980).
  13. F. P. Preparatat and M. I. Shamos, Computational Geometry: An Introduction (Springer, Heidelberg, 1985; Mir, Moscow, 1989).
  14. B. E. Alekseev and V. A. Talanov, Graphs. Computational Models. Structures (Lobachevsky State Univ. of Nizhni Novgorod, Nizhni Novgorod, 2005) [in Russian].
  15. K. Paton, “An Algorithm for Finding a Fundamental Set of Cycles of a Graph,” Commun. ACM 12 (9), 514-518 (1969).
  16. E. M. Reingold, J. Nievergelt, and N. Deo, Combinatorial Algorithms. Theory and Practice (Prentice-Hall, Englewood Cliffs, 1977; Mir, Moscow, 1980).
  17. B. N. Ivanov, “Nesting Structures of the Isoline Field in the Gradient Filling Problem,” Vychisl. Metody Programm. 7 (2), 30-40 (2006).

Лицензия

Copyright (c) 2021 Б.Н. Иванов

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.