Русская Википедия:Многочлен паросочетаний
Материал из Онлайн справочника
Многочлен паросочетаний — производящая функция для числа паросочетаний различных размеров в графе.
Определения
Известны несколько связанных типов определений:
- <math>m_\Gamma(x) := \sum_{k\geq0} m_k x^k,</math>
- <math>M_\Gamma(x) := \sum_{k\geq0} (-1)^k m_k x^{n-2k},</math>
- <math>\mu_\Gamma(x,y) := \sum_{k\geq0} m_k x^k y^{n-2k},</math>
где <math>m_k</math> обозначает число паросочетаний из <math>k</math> пар графа <math>\Gamma</math>.
Замечания
Каждый тип имеет свои преимущества, и все эквивалентны путем несложных преобразований. Например,
- <math>M_\Gamma(x) = x^n m_\Gamma(-x^{-2})</math>
и
- <math>\mu_\Gamma(x,y) = y^n m_\Gamma(x/y^2).</math>
См. также