本页使用了标题或全文手工转换

积和式

维基百科,自由的百科全书
跳到导航 跳到搜索

数学,特别是线性代数中,积和式是一个与行列式类似的多项式。与行列式类似,积和式可以看作是定义在一个变量矩阵上。积和式在计算机科学,特别是计算复杂性理论中有重要的地位。比如计算一个二分图(bipartite graph)的完美匹配(perfect matching)的数目可以方便的表示为计算积和式的值。

定义[编辑]

对于一个n×n的矩阵,我们将看作是不定元,记关于A的积和式为perm(A),则其定义为

其中求和是对所有的为n阶置换群。再举例如:

从定义不难验证,积和式是多线性多项式,且在置换A中行(或列)的操作下保持不变。与行列式类似,积和式可以用拉普拉斯展开式展开。

与积和式相类似,但在性质上有很大不同的是行列式。对于n×n的矩阵,行列式的定义为

其中符號差。可以看出从形式上,两者的区别仅在于对某些项,前面的符号有所不同。

组合上的解释[编辑]

积和式的定义可以从如下两方面理解,即计算二分图上完美匹配的个数,以及计算一个上的圈覆盖的权重。

与二分图完美匹配的关系[编辑]

二分图上的完美匹配是算法理论和计算复杂性理论中的重要问题。对于一个n×n的二分图G=(L, R, E),其中L={1, 2,..., n}是左边结点的集合,R={1', 2', ..., n'}是右边结点的集合,E为边的集合,G的一个完美匹配是{1, 2, ..., n}到{1', 2', ..., n'}的一个双射f,使得(1, f(1)), (2, f(2)), ..., (n, f(n))都在E中出现。

对G,我们可以建立如下n×n的0-1矩阵,其中当且仅当。不难验证,的值即是G中完美匹配的个数。这样,我们将积和式的值与二分图完美匹配的个数建立了联系。

与图的圈覆盖的关系[编辑]

对于一个图G=(V,E),V={1, 2, ..., n}为结点集,E为边集。一个G的圈覆盖是一组G中的不相交的圈的集合,且这些圈覆盖所有的点集。由于一个置换可以做环状分解,可以看出一个置换与一个可能的圈覆盖是一一对应的。特别的,G的邻接矩阵的积和式即是G中圈覆盖的数目。

积和式的计算复杂性[编辑]

积和式的计算是#P完全的。相对的,行列式可以用高斯消元法等算法在多项式时间内解决。