邊覆蓋多項式

對給定的覆蓋單元集F，設圖G所有邊(點)覆蓋所構成的集族為J，對每一覆蓋S∈J，將一個單項式X(S)定義為Π_α∈Sw_α，進而對圖G賦以一個多項式P(G)，定義Σ_S∈JX(S)，這個P(G)便稱為圖G在F之下的“邊(點)覆蓋多項式”。

基本介紹

• 中文名：邊覆蓋多項式
• 所屬學科：數學（圖論）
• 性質：圖的一種多項式
• 相關概念：點覆蓋，簡單圖，覆蓋單元集等

基本介紹

考察有向(無向)簡單圖，其中，必要時也可以考慮有自環(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並無孤立頂點。

舉例分析

下面來看一些例子。

1．圈多項式

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

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

2.子圖多項式

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

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

就是雙色多項式，其中p(S)及q(S)分別表示由S的單元的並所構成的支撐子圖的分圖數及圈秩。

(2°) 若令，其中為連通子圖α的秩，則

就是秩多項式，其中，表示由S所成的支撐子圖的秩。

(3°) 若令，其中為連通子圖α的邊數，則

就是色多項式，事實上，記，並以表示H的生成子圖的秩，則上式可改寫為

這就是色多項式的展開式(極易由容斥原理推出)。

3．匹配多項式

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

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

基本定理

設圖G= (V，E)在單元集之下的邊(點)覆蓋多項式為P(G)，下面將給出這兩類多項式的一般消去定理。

定義4對任意的頂點子集及邊子集，二元組稱為G的“偽子圖”。

當中每條邊所關聯的頂點均屬於時，就是通常意義的子圖，將簡記為。

定義5給定G的一個偽子圖H，圖G關於H的部分邊(點) 覆蓋S_H，是指由若干個無公共邊(點)的單元所組成的集合，這些單元的並包含了H的全部頂點和邊，且每個單元都至少含有H的一個頂點或一條邊。

對於圖G的一個邊(點)覆蓋S 而言，如果S覆蓋著H的點和邊，則將S 中含有H的頂點或邊的單元取出來，這樣構成的子集S_H一定是關於H的部分覆蓋，即有，但反過來說，一個部分覆蓋卻不一定能成為某個覆蓋的子集(它未必能添上一些單元後構成G的覆蓋)。

定義6對部分邊(點)覆蓋而言，其相應的單項式定義為

特別當，因而時，。

此外，我們記。

現在，分兩種情況討論。

邊覆蓋多項式的消去定理

定義7一個關於H的部分邊覆蓋S_H稱為極大的，如果不存在以它為真子集的另一個關於H的部分邊覆蓋。

命題 對任一個邊覆蓋，由其中所有含有H的頂點或邊的單元所構成的部分邊覆蓋S_H一定是極大的。

證明：設是按上述方式導出的部分邊覆蓋，那么H中的邊()及H中的頂點所關聯的邊(的端點)均被S_H的單元所覆蓋；而任一單元均非孤立點，所以不存在這樣的單元，它與S_H的單元無公共邊而又包含H的頂點或邊，故S_H為極大的。

定理1設圖G在單元集之下的邊覆蓋多項式為P(G)，並設為G的一個偽子圖，則

其中為G關於H的一切極大的部分邊覆蓋的集合。

點覆蓋多項式的消去定理

取定圖G的一個偽子圖，考察由它除去一些邊所成的偽子圖H的集合

對於每一個，又考察部分點覆蓋的集合

{部分點覆蓋}. (4)

就是G關於H的部分點覆蓋，它的單元包含J' 的邊，而不包含的邊。為更明顯起見，對於，我們令。那么，就是圖G_H關於H的部分點覆蓋。

定理2 設圖G在單元集之下的點覆蓋多項式為P(G)，並設為G的一個偽子圖，則

其中集合及分別由(3)(4)式所定義。