摘要
称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配。判定图是否含有基数为k的偶匹配是NP-困难问题,该文主要刻画了循环图C_(2n)(1,4)的k-偶匹配可扩性。
G is said to be bipartite matching-extendable,if every bipartite matching M of is included in a perfect matchingof G . The problem determining whether there is a bipartite matching of cardinality k in a graph G is NP-complete. This papershows that the k-bipartite matching extendability of circulant graphs C2n（1,4） .
出处
《计算机与数字工程》
2017年第11期2097-2098,2196,共3页
Computer & Digital Engineering
基金
平顶山学院青年科研基金项目(编号:2012001)
河南省科技厅重点科技攻关项目(编号:132102310126)资助
关键词
完美匹配
偶匹配可扩
k-偶匹配可扩
循环图
pefrect matching,bipartite matching,k-bipatrite matching extendable,circulant graph
