| 杨利民,年四洪.无 K3子图的图中1-因子计数[J].,2021,61(5):546-550 |
| 无 K3子图的图中1-因子计数 |
| Counting of 1-factors in graphs without K3 subgraphs |
|
| DOI：10.7511/dllgxb202105014 |
| 中文关键词:N(G，k)色多项式S(n)-因子1-因子 |
| 英文关键词:N(G, k)chromatic polynomialS(n)-factor1-factor |
| 基金项目:大理大学高层次人才科研启动基金资助项目(KY0719203410). |
|
| 摘要点击次数:215 |
| 全文下载次数:129 |
| 中文摘要: |
| 1-因子或完美匹配的计数是NP 难的，利用S(n)-因子的表示公式和分支分析方法研究1-因子或完美匹配具有理论和实际意义．首先，得到无K3子图的图中1-因子计数公式和组合恒等式；其次，导出1-因子或完美匹配存在和不存在的充分必要条件；最后，得出一个结论：存在连通图使得它的1-因子的个数大于任意的自然数N． |
| 英文摘要: |
| It is NP hard to count 1-factor or perfect matching. It is of theoretical and practical significance to study 1-factor or perfect matching by using representation formula and branch analysis method of S(n)-factor. Firstly, the counting formulas and combinatorial identities of 1-factors in graphs without K3 subgraphs are obtained. Secondly, the necessary and sufficient conditions for the existence and nonexistence of 1-factors or perfect matching are derived. Finally, a conclusion is given that there exists a connected graph such that the number of 1-factors is greater than any natural number N. |
| 查看全文查看/发表评论下载PDF阅读器 |
| --> | 关闭 |
优惠券领取后72小时内有效，10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材，产品类型包含电子书、题库、全套资料以及视频，无论您是考研复习、考证刷题，还是考前冲刺等，不同类型的产品可满足您学习上的不同需求。 ...考试优惠券 本站小编 Free壹佰分学习网 2022-09-19