Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)8653ArticlesСтатьиThe Number of Fixed Length Cycles in Undirected Graph Explicit Formula in Case of Small LengthsКоличество простых циклов фиксированной длины в неориентированном графе. Явные формулы в случае малых длинVoropaevA NВоропаевАнтон НиколаевичКафедра прикладной математики и кибернетики; Петрозаводский государственный университет; Petrozavodsk State UniversityКафедра прикладной математики и кибернетики; Петрозаводский государственный университетantonvoropaev@mail.ruPerepechkoS NПерепечкоСергей НиколаевичКафедра прикладной математики и кибернетики; Петрозаводский государственный университет; Petrozavodsk State UniversityКафедра прикладной математики и кибернетики; Петрозаводский государственный университетpersn@newmail.ruPetrozavodsk State UniversityПетрозаводский государственный университет150220122NO2 (2012)№2 (2012)61208092016Copyright ©; 2012, Voropaev A.N., Perepechko S.N.Copyright ©; 2012, Воропаев А.Н., Перепечко С.Н.2012Voropaev A.N., Perepechko S.N.Воропаев А.Н., Перепечко С.Н.https://creativecommons.org/licenses/by-nc/4.0https://journals.rudn.ru/miph/article/view/8653Modifications of Ross and Harary algorithm to express the number ck of cycles of length k in an undirected graph in terms of its adjacency matrix are developed. The general undirected graphs as well as bipartite graphs were considered. Computer algebra implementations of the algorithms enable us to construct the formulae at least for k ≤ 12 in general case and for k ≤ 14 in case of bipartite graph. It was shown that, for any fixed value of k ≥ 8 and space complexity quadratic in order n of a graph, the time complexity of computing ck is O(n[k/2] logn). In case of bipartite graph, for k = 8,10,14 better estimations are obtained: O(n3 log2n), O(n4 log2n), O(n6 log2n).Разработаны модификации алгоритма Росса и Харари для вывода формул, выражающих количество ck простых циклов длиной k в неориентированном графе через его матрицу смежности. Рассмотрены как общий случай, так и случай двудольного графа. Алгоритмы, реализованные в системе компьютерной алгебры, позволяют выводить формулы при k ≤ 12 в общем случае и при k ≤ 14 в случае двудольного графа. Установлено, что при любом фиксированном k ≥ 8 и затратах памяти, квадратичных относительно порядка n графа, время вычисления ck есть величина O(n[k∕2] logn). Для случая двудольного графа при k = 8,10,14 установлены лучшие оценки: O(n3 log2n), O(n4 log2n), O(n6 log2n).graph algorithmscycles in graphadjacency matrixалгоритмы на графахциклы в графахматрица смежности1.Harary F., Ross I.C. The Number of Complete Cycles in a Communication Network // The Journal of Social Psychology. - 1954. - Vol. 40. - Pp. 329-332.2.Bianconi G., Capocci A. Number of Loops of Size . in Growing Scale-Free Networks // Physical Review Letters. - 2003. - Vol. 90, No 7. - P. 078701(4).3.Structural Properties of Planar Graphs of Urban Street Patterns / A. Cardillo, S. Scellato, V. Latora, S. Porta // Physical Review E. - 2006. - Vol. 73, No 6. - P. 066107(8).4.Fagiolo G. Clustering in Complex Directed Networks // Physical Review E. - 2007. - Vol. 76. - P. 026107(8).5.Halford T.R., Chugg K.M. An Algorithm for Counting Short Cycles in Bipartite Graphs // IEEE Transactions on Information Theory. - 2006. - Vol. 52, No 1. - Pp. 287-292.6.Ross I.C., Harary F. On the Determination of Redundancies in Sociometric Chains // Psychometrika. - 1952. - Vol. 17, No 2. - Pp. 195-208.7.Harary F., Manvel B. On the Number of Cycles in a Graph // Matematick.y .casopis. - 1971. - Vol. 21. - Pp. 55-63.8.Alon N., Yuster R., Zwick U. Finding and Counting Given Length Cycles // Algorithmica. - 1997. - Vol. 17. - Pp. 209-223.9.Chang Y.C., Fu H.L. The Number of 6-cycles in a Graph // Bulletin of the Institute of Combinatorics and its Applications. - 2003. - Vol. 39.10.Хоменко Н.П., Головко Л.Д. Выделение из графа его частей некоторых типов и подсчёт их количества // Украинский математический журнал. - 1972. - Т. 24, № 3. - С. 385-396. [Khomenko N.P., Golovko L.D. Vihdelenie iz grafa ego chasteyj nekotorihkh tipov i podschyot ikh kolichestva // Ukrainskiyj matematicheskiyj zhurnal. - 1972. - T. 24, No 3. - S. 385-396. ]