|
Conference publicationsAbstractsXVII conferenceЯвные формулы для подсчёта простых циклов с длиной, близкой к обхвату графаПетрозаводский государственный университет, Россия, 185910, Петрозаводск, пр. Ленина, 33, 8(814)78-51-40, voropaev@psu.karelia.ru, persn@aport.ru 1 pp. (accepted)Разработана вычислительная схема метода Харари и Манвела для вывода формул, выражающих количество простых циклов длиной k в неориентированном графе через его матрицу смежности. Алгоритм учитывает структурные особенности графов, такие как двудольность графа или отсутствие в нём коротких циклов. В результате для частных семейств графов получаются более компактные и эффективные формулы по сравнению с общим случаем. Применение системы компьютерной алгебры позволяет выводить выражения до значения k = 16. Для двудольных графов с обхватом g при k ≤ g + 4 ≤ 16 вычислительная сложность формул сопоставима со сложностью умножения матриц размера n × n, где n – порядок графа. При этом затраты памяти квадратичны относительно n. Зависимость сложности выражений для произвольных и двудольных графов была показана ранее [1]. В следующей таблице (см. прилагаемый pdf-файл) представлено количество слагаемых в формулах для двудольных графов с учётом обхвата графа (до черты) и без учёта (после черты). Метод Харари и Манвела [2] применялся в работах других авторов [3, 4]. Однако при этом не предлагалось систематизированной схемы вывода формул, без которой не удалось продвинуться далее значения k = 7. Альтернативный способ подсчёта простых циклов длиной g, g+2 и g+4 в двудольных графах приводится в [5]. Предложенный в этой статье алгоритм не ограничен малыми значениями g, однако в случае g ≤ 12 он несколько уступает по эффективности формулам, полученным в данной работе.
1. Perepechko S. N., Voropaev A. N. The number of fixed length
cycles in an undirected graph. Explicit formulae in case of small lengths //
Mathematical Modeling and Computational Physics (MMCP'2009). – Dubna : JINR,
2009. – Стр. 148-149. |
