【摘 要】
：
图G的r-边染色是指一个满射φ:E(G)→{1,2,…,r｝.边染色图G称为单色的,若图G的所有边都染有相同的颜色.边染色图G称为杂色的,若图G的任意两条边都染有不同的颜色.
Erd(o)
论文部分内容阅读
图G的r-边染色是指一个满射φ:E(G)→{1,2,…,r｝.边染色图G称为单色的,若图G的所有边都染有相同的颜色.边染色图G称为杂色的,若图G的任意两条边都染有不同的颜色.
Erd(o)s的一个简单而著名的注记表明任何2-边染色完全图Kn都有一棵单色支撑树.一个自然的推广题是:将r-边染色完全图Kn划分成尽可能少的点不交的单色树.Erd(o)s等人提出了r-边染色图的单色子图划分数的概念.对应于图的单色子图划分问题,Chen等人提出了r-边染色图的杂色树划分数的概念.边染色图的单色和杂色子图划分问题在图论研究中具有重要的理论意义,相关的研究日益引起众多研究者的兴趣.
本文主要研究边染色图的杂色子图划分问题,主要研究结果如下:
第一部分从算法的角度研究r-边染色完全二部图Km,n的杂色树划分问题,设计了一个多项式时间算法,它能在多项式时间内找到至多tr(Km,n)棵点不交的杂色树覆盖Km,n的所有顶点.
第二部分主要考虑r-边染色完全三部图的杂色树划分数问题,在第一部分完全二部图的结论基础上,继续研究完全三部图并得到了r-边染色完全三部图的杂色树划分数的精确表达式.
其他文献
本文主要研究随机延迟微分方程(SDDEs)解析解和数值解的p阶矩指数稳定性和几乎处处指数稳定性。通常情况下，我们用Lyapunov函数来研究随机微分方程(SDEs)和SDDEs的稳定性，但并
点集图形在许多课题中都有涉及,例如,特殊空间的点、数字照片中的像素、银河中的星球和空间数据等。并且,点集图形集重建是图形重建领域的一个非常重要的内容。假设平面中有
在实际问题的分析和研究过程中，为了更加准确地描述客观事物的变化规律，需要将众多的随机因素考虑在内，因此产生了随机微分方程这一重要的数学分支。随着科学家们的深入探索，随机
这篇硕士论文是作者在攻读硕士学位期间的主要研究成果.
在第二章，我们考虑如下具有Dirichlet边界条件的(p(x))，q(x))-Laplacian算子型拟线性椭圆方程组
的多解性问
课程改革的不断推进使得人们越来越注重素质教育,只有通过素质教育才能够培养出真正满足社会进步和时代发展要求的人才。体育对于学生身体健康的促进作用毋庸置疑,但是人们却
在本学位论文中,我们从两个方面研究了传染病在传播过程中发生突变的现象,其一是针对流感传播时发生突变的情形,其二是针对HIV-1病毒在体内感染健康细胞时发生突变的情形.通
In order to study the rules of distribution in a plastic zone of rocks, surrounding a roadway, affected by tectonic stress, we first analyzed the mechanics of a