А.Н. Воропаев

Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах

Приводится описание двух способов вывода формул для количества циклов длиной k в неориентированных графах. Идея вывода состоит в перечислении всевозможных конфигураций замкнутых маршрутов длиной k и выражении чисел соответствующих маршрутов через матрицу смежности графа. Комбинация указанных величин с определёнными коэффициентами, которые также требуется вычислить, даёт формулу для подсчёта циклов. Оба способа вывода основаны на подходах, предложенных в работах Росса, Харари и Манвела. В одном случае коэффициенты, входящие в формулу, вычисляются в ходе перечисления конфигураций, а в другом ‒ исходя из сгенерированного набора конфигураций. Реализация способов в системе компьютерной алгебры позволила продвинуться до значения k = 13.