图的给定匹配数的离心率距离和

针对可预测生物和物理性质的图的不变量——离心率距离和,采用Tutte-Berge公式及图的转化方法,给出了图的给定匹配数的离心率距离和的紧下界,且完全确定了其极值图.     

图的伪对集

本文定义了图的伪对集是可以含有环的对集,给出了一个图有完美伪对集的充分必要条件并证明了有关最大伪对集的两个定理,从而推广了Tutte及Berge的对集定理。     

存在完美匹配4正则连通图的分类

本用Tutte定理对存在完姜匹配的4正则连通图给以明确分类,并由此得出关于4正则连通图完美(极大)匹配的一些重要性质．     

关于D-图的注记

为了研究具有完美匹配图的Tutte集和极端集,D Bauer等提出了一种新的图运算D-图,并且得到许多有趣的性质.本文研究了基本图的水平,证明了对于任何非二部的基本图,它的D~2(G)是一个完全图.此外,还给出了饱和图G的D-图的刻画,并且对于一般图的情形做出了分析.     

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

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

一类带号图构形的Tutte多项式

研究了带号曲轮图和带号双半轮图对应图构形的Tutte多项式,主要用带号图的删除-限制定理来计算其Tutte多项式,并运用带号图的符号转换函数找到了几种有规律的基本图形（基图）,推导出这些基本图形Tutte多项式的递推公式后,通过计算机辅助给出这类带号图的Tutte多项式,进而得到特征多项式及OS代数的维数。最后计算了半螺旋双吸泵3种不同内部结构的Tutte多项式。     

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

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

循环图C_(2n)(1,2n/3)的2-偶匹配可扩性

根据图论中的Tutte定理、循环图的BM-可扩性、Hamilton图等理论关于完美匹配的刻画,详细的证明了循环图C2n(1,2n/3)当n=3,6,9时的2-偶匹配可扩性。     

Green公式及其证明

首先指出数学分析中反映二重积分和第二类平面线积分联系的Green公式可以看成是散度定理的一种特殊情形，然后利用散度定理给出广义分部积分公式、第一Green公式和第二Green公式的证明．     

完美图在超图上的推广

由完美图知道,如果图G和它的每一个诱导子图均满足其色数x等于其最大团的基数ω,则图G是完美的。在这篇论文中,定义了弱k-完美超图和强k-完美超图。在这个定义之下,完美图是超图的一个特殊情况。进一步,讨论了弱k-完美超图和强k-完美超图的性质,并且得出了一个定理,该定理不能由Lovasz的相应定理直接推广而来。     

Green公式及其证明

首先指出数学分析中反映二重积分和第二类平面线积分联系的Green公式可以看成是散度定理的一种特殊情形，然后利用散度定理给出广义分部积分公式、第一Green公式和第二Green公式的证明．     

3类3-正则图中的完美匹配数

完美匹配的计数理论在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.但是,一般图的完美匹配计数问题已经被证实为NP-难问题.Lova'sz和Plummer曾提出关于完美匹配计数的一个猜想:任意2-边连通3-正则图都有指数多个完美匹配.本文用划分、求和再嵌套递推的方法给出了3类特殊图完美匹配数目的显式表达式,从而验证了Lova'sz和Plummer猜想在这3类图上的正确性.     

图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的完美匹配按匹配一个固定顶点的边进行分类, 先求出每类完美匹配数目的递推关系式, 得到一组有相互联系的递推关系式, 再利用这组递推式之间的相互关系, 给出这两个图完美匹配数的计数公式.     

无K3子图的图中1-因子计数

1-因子或完美匹配的计数是NP-难的,利用S~((n))-因子的表示公式和分支分析方法研究1-因子或完美匹配具有理论和实际意义.首先,得到无K_3子图的图中1-因子计数公式和组合恒等式;其次,导出1-因子或完美匹配存在和不存在的充分必要条件;最后,得出一个结论:存在连通图使得它的1-因子的个数大于任意的自然数N.     

若干四角系统完美匹配数的计算

图的完美匹配的计数问题是匹配理论研究中的一个重要课题,而对于一般图的完美匹配计数问题是NP-难的.本研究运用组合递推法给出了几类四角系统的完美匹配数的显式表达式.     

几类图完美匹配的数目

图的完美匹配的计数问题是匹配理论研究中的一个重要课题,此问题与统计晶体物理中的dimmer问题有关.一般图的完美匹配计数问题是NP-难的.本文给出了几类图的完美匹配数的显式表达式.作为应用,计算出了一些图的Hamilton圈的数目.     

PM紧邻极值Brick

图G中所有完美匹配的关联向量,通过整数线性组合形成的空间,称为图的匹配格.若匹配覆盖图满足G完美匹配数等于匹配格的维数,则称其为匹配覆盖极值图.当图任意去掉两个点不交的匹配交错圈后,剩下的图无完美匹配,则称该图满足PM紧邻.本文证明了所有极值brick均为PM紧邻.     

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

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

两类图完美匹配数的递推计算

利用划分、求和再嵌套递推法研究了两类特殊图的完美匹配计数问题,给出了图3-nC_(6,3)和3-nP_(2,4)的完美匹配数的计算公式.所给出的方法可以计算出许多类图的所有完美匹配的数目,为图的完美匹配问题的应用提供了理论支持.