图型序列多元母函数的若干结果

本文讨论了图型序列多元母函数的性质，给出了割集定理和一些递归性质．利用这些性质可简化图型序列多元母函数的计算．

图型序列母函数的递归性质

以有向图Ｇ的顶点为元素，Ｇ的有向途径所对应的序列称为图型序列．本文讨论图型序列母函数的一些递归性质，主要包括割点定理，割边定理和删点公式．利用这些性质可以简化图型序列母函数的计算．

一些特殊图的生成函数

利用“图型序列的母函数”所给出的图型序列生成函数的性质，本文导出一些重要特殊图的生成函数。ｎ，ｍ（－ｘ）＝１，所以有定理４设Ｇ为ｎ阶出（或人）ｋ正则图（每个顶点的出（或人）度均为ｋ），则证明由条件可知，Ｉ—Ａｘ的各行之和均为１－ｋｘ，Ｉ＋ｘ的各行之和均为１＋（ｎ－ｋ）ｘ，于是其中ａｉｊ＝１－ａｉｊ由此可得定理５无向轮图的生成函数为证明因为具有ｎ个顶点的轮图的补图是由仅有一个含自回路的顶点及ｎ－１阶ｎ－３正则图构成的非连通图，所以由此可得定理６ ｎ阶无环无向路的生成函数其中△＝证明 设Ｐｎ的邻接矩阵为Ａ，则设Ｄｎ的伴随矩阵易知Ｄｉｊ＝Ｄｊｉ，当ｊ≥ｉ时，于是代入后，经整理即得证。