A survey of Pfaffian orientations of graphs
A survey of Pfaffian orientations of graphs
复制标题
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
R. Thomas
中科院分区：
文献类型：
--
作者：
R. Thomas
如果每一个偶循环C使得G\V (C)有一个完美匹配且在循环的任意方向上都有奇数条边，那么图G的取向就是普氏的。Pfaffian取向的意义在于，如果一个图有一个，那么完美匹配的数量（又称二聚体问题）可以在多项式时间内计算出来。哪些二部图具有普氏取向的问题等价于许多其他感兴趣的问题，如Polya的永久问题，偶有向环问题，或方阵的符号-非奇异矩阵问题。这些问题现在已经相当清楚了。另一方面，如何有效地检验一般图是否为普氏图是未知的，但与正则图的交叉数和边着色的符号有一些有趣的联系。
An orientation of a graph G is Pfaffian if every even cycle C such that G\V (C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance of Pfaffian orientations is that if a graph has one, then the number of perfect matchings (a.k.a. the dimer problem) can be computed in polynomial time. The question of which bipartite graphs have Pfaffian orientations is equivalent to many other problems of interest, such as a permanent problem of Polya, the even directed cycle problem, or the sign-nonsingular matrix problem for square matrices. These problems are now reasonably well-understood. On the other hand, it is not known how to efficiently test if a general graph is Pfaffian, but there are some interesting connections with crossing numbers and signs of edgecolorings of regular graphs.