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

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

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

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

几类图完美匹配的数目

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

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

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

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

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

3类图完美匹配数目的计算公式

图的完美对集计数问题已经被证实是NP—难问题,因此要得到一般图的完美对集的数目是非常困难的.该问题在蛋白质结构预测、量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.本文用划分、求和、再递推的方法分别给出了图2-nT_2,1-nDT_2和3-nDT_4的完美匹配数目的计算公式,所给出的方法可以计算出许多类图的所有完美匹配的数目.     

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

图的完美匹配计数问题已经被证实是NP—难的,因此要得到一般图的完美对集的数目是非常困难的。该问题在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义。用划分、求和、再递推的方法给出了图2-n D4,2-n C6,3和3-n C6完美匹配数目的计算公式。所给出的方法,可以计算出许多图类的所有完美匹配的数目,开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。     

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

用划分、求和、再递推的方法分别给出了图3-nK2,2,2和2-n4XC8的完美匹配数目的计算公式,所给出的方法可以计算出许多特殊图的所有完美匹配的数目,为图的完美匹配的应用提供了理论支持.     

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

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

5类特殊图完美匹配的计数

匹配计数理论是图论的核心内容之一.但是,一般图的完美匹配计数问题却是NP-难问题.文章用划分、求和、再递推的方法给出了5类图完美匹配数目的显式表达式,所给出的方法,可以计算出许多特殊图的所有完美匹配的数目.     

6类图完美匹配的数目

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

几类特殊图完美匹配数目的递推求法

匹配计数理论是图论的核心内容之一,此理论有很强的物理学和化学背景.但是,一般图的完美匹配计数问题却是NP-难问题.用划分、求和、嵌套递推的方法给出了几类图完美匹配数目的显式表达式.     

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

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

4类特殊图完美匹配的计数

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

2类图完美匹配数目的解析式

匹配计数理论是图论研究的重要内容之一,而且是一个有生机和活力的研究领域。它不仅有很强的应用背景,而且在过去的几十年中,它是快速发展的组合论中许多重要思想的源泉。但是,一般图的完美匹配计数问题却是NP-难问题。用划分,求和,再递推的方法给出了2类图完美匹配数目的计算公式,所给出的方法,可以计算出许多类图的所有完美匹配的数目。     

完美匹配树谱半径的进一步排序

用图的谱对图进行分类和排序是图谱理论的研究方向之一.主要研究了完美匹配树依谱半径排序的问题.事实上,到目前为止,具有前七大谱半径的完美匹配树已经排出,且具有第八大至第二十大谱半径的完美匹配树的范围也已经确定,但它们之间的大小顺序还没有具体给出.借助图的移接变形和图的特征多项式等工具,完整地解决了这一问题,具体排出了具有第八大至第二十大谱半径的完美匹配树.     

近完美匹配全覆盖点

利用匹配理论中的Gallai-Edmonds结构定理,首先得到了在一个有近完美匹配的图中判定一个顶点为近完美匹配全覆盖点的充要条件,然后对每一个顶点都为近完美匹配全覆盖点的图类给出了一个刻画.同时,也给出了一种构造这类图的方法.     

2类图完美匹配的数目

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

Tutte定理与Tutte-Berge公式的等价性证明

Tutte定理在匹配理论中占有中心位置,刻画了一般图有完美匹配的充分必要条件.Tutte-Berge公式是任意图上关于最大匹配的一个核心结果,确定了匹配数的一个最大最小关系,且提供了任意图中匹配数的一个紧的上界.Tutte定理常常被认为是Tutte-Berge公式的一个特殊情形.提供Tutte定理与TutteBerge公式的一个简单而完整的等价性证明,从而说明Tutte-Berge公式也是Tutte定理的一个特殊情形.作为Tutte公式的一个应用,考察并总结了任意正则图中是否具有完美匹配的情况,结果包含了著名的Petersen定理.     

简单图的最大匹配的几种矩阵求法

求一个简单图的最大匹配与完美匹配问题在经济生产中有着重要的实际意义。将求二分图的完美匹配转化为简化邻接矩阵问题来解决，将一般简单图的最大匹配问题转化为关联矩阵问题或求对偶图的邻接矩阵中阶最大主子式所在的行(列)的序号集问题，这不仅使矩阵工具在图论中得到了充分运用，而且这种方法用起来方便，又便于计算机处理。