2类图的完美匹配数的分类递推求法

首先,把图的完美匹配按关联某个顶点的边进行分类,求出每一类完美匹配数目的递推关系式.其次,把各类完美匹配的递推式相加,得到一组有相互联系的递推关系式,再利用这些递推式之间的相互关联,消去那些不需要的递推关系式,从而得到这个图的完美匹配数目的递推关系式.最后解出这个递推式的通解,进而得到这个图的完美匹配数目的显式公式.     

图2-2nP5和2-nK1,1,1,3完美匹配的计数

把图2-2nP₅和2-nK_1,1,1,3的完美匹配按匹配一个固定顶点的边进行分类, 先求出每类完美匹配数目的递推关系式, 得到一组有相互联系的递推关系式, 再利用这组递推式之间的相互关系, 给出这两个图完美匹配数的计数公式.     

图2-2nP5和2-nK1,1,1,3完美匹配的计数

把图2-2nP₅和2-nK_1,1,1,3的完美匹配按匹配一个固定顶点的边进行分类, 先求出每类完美匹配数目的递推关系式, 得到一组有相互联系的递推关系式, 再利用这组递推式之间的相互关系, 给出这两个图完美匹配数的计数公式.     

2类图完美匹配数按匹配顶点分类的递推求法

先把图3-nY₄和3-nC_6,3的完美匹配按饱和某个顶点的完美匹配进行分类, 得到一组有相互联系的递推关系式, 再由这组递推式间的关系给出这两类图完美匹配数的计算公式.     

按匹配顶点分类的完美匹配数递推求法

先把图2-nZ₆,2-nXT₃的完美匹配按匹配某个顶点进行分类, 求出一组相互联系的完美匹配数递推关系式, 再由这组递推关系式给出这两类图的完美匹配数计算公式.     

两类特殊图的1-因子数目

图的1-因子(完美匹配)数目问题是图论理论中的一个重要的问题,一般图的完美匹配计数问题已经被证实为N-P困难问题,因此,只能针对特殊图寻求其完美匹配数目.本文利用线性递推和组合线性递推的方法,给出了两类特殊图的完美匹配数的表达式.为图的完美匹配问题的应用提供了理论支持.     

按饱和顶点分类的完美匹配数的递推求法

构造了2类新图2-2nK₅和2-nZ₅,用嵌套递推的方法,得到了这2类新图的完美匹配数的2个递推关系式及其通解, 从而得到了这2类图的完美匹配数目的计算公式.     

2类图完美匹配计数公式的嵌套递推求法

把图2-nD_8和2-nD_6的完美匹配按饱和某个顶点的完美匹配进行分类,求出每一类完美匹配数目的递推关系式,再利用这些递推式之间的相互关系,得到这两类图的完美匹配数目的递推关系式,最后从递推式中解出这两类图的完美匹配数目的计算公式.     

3类图1-因子的数目

图的1-因子计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景.但是,一般图的1-因子计数问题却是NP-困难的.用划分,求和,再递推的方法分别给出了图2-2nC5,2-nC6和N2n的1-因子数目的计算公式.     

一类3-正则图完美对集的计数

图的完美对集计数理论是图论研究的重要内容之一,此问题的研究具有很强的计算机科学、物理学和化学的应用背景,是一个有生机和活力的研究领域,也是快速发展的组合数学理论中许多重要思想的源泉.构造了一类3-正则新图2-3-nC_6,用嵌套递推的方法,得到了图2-3-nC_6的完美对集数的一个递推关系,再解出这个递推式的通解,从而得到了这个图的完美对集数计算公式.最后又给出这个图完美对集数计算公式的一个组合证明.     

3类图的完美对集数按匹配顶点分类的递推求法

构造了三类新图2-2nN2,2-nX4和3-nD4,用递推的方法得到了图2-2nN2,2-nX4和3-nD4的完美对集数的三个递推关系式,再解出这三个递推式的通解,从而得到了这三类图的完美对集数的计算公式.     

两类图中完美匹配数的递推求法

该文针对两类特殊图2-nP和2-nC6,4 ，利用匹配顶点分类的方法，建立了两类图完美匹配数的递推关系式，并且解出了递推式的通解，从而得到了这两类图的完美匹配数目的计算公式.     

一类图的亏格嵌入

在联树模型的基础上,把图在曲面上的嵌入用其联树,也即其关联曲面来表示。然后通过对关联曲面进行分类,建立递推关系式,进而得到了一类异于目前已知嵌入分布的新图类的可定向嵌入分布。     

自然数幂和公式系数的递推公式和有关Bernoulli数的计算公式

研究了自然数幂和的表示公式,给出了其系数的一个递推关系式;利用递推关系式,得到幂和的各项系数,并由幂和公式的系数得到了计算Bernoulli数的几个计算公式.     

2类特殊图的完美对集数的分类递推求法

用划分、求和的方法分别给出了图2-nP_8和2-nZ_3的完美对集数目的递推关系式,再从得到的递推关系式中求出了这两类图的完美对集数目的显式计算公式.本文给出了求一些图的完美对集数的一种方法,为完美对集理论的应用提供了支持.     

广义θ-图的分数关联色数

本文从分数色数的定义和已有结论出发,针对两种不同的情况分别给出广义θ-图的分数关联色数,并由此进一步给出广义θ-图的r-冠图的分数关联色数,得到如下结论:incf(θk)={k+1 ,至少有一条路径的长不为2/k2/d-1所有路径的长均为2;incf(Ir(θk))=inc(Ir(θk))=k+r+1.     

直线划分平面区域问题

本文运用欧拉公式对直线划分平面区域问题进行一些探讨。 欧拉(Euler)在研究凸多面体时,得出它们的顶点数、棱数和面数之间的一个简单关系式。这个关系式还可推广到平面上来,用图论的语言叙述就是下面的定理[1]. 定理 若一个连通平面图G的顶点数为P,棱数为q,面数为f,则 p-q+f=2 这个公式称为欧拉公式.若无限面不计在内,则有 p-q+f=1. 关于这个定理的证明,在一般图论参考书中均可查到。下面我们利用欧拉公式对直线划分平面区域问题进行一些探讨. 对于欧氏平面上的任意一条直线a(图二),它把欧氏平面分为两个”半平面”或”区域”。平面上属…     

若干图类的生成树数

连通图的生成树是该图的极小连通生成子图。本文求出了所有梯形图、扇形图和轮形图生成树的棵数，分别给出了它们的递推关系式和通项表达式．     

简单图类的生成树数（I）

连通图的生成树是该图的极小连通生成图。本文通过Ｃａｙｌｅｙ公式及求解递推关系方程，分别求出了三类简单外平面图Ａｎ，Ｂｎ和Ｚｎ的生成树的棵数，给出了它们的递推关系式及通项表达式。     

简单图类的生成树数（Ⅰ）

连通图的生成树是该图的极小连通生成子图．本文通过Ｃａｙｌｅｙ公式及求解递推关系方程，分别求出了三类简单外平面图Ａ＿ｍ，Ｂ＿ｍ和Ｚ＿ｍ的生成树的棵数，给出了它们的递推关系式及通项表达式．