圈多項式

圈多項式

在無向圖的情況,設覆蓋單元集F由G中所有的K1(一點生成子圖)、K2(一邊生成子圖)及初級圈(點數≥3)所構成,R為實數域上的多項式環,由此產生出的點覆蓋多項式通常稱為“圈多項式”。

基本介紹

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

考察有向(無向)簡單圖,其中,必要時也可以考慮有自環(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(一邊生成子圖)及初級圈(點數≥3)所構成,R為實數域上的多項式環,由此產生出的點覆蓋多項式通常稱為“ 圈多項式”,特別當單元K的度量為(未定元),K的度量為-1,其它初級圈的度量為-2時,點覆蓋多項式

圈多項式 圈多項式

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

相關概念

子圖多項式

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式

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

匹配多項式

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

設由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的一個頂點或一條邊。

圈多項式 圈多項式

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

圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

特別當,因而時,。

圈多項式 圈多項式

此外,我們記。

現在,分兩種情況討論。

邊覆蓋多項式的消去定理

圈多項式 圈多項式

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

圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

點覆蓋多項式的消去定理

圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

{部分點覆蓋}. (4)

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式

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

圈多項式 圈多項式
圈多項式 圈多項式
圈多項式 圈多項式

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

相關詞條

熱門詞條

聯絡我們