匹配多项式

匹配多项式(matching polynomial)是图的一种多项式，设F由G中所有子图K1及K2所构成，它们的度量分别为x及y，由这种单元组成的点覆盖S就是图G的“匹配”(matching)；它对应的单项式为xn-2ε(S)yε(S)，其中ε(S)为S中单元K2的数目(边数)，这个单项式对应相应的多项式就是图G的匹配多顶式。。考察有向(无向)简单图，其中，必要时也可以考虑有自环(loop)的有向图，今后分别以V(S)及E(S)表示子图S的顶点集及边集；记号表示子图的并运算。