點覆蓋多項式

對給定的覆蓋單元集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)式所定義。