С.Н. Перепечко

Количество совершенных паросочетаний в графах C_m×C_n

Обсуждается эффективность формул для числа совершенных паросочетаний на торах C_m×C_n, пригодных для проведения расчётов в больших графах. Получен набор рекуррентных соотношений при фиксированном значении параметра m ≤ 20 и изучены их основные свойства. Установлена зависимость порядка соотношения от m в виде оценки сверху. Найдена асимптотика числа совершенных паросочетаний при фиксированном m.

КЛЮЧЕВЫЕ СЛОВА: совершенные паросочетания, подсчёт паросочетаний, рекуррентные соотношения, производящие функции