| 关于图的运算与图的Pfaffian性 |
| |
| 引用本文： | 林峰根,张莲珠,卢福良.关于图的运算与图的Pfaffian性[J].数学研究,2011,44(2):148-159. |
| |
| 作者姓名： | 林峰根 张莲珠 卢福良 |
| |
| 作者单位： | 厦门大学数学科学学院,福建厦门,361005 |
| |
| 基金项目： | supported by NSFC(10831001) |
| |
| 摘 要： | 关于一般的图的完美匹配计数的问题已证实是NP-hard问题.但Pfaffian图的完美匹配计数问题(以及其它相关问题)却能够在多项式时间内解决.由此可见图的Pfaffian性的重要性.在这篇文章中,我们研究了若干种影响图的Pfaffian性的运算.
|
| 关 键 词： | Pfaffian图 运算 完美匹配 |
Operations Effecting Pfaffian Property of Graphs |
| |
| Lin Fenggen,Zhang Lianzhu,Lu Fuliang.Operations Effecting Pfaffian Property of Graphs[J].Journal of Mathematical Study,2011,44(2):148-159. |
| |
| Authors: | Lin Fenggen Zhang Lianzhu Lu Fuliang |
| |
| Institution: | Lin Fenggen Zhang Lianzhu Lu Fuliang (School of Mathematical Sciences Xiamen University,Xiamen Fujian 361005) |
| |
| Abstract: | It is well known that enumeration problem of perfect matchings for general graphs is NP-hard.The importance of Pfaffian orientations stems from the fact that if a graph G is Pfaffian, then the number of perfect matchings of G(as well as other related problems) can be computed in polynomial time.In the present paper,we DISCUSS some operations on graphs and examine their effect on the Pfaffian property of graphs. |
| |
| Keywords: | Pfaffian graphs Operations Perfect matchings |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
