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

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

Определения

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

m_{\Gamma }(x):=\sum _{k\geq 0}m_{k}x^{k},

M_{\Gamma }(x):=\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},

\mu _{\Gamma }(x,y):=\sum _{k\geq 0}m_{k}x^{k}y^{n-2k},

где $m_{k}$ обозначает число паросочетаний из $k$ пар графа $\Gamma$ .

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

M_{\Gamma }(x)=x^{n}m_{\Gamma }(-x^{-2})

и

\mu _{\Gamma }(x,y)=y^{n}m_{\Gamma }(x/y^{2}).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.