對給定的覆蓋單元集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中所有的K1(一點生成子圖)、K2(一邊生成子圖)及初級圈(點數≥3)所構成,R為實數域上的多項式環,由此產生出的點覆蓋多項式通常稱為“圈多項式”,特別當單元K1的度量為 (未定元),K2的度量為-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中所有子圖K1及K2所構成,它們的度量分別為x及y,由這種單元組成的點覆蓋S就是圖G的“匹配”(matching);它對應的單項式為 ,其中 為S中單元K2的數目(邊數),於是
就是圖G的匹配多項式,其中 為k邊匹配的數目。
基本定理
設圖G= (V,E)在單元集 之下的邊(點)覆蓋多項式為P(G),下面將給出這兩類多項式的一般消去定理。
定義4 對任意的頂點子集 及邊子集 ,二元組 稱為G的“偽子圖”。
當 中每條邊所關聯的頂點均屬於時,就是通常意義的子圖,將簡記為。
定義5 給定G的一個偽子圖H,圖G關於H的部分邊(點) 覆蓋SH,是指由若干個無公共邊(點)的單元所組成的集合,這些單元的並包含了H的全部頂點和邊,且每個單元都至少含有H的一個頂點或一條邊。
對於圖G的一個邊(點)覆蓋S 而言,如果S覆蓋著H的點和邊,則將S 中含有H的頂點或邊的單元取出來,這樣構成的子集SH一定是關於H的部分覆蓋,即有,但反過來說,一個部分覆蓋卻不一定能成為某個覆蓋的子集(它未必能添上一些單元後構成G的覆蓋)。
定義6 對部分邊(點)覆蓋而言,其相應的單項式定義為
特別當,因而 時,。
此外,我們記。
現在,分兩種情況討論。
邊覆蓋多項式的消去定理
定義7 一個關於H的部分邊覆蓋SH稱為極大的,如果不存在以它為真子集的另一個關於H的部分邊覆蓋。
命題 對任一個邊覆蓋,由其中所有含有H的頂點或邊的單元所構成的部分邊覆蓋SH一定是極大的。
證明: 設是按上述方式導出的部分邊覆蓋,那么H中的邊()及H中的頂點所關聯的邊(的端點)均被SH的單元所覆蓋;而任一單元均非孤立點,所以不存在這樣的單元,它與SH的單元無公共邊而又包含H的頂點或邊,故SH為極大的。
定理1 設圖G在單元集之下的邊覆蓋多項式為P(G),並設為G的一個偽子圖,則
其中為G關於H的一切極大的部分邊覆蓋的集合。
點覆蓋多項式的消去定理
取定圖G的一個偽子圖,考察由它除去一些邊所成的偽子圖H的集合
對於每一個,又考察部分點覆蓋的集合
{部分點覆蓋}. (4)
就是G關於H的部分點覆蓋,它的單元包含J' 的邊,而不包含的邊。為更明顯起見,對於,我們令。那么,就是圖GH關於H的部分點覆蓋。
定理2 設圖G在單元集之下的點覆蓋多項式為P(G),並設為G的一個偽子圖,則
其中集合及分別由(3)(4)式所定義。