匹配多項式

匹配多項式(matching polynomial)是圖的一種多項式，設F由G中所有子圖K₁及K₂所構成，它們的度量分別為x及y，由這種單元組成的點覆蓋S就是圖G的“匹配”(matching)；它對應的單項式為xy，其中ε(S)為S中單元K₂的數目(邊數)，這個單項式對應相應的多項式就是圖G的匹配多頂式。。

基本介紹

• 中文名：匹配多項式
• 外文名：matchingpolynomial
• 所屬學科：數學（圖論）
• 屬性：圖的一種多項式
• 相關概念：匹配，點覆蓋多項式，點覆蓋等

基本介紹

考察有向(無向)簡單圖，其中，必要時也可以考慮有自環(loop)的有向圖，今後分別以V(S)及E(S)表示子圖S的頂點集及邊集；記號表示子圖的並運算。

相關定義

定義1取定圖G的一個子圖族；對其中每一個子圖，賦以某一整環R中之元，作為它的度量，這樣一個具有度量的子圖族便稱為“覆蓋單元集”；其中每一個子圖α稱為“(覆蓋)單元”。

定義2對於不含全不連通子圖的覆蓋單元集而言，圖G的一個“邊覆蓋”，是指由若干個無公共邊的單元所組成的集合，使得

換言之，構成邊集E(G)的一個劃分。

定義2’對給定的覆蓋單元集而言，圖G的一個“點覆蓋”，是指由若干個無公共頂點的單元所組成的集合，使得

換言之，構成頂點集V(G)的一個劃分。

邊(點)覆蓋多項式

定義3對給定的覆蓋單元集，設圖G所有邊(點)覆蓋所構成的集族為，對每一覆蓋，賦以一個單項式

進而對圖G賦以一個多項式

這個P(G)便稱為圖G在之下的“邊(點)覆蓋多項式”。

下文始終採取“空和為零，空積為1“的習慣約定，因此，當時，P(G)=0，當G=(空圖)時，只有一個覆蓋；而，所以。其次，在邊覆蓋多項式的情況，增減一些孤立頂點時邊覆蓋不變，因而多項式亦不變；故此時不妨假定圖G並無孤立頂點。

匹配多項式的定義

設由G中所有子圖K₁及K₂所構成，它們的度量分別為x及y，由這種單元組成的點覆蓋S就是圖G的“匹配”(matching)；它對應的單項式為，其中為S中單元K₂的數目(邊數)，於是

就是圖G的匹配多項式，其中為k邊匹配的數目。

相關概念

1．圈多項式

在無向圖的情況，設由G中所有的K₁(一點生成子圖)、K₂(一邊生成子圖)及初級圈(點數≥3)所構成，R為實數域上的多項式環，由此產生出的點覆蓋多項式通常稱為“圈多項式”，特別當單元K₁的度量為(未定元)，K₂的度量為-1，其它初級圈的度量為-2時，點覆蓋多項式

就是熟知的特徵多項式，其中p(S)為S中有邊的單元數，q(S)為S中的圈數。

2.子圖多項式

當G為無向圖，由G的一切連通子圖所構成時，圖G在之下的點覆蓋多項式稱為“子圖多項式”，而當單元的度量不同時，可得一些特殊的多項式，例如：

(1°) 對每一單元，賦以度量，其中為連通子圖α的圈秩，那么圖G在這種覆蓋意義下的多項式