几类图完美匹配的数目

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

2类图完美匹配的数目

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

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

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

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

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

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

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

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

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

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

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

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

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

5类图完美匹配的计数

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

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

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

四类图完美匹配的计数公式

用划分,求和,再递推的方法给出了四类图完美匹配数目的显式表达式.所给方法可以计算出许多二分图所有完美匹配的数目.     

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

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

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

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

4类图完美匹配数目的嵌套递推求法

用划分,求和再递推的方法分别给出了图3-n3LC4, 3-nBC4, 3-nL4和1-nXC4的完美匹配数目的计算公式,所给出的方法可以计算出许多特殊图的所有完美匹配的数目. 并利用所得到的计算公式计算出了一类图的Hamilton圈的数目.     

图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类图完美匹配数的计算

一般图的完美匹配计数问题是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.     

计算一类矩阵的积和式的改进算法及其应用

根据三次图的结构特点,在R-NW算法和Hybrid方法的基础进行改进,得到了一种更快的计算其邻接矩阵的积和式的方法,叫做F方法.并以实例验证了F方法的可行性.最后计算了一些二部图的二部邻接矩阵的积和式,进而得到它们的完美匹配的个数.