完全i部图N［(X1,X2,…,Xi),k］计数公式

采用组合卷积公式方法,研究图的S(n)-因子的计数问题.首先获得完全2-部图的恰有k个分支的S(n)-因子的计数公式,并用同样方法获得完全i-部图的恰有k个分支的S(n)-因子的计数公式,从而给出完全i-部图的所有因子数计数公式.进一步研究了完全i-部图的组合恒等式,并通过组合计算技巧,获得了完全i-部图、完全2-部图和完全3-部图的组合恒等武.该研究对图论及组合学具有理论和应用价值.     

两类特殊图1-因子数分类递推求法

图的1-因子计数问题已经被证明是NP-难的,但因该问题在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.首先,把图的1-因子按关联某个顶点的边进行分类,求出每一类1-因子数的递推关系式.其次,把各类1-因子的递推关系式相加,得到一组有相互联系的递推关系式,再利用这些递推关系式之间的相互关联,消去那些不需要的递推关系式,从而得到这个图的1-因子数的递推关系式.最后解出这个递推关系式的通解,进而得到这个图的1-因子数的显式公式.     

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

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

平面上4×n矩形格图中圈的计数

研究有限图上圈的计数问题,对运筹学上的“图上作业法”、集成电路的线路设计、有机分子的结构等,都有一定的实用意义。[1]中讨论了平面上2×n矩形格图中圈的计数问题,[2]中讨论了平面上2×n矩形和环形格图以及3/2×n矩形和环形格图中圈的计数问题,[3]中讨论了平面上3×n矩形和环形格图中圈的计数问题,都分别得到了相应的公式。本文将讨论平面上4×n矩形格图中圈的计数问题,并得到相应的公式。     

2类特殊偶图完美匹配的计数

图的完美匹配计数问题是匹配理论研究的一个重要课题,此问题有很强的物理学和化学背景.LovszL和Plummer M就曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.但是,一般图的完美匹配计数问题已经被证明了是NP-难问题.用划分,求和,再嵌套递推的方法给出了2类特殊偶图完美匹配数目的显式表达式,从而验证了LovászL和Plummer M猜想在这2类图上的正确性,所给出的方法,可以计算出许多偶图的所有完美匹配的数目.     

两类最小可行图的计数

讨论了最小可行图的计数问题,得到了关于(X_1,X_2)和(X_1,X_2,X_3)的最小可行图的计数公式.     

3-正则图的1-因子与割边数

利用Tutte条件证明了恰有1条割边或2条割边的3-正则图存在1-因子,而且1-因子必包含其割边.并且得出了一些结论,最后给出了必然存在1-因子的3-正则图的割边数的上限为2,构造了一类可以允许有若干条割边的3-正则图存在1-因子.     

2类图完美匹配的数目

一般图的完美匹配计数问题是NP-困难的.用划分、求和、再递推的方法给出了2类特殊图完美匹配数目的计算公式.所给出的方法,可以计算出许多二分图的所有完美匹配的数目.作为应用,计算出了一类棋盘1×2的多米诺覆盖数目.     

关于圈图Cn 的连2距k着色计数

研究圈图 的连2距 着色计数问题,通过求解递推关系得到若干计数公式.     

8-图的自同态幺半群

研究了8-图的正则自同态幺半群的代数结构,确定了正则自同态幺半群的Green关系以及相关的计数问题.讨论了8-图的自同态幺半群的完全正则性.     

6类图完美匹配的数目

 图的完美匹配计数问题是匹配理论研究中的一个重要课题,此问题有很强的物理学和化学背景,历来引起众多数学家,物理学家和化学家的广泛关注。但是,一般图的完美匹配计数问题却是NP－难的。用划分,求和,再递推的方法给出了6类特殊图完美匹配数目的计算公式。作为应用,计算出了一类棋盘1×2的多米诺覆盖的数目。     

5类图完美匹配的计数

 匹配计数理论是图论的核心内容之一,由于得到应用领域的支持,并与其他理论课题发生密切联系,受到众多学者的关注,产生出许多含义丰富而深刻的理论成果。但是,一般图的完美匹配计数问题却是〖WTBX〗NP-〖WTBZ〗困难的。用划分、求和、再递推的方法给出了5类图完美匹配数目的显式表达式。所给出的方法,可以计算出许多二分图的所有完美匹配的数目。     

图的邻域并和连通的[k,k+1]-因子

设G是阶为n的图.F是G的支撑子图且对所有的x∈V(G)都有k≤dF(x)≤k+1,则称F为G的[k,k+1]-因子.一个[k,k+1]-因子如果连通,则称为连通的[k,k+1]-因子.一个[k,k+1]-因子若包含一个哈密顿圈,则称为哈密顿[k,k+1]-因子.给出了图有哈密顿[k,k+1]-因子或连通的[k,k+1]-因子关于邻域并的若干新的充分条件.     

2类图完美匹配数的计算

一般图的完美匹配计数问题是NP-难问题。本文用划分、求和及嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式,所用的方法也开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。σ（n）和g（n）分别表示图3-nC6．3和2-nK3.3的完美匹配的数目。证明σ（n）3＋√3/6·（4＋2√3）^n,g（n）=41＋5√41/82,（7＋√41/2）^n＋（41-5）√41/82·（7-√41/2）^n.     

立方图中的路因子和圈因子

给定连通图集合Φ,对图G的生成子图F,如果F的每个分支都同构于集合Φ的一个元素,则F被称为G的Φ-因子.最近Kawarabayashi 等证明了:2-连通立方图有一个{Cn|n≥4}-因子和{pn|n≥6}-因子,其中Cn表示阶为n的圈,Pn表示阶为n的路.Kano等给出了每一个阶至少为8的立方偶图有{Cn|n≥6}-因子和{pn|n≥8}-因子的结论,并且提出猜想:阶至少为6的3-连通立方图有{Cn|n≥5}-因子和{pn|n≥7}-因子.现给出这个猜想的证明.     

组合图中生成树的计数

经典理论矩阵树定理用于图中生成树的计数并不实用,但利用Chebyshev多项式的性质作为工具,结合Kel,malls和Chelnokov的结果,可以给出较简单的方法对很多图中的生成树进行精确计数．通过给出一些组合图中生成树的计数进一步体现了该技术在其中所起的作用．     

图的2-因子与图的上可嵌入性

结合图的4-边形2-因子条件,确定了一类新的上可嵌入图类,推广了黄元秋等早期在这方面的结果.并且综合已有结果,较完整地刻画了这类图的上可嵌入性.     

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

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