树的匹配覆盖

来源 :郑州大学学报：理学版 | 被引量 : 0次 | 上传用户：BarDy

【摘要】

：

设图G没有孤立点．图G的匹配覆盖数，记为me（G），是指满足如下条件的最小正整数k：G有k个匹配M1，M2，…，Mk覆盖图G的所有顶点．证明了如果图G是一个树，则mc（G）∈{△0（G），△0（G）＋1}，其中△0（G）是指使得图G

【作者】

：

宋晓新梁宏伟

【机构】

：

河南大学数学与信息科学学院,郑州大学数学系

【出处】

：

郑州大学学报：理学版

【发表日期】

：

2006年1期

【关键词】

：

匹配匹配覆盖悬挂度 matching matching cover hang degree

【基金项目】

：

河南省教育厅自然科学基金资助项目,编号200510475038. Acknowledgment The authors would like to express their hearty thanks to Prof. Yuan Jinjiang for many useful suggestions.

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

设图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的匹配覆盖数的线性算法．

其他文献

Wehrl熵表征介观RLC电路量子效应的研究

首先利用信息测量理论中的Wehrl熵，给出热场中谐振子系统的Wehrl熵，然后将介观RLC电路等效成热谐振子，研究介观RLC电路在热真空态下量子效应和Wehrl熵之间的关系．结果表明，Wehrl熵

期刊

WEHRL熵热谐振子介观RLC电路量子涨落Wehrl entropy thermal harmonic oscillator mesoscopic

卡塔兰数的一个几何模型

明安图是清代一位杰出的蒙古族数学家和天文学家，他去世后他的遗著《割圆密率捷法》，由他的学生在1774年完成，并且在1839年出版了这部著作．指出了明安图是世界上第一位卡塔兰数的

期刊

明安图E.Catalan卡塔兰数无穷级数几何模型Ming Antu E. Catalan Catalan numbers infinite se

介观LC电路数-相空间的量子涨落

从电路系统的Lagrange量人手，利用数-相量子化方案，将介观LC电路量子化，得到了数一相算符表示的Hamiltonian，研究了真空态和压缩真空态下电路中电荷数和相位差的量子涨落．结果表明

期刊

介观LC电路数-相量子化量子涨落mesoscopic LC circuit number-phase quantization quantum flu

多指标预测模型的纠偏组合预测模型

在各个多指标模型具有系统偏差和尺度偏差的情况下，在正态分布前提下给出了多指标待预测向量的贝叶斯极大似然估计．该估计纠正了系统偏差和尺度偏差，且为一种多个多指标预测模型

期刊

多指标预测模型组合预测纠偏估计贝叶斯估计forecast model with multiple indexes combinatorial fore

局部分析方法在可解群中的应用

局部分析方法是有限群理论最基本的方法，利用可解群的性质和有限群的基本定理，通过局部分析方法，研究了可解群和可解子群的一些性质．利用成分的性质及Thompson A×B引理，得到

期刊

有限群可解群P-子群中心化成分finite group solvable group p-subgroup centralization~ co

密度函数的小波估计及其影响函数

把小波的思想和方法应用到统计学的密度估计中，得到了密度小波估计的一个统一的非迭代表示形式．对于给定的一种系数估计方法，这种表示形式容易计算密度估计的影响函数，进而可以进

期刊

密度函数小波影响函数density estimation wavelet influence function

属性识别模型在质量评价中的应用

针对模糊隶属度不满足“归一条件”及“可加性原则”而导致评价结果不准确甚至错误的问题,将属性识别模型理论与模型运用于质量评价,并通过实例验证了该模型和方法的合理性和

期刊

属性集属性识别质量评价attribute set attribute recognition quality assessment

一类具有反馈控制参数的时变分岔

采用Hopf分岔方法研究了一类具有反馈控制参数的时变分岔问题,其主要研究目的是判断这类问题周期解的存在性与稳定性,其周期解取决于非完全参数和时变控制参数,并且在适当的

期刊

时变分岔HOPF分岔非完全参数反馈控制time-varying bifurcation Hopf bifurcation imperfect par

一类广义Sierpinski地毯的Hausdorff测度

得到正方形上一类Sierpinski地毯En的等价构造,即为一类六边形上的Sierpinski地毯Qn;通过在Qn上定义一个质量分布,由质量分布原理得到下界,从而完全确定了En的Hausdorff测度

期刊

分形HAUSDORFF测度SIERPINSKI地毯fractal Hausdorff measure Sierpinski carpet

基于URL类型和网页链接变化的信息采集更新算法

通过观察网站呈现网页的规律及网页本身的结构特点，提出基于URL类型及网页链接变化规律的入口页面识别算法，优先抓取入口页面．在实际应用中，取得了较好的更新效果．

期刊

入口页面网页更新增量采集entry page page refreshment incremental crawler

树的匹配覆盖

与本文相关的学术论文