本頁使用了標題或全文手工轉換

積和式

維基百科,自由的百科全書
跳至導覽 跳至搜尋

數學,特別是線性代數中,積和式是一個與行列式類似的多項式。與行列式類似,積和式可以看作是定義在一個變數矩陣上。積和式在計算機科學,特別是計算複雜性理論中有重要的地位。比如計算一個二分圖(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完全的。相對的,行列式可以用高斯消去法等算法在多項式時間內解決。