2类图的完美匹配数的分类递推求法

摘要

首先,把图的完美匹配按关联某个顶点的边进行分类,求出每一类完美匹配数目的递推关系式.其次,把各类完美匹配的递推式相加,得到一组有相互联系的递推关系式,再利用这些递推式之间的相互关联,消去那些不需要的递推关系式,从而得到这个图的完美匹配数目的递推关系式.最后解出这个递推式的通解,进而得到这个图的完美匹配数目的显式公式.