排序方式: 共有8条查询结果,搜索用时 156 毫秒
1
1.
研究了2-外平面图的无圈边染色问题.运用删点变换,得到了2-外平面图的结构性质;继而,运用数学归纳法,得到了图的一个无圈(Δ(G)+3)-边染色,即得到:若G是一个2-外平面图,则a’(G)≤Δ(G)+3. 相似文献
2.
本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$ ,其中$m$ 是机器数目。 相似文献
3.
本文研究具有加工次序约束的单位工件开放作业和流水作业排序问题,目标函数为极小化工件最大完工时间。工件之间的加工次序约束关系可以用一个被称为优先图的有向无圈图来刻画。当机器数作为输入时,两类问题在一般优先图上都是强NP-困难的,而在入树的优先图上都是可解的。我们利用工件之间的许可对数获得了问题的新下界,并基于许可工件之间的最大匹配设计近似算法,其中匹配的许可工件对均能同时在不同机器上加工。对于一般优先图的开放作业问题和脊柱型优先图的流水作业问题,我们在理论上证明了算法的近似比为$2-\frac 2m$ ,其中$m$ 是机器数目。 相似文献
4.
一个图G的无圈边染色是一个正常的边染色,使得任一个圈上至少有3种不同的颜色.G的无圈边色数a'(G)是使得G有无圈k-边染色的最小整数k.设G是一个最大度为4的外平面图.对于现有结果 4≤a'(G)≤5中,何时为4,何时为5,还没有一个完整的刻画.给出一个使得a'(G)=4的充分条件,拓展了该领域的相关结果. 相似文献
5.
图G的一个L(2,1)-标号是对G顶点集合的一个非负整数分配,使得其中相邻的点取得的整数差值至少为2并且距离为2的点取得不同的整数.L(2,1)-标号数就是所有这样的标号分配中最小的标号跨度值.Griggs和Yeh的[Labelling graphs with a condition at distance 2,SIAM J.Discrete Math.,1992,5:586-595]已经证明了,一棵树的L(2,1)-标号数不是△就是△+1.对于最大度为3的树的L(2,1)-标号数,本文给出了一个完全的刻画. 相似文献
6.
一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K4-图子式的图的无圈边色数. 相似文献
7.
8.
一个图G的无圈边染色是一个正常的边染色,使得不产生双色圈.Fiamˇcik和Alon等分别提出了著名的无圈边色数猜想:每一个简单图G是无圈边(Δ+2)可染的,其中Δ是G的最大度.证明了对于不含3圈和5圈相邻的平面图猜想成立. 相似文献
1