|
|||||
|
|
| 一类二分图的k-匹配数 | |
| 引用本文： | 陈佘喜,虞锦萍,刘建勋.一类二分图的k-匹配数[J].数学的实践与认识,2010,40(3). |
| 作者姓名： | 陈佘喜 虞锦萍 刘建勋 |
| 作者单位： | 1. 湖南科技大学知识处理与网络化制造湖南省普通高校重点实验室,湖南湘潭411201;湖南科技大学数学与计算科学学院,湖南湘潭411201 2. 湖南科技大学数学与计算科学学院,湖南湘潭,411201 3. 湖南科技大学知识处理与网络化制造湖南省普通高校重点实验室,湖南湘潭,411201 |
| 基金项目： | 国家自然科学基金(90818004,60673119) |
| 摘 要： | 设G是一个具有二分类(X_1,X_2)的简单偶图,|X_1|=|X_2|=n,如果对于给定的c>0,|M(S)|≥(1+c)|S|对任意满足|S|≤n/2的S(?)X_i(i=1,2)都成立,其中N(S)是S的邻集,则称G是(n,c)-扩张图.给出了(n,c)-扩张图的k-匹配数与完美匹配数之比的顺从界. |
| 关 键 词： | 二分图 匹配 交错路 |
The Number of k-Matchings of A Type of Bigraphs |
|
| CHEN She-xi,YU Jin-ping,LIU Jiang-xun.The Number of k-Matchings of A Type of Bigraphs[J].Mathematics in Practice and Theory,2010,40(3). | |
| Authors: | CHEN She-xi YU Jin-ping LIU Jiang-xun |
| Institution: | CHEN She-xi~(1,2),YU Jin-ping~2,LIU Jiang-xun~1 (1.Key Laboratory of Knowledge Processing , Networked Manufacturing,College of Hunan Province,Hunan University of Science , Technology,Xiangtan 411201,China) (2.School of Mathematics , Computational Science,China) |
| Abstract: | Given c>0,an(n,c)-expander is a simple bigraph with bipartition(X_1,X_2) and |X_1|= |X_2| = n,such that |N(S)|≥(1+c)|S| for every S(?) X_i(i=1,2) with |S|≤n/2,where N(S) is the neighbour set of S.In this paper,amenable bounds on the ratios of the number of k-matchings to the number of perfect matchings of an(n,c)-expander are obtained. |
| Keywords: | bigraph matching alternating path |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |