| 树的匹配覆盖 |
| |
| 引用本文： | 宋晓新,梁宏伟.树的匹配覆盖[J].郑州大学学报(理学版),2006,38(1):24-27,40. |
| |
| 作者姓名： | 宋晓新 梁宏伟 |
| |
| 作者单位： | 1. 河南大学数学与信息科学学院,河南,开封,475001;郑州大学数学系,郑州,450001
2. 河南大学数学与信息科学学院,河南,开封,475001 |
| |
| 基金项目： | 河南省教育厅自然科学基金资助项目,编号200510475038 |
| |
| 摘 要： | 设图G没有孤立点.图G的匹配覆盖数,记为mc(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{Δ0(G),Δ0(G) 1},其中Δ0(G)是指使得图G的某个顶点有l个一度邻点的l的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法.
|
| 关 键 词： | 匹配 匹配覆盖 悬挂度 |
| 文章编号： | 1671-6841（2006）01-0024-04 |
| 收稿时间： | 01 10 2005 12:00AM |
| 修稿时间： | 2005-01-10 |
Cover the Vertices of a Tree by Matchings |
| |
| SONG Xiao-xin,LIANG Hong-wei.Cover the Vertices of a Tree by Matchings[J].Journal of Zhengzhou University:Natural Science Edition,2006,38(1):24-27,40. |
| |
| Authors: | SONG Xiao-xin LIANG Hong-wei |
| |
| Institution: | 1. College of Mathematics and Information Science, Henan University, Kai feng 475001, China ; 2. Department of Mathematics ,Zhengzhou University ,Zhengzhou 450001 ,China |
| |
| Abstract: | The matching cover number of a graph G without isolated vertices,denoted by mc(G) ,is the minimum in teger k such that G has k matchings M1 ,M2 ,…,Mk that M1 ∪M2 ∪ … ∪Mk cover V(G). It is shown that if G is a tree, then mc(G) ∈ {△0 (G), △0 (G) +1 }, where△0 (G) is the maximum number l such that a certain vertex of G is adjacent to l vertices of degree 1.Moreover,given a tree G,the matching cover number of G can be determined by a linear-time algorithm. |
| |
| Keywords: | matching matching cover hang degree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
