Количество простых циклов фиксированной длины в неориентированном графе. Явные формулы в случае малых длин

Разработаны модификации алгоритма Росса и Харари для вывода формул, выражающих количество 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).

алгоритмы на графах, циклы в графах, матрица смежности