Русская Википедия:Многочлен паросочетаний

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определения

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

<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>

См. также

• Хроматический многочлен