| 唐保祥,任韩.两类特殊图1-因子数分类递推求法[J].,2019,59(1):106-110 |
| 两类特殊图1-因子数分类递推求法 |
| Classification and recursive method for 1-factor number of two kinds of special graphs |
| |
| DOI：10.7511/dllgxb201901014 |
| 中文关键词: 1-因子 递推关系式 通解 显式公式 |
| 英文关键词: 1-factor recursive relation general solution explicit formula\@ |
| 基金项目:国家自然科学基金资助项目(11171114). |
|
| 摘要点击次数: 788 |
| 全文下载次数: 618 |
| 中文摘要: |
| 图的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. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
|
|
|