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

Подсчёт циклов в двудольных графах с длиной менее трёх обхватов

Результаты предыдущей работы, посвящённой подсчёту коротких циклов в двудольных графах, обобщены на случай, когда длина цикла меньше трёх обхватов графа. Посредством вычислительных экспериментов показано, что при значениях обхвата g = 4, 6, 8, 10 наибольшие кратности сумм в явных формулах для подсчёта циклов длиной 2g+2, 2g+4, … , 3g-2 в двудольных графах равны 4. В то же время, найдено семейство двудольных форм замкнутых маршрутов длиной 3g с обхватом g, которым соответствуют шестикратные суммы (для всех чётных значений g ≥ 4). Оценка практической эффективности явных формул для подсчёта циклов длиной менее 3g выполнена в сравнении с несколькими известными перечислительными методами.

КЛЮЧЕВЫЕ СЛОВА: подсчёт циклов, обхват, двудольные формы