论文部分内容阅读
设图G没有孤立点.图G的匹配覆盖数,记为me(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{△0(G),△0(G)+1},其中△0(G)是指使得图G的某个顶点有z个一度邻点的z的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法.