摘要
图的1-因子计数问题已经被证明是NP-难的,但因该问题在量子化学、晶体物理学和计算机科学中都有重要的应用,对此问题的研究具有非常重要的理论价值和现实意义.首先,把图的1-因子按关联某个顶点的边进行分类,求出每一类1-因子数的递推关系式.其次,把各类1-因子的递推关系式相加,得到一组有相互联系的递推关系式,再利用这些递推关系式之间的相互关联,消去那些不需要的递推关系式,从而得到这个图的1-因子数的递推关系式.最后解出这个递推关系式的通解,进而得到这个图的1-因子数的显式公式.
The 1-factor counting problem of the graph has been proven to be NP-hard. Because this problem has important applications in quantum chemistry, crystal physics and computer science, the research on this problem has very important theoretical and practical significance. Firstly, the 1-factors of the graph are classified according to the edge associated with a certain vertex, and the recursive relation of the 1-factor number of each class is obtained. Secondly, the recursive relations of the various 1-factor are added, then a set of recursive relations with interrelation is obtained, and the reciprocal correlation between these recursive relations is used to eliminate the recursive relations that are not needed, and obtain the recursive relation of the 1-factor number of the graph. Finally, the general solution of this recursive relation is solved, and then the explicit formula of the 1-factor number of this graph is got.
作者
唐保祥
任韩
TANG Baoxiang;REN Han(School of Mathematics and Statistics, Tianshui Normal University, Tianshui 741001, China;Department of Mathematics, East China Normal University, Shanghai 200062, China)
出处
《大连理工大学学报》
EI
CAS
CSCD
北大核心
2019年第1期106-110,共5页
Journal of Dalian University of Technology
基金
国家自然科学基金资助项目(11171114)
关键词
1-因子
递推关系式
通解
显式公式
1-factor
recursive relation
general solution
explicit formula
