10.3969/j.issn.1671-6841.2006.01.005
树的匹配覆盖
设图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的匹配覆盖数的线性算法.
匹配、匹配覆盖、悬挂度
38
O1(数学)
河南省教育厅自然科学基金200510475038
2006-08-16(万方平台首次上网日期,不代表论文的发表时间)
共5页
24-27,40