简介:关于一般的图的完美匹配计数的问题已证实是NP—hard问题。但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决。由此可见图的Pfaffian性的重要性。在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.
关于图的运算与图的Pfaffian性