Многочлен паросочетаний

Перейти к навигацииПерейти к поиску

Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе.

Определения

Известны несколько связанных типов определений:

где обозначает число паросочетаний из пар графа .

Замечания

Каждый тип имеет свои преимущества, и все эквивалентны путем несложных преобразований. Например,

и

См. также