取定圖G的一個子圖族F，對其中每一個子圖α∈F，賦以某一整環R中之元 wα，作為它的度量，這樣一個具有度量的子圖族F便稱為“覆蓋單元集”；其中每一個子圖α 稱為“(覆蓋)單元”。當G為無向圖，F由G的一切連通子圖所構成時，圖G在F之下的點覆蓋多項式稱為“子圖多項式”，而當單元α∈F的度量w(α)不同時，可得一些特殊的多項式，例如雙色多項式、秩多項式、色多項式等。
基本介紹
- 中文名：子圖多項式
- 外文名：subgraph polynomial
- 所屬學科：數學（圖論）
- 屬性：圖的一種多項式
- 簡介：一種點覆蓋多項式
基本介紹,相關定義,邊(點)覆蓋多項式,子圖多項式的定義,相關概念,圈多項式,匹配多項式,相關定理,
基本介紹
相關定義
定義1取定圖G的一個子圖族
；對其中每一個子圖
，賦以某一整環R中之元
，作為它的度量，這樣一個具有度量的子圖族 便稱為“覆蓋單元集”；其中每一個子圖α稱為“(覆蓋)單元”。
定義2對於不含全不連通子圖的覆蓋單元集 而言，圖G的一個“邊覆蓋”，是指由若干個無公共邊的單元所組成的集合
，使得
定義2’對給定的覆蓋單元集 而言，圖G的一個“點覆蓋”，是指由若干個無公共頂點的單元所組成的集合 ，使得
邊(點)覆蓋多項式
定義3對給定的覆蓋單元集 ，設圖G所有邊(點)覆蓋所構成的集族為
，對每一覆蓋
，賦以一個單項式
下文始終採取“空和為零，空積為1“的習慣約定，因此，當
時，P(G)=0，當G=
(空圖)時，只有一個覆蓋
；而
，所以
。其次，在邊覆蓋多項式的情況，增減一些孤立頂點時邊覆蓋不變，因而多項式亦不變；故此時不妨假定圖G並無孤立頂點。
子圖多項式的定義
當G為無向圖， 由G的一切連通子圖所構成時，圖G在 之下的點覆蓋多項式稱為“子圖多項式”，而當單元
的度量
不同時，可得一些特殊的多項式，例如：
(1°) 對每一單元 ，賦以度量
，其中
為連通子圖α的圈秩，那么圖G在這種覆蓋意義下的多項式
(2°) 若令
，其中
為連通子圖α的秩，則
(3°) 若令
，其中
為連通子圖α的邊數，則
相關概念
圈多項式
在無向圖的情況，設 由G中所有的K1(一點生成子圖)、K2(一邊生成子圖)及初級圈(點數≥3)所構成，R為實數域上的多項式環，由此產生出的點覆蓋多項式通常稱為“圈多項式”，特別當單元K1的度量為
(未定元)，K2的度量為-1，其它初級圈的度量為-2時，點覆蓋多項式
就是熟知的特徵多項式，其中p(S)為S中有邊的單元數，q(S)為S中的圈數。
匹配多項式
設 由G中所有子圖K1及K2所構成，它們的度量分別為x及y，由這種單元組成的點覆蓋S就是圖G的“匹配”(matching)；它對應的單項式為
，其中
為S中單元K2的數目(邊數)，於是
相關定理
設圖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的集合
定理2 設圖G在單元集 之下的點覆蓋多項式為P(G)，並設 為G的一個偽子圖，則
