论文部分内容阅读
给图G的边任意一个定向，如果该有向图对应的斜邻接矩阵的行列式等于图 G 的完美匹配数的平方，那么就称这个定向是Pfaffian定向，图G称为Pfaffian图。研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到。该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图。