排课表问题是图是否 可边着色的问题。即给定图 和正整数 ,问是否存在 的一种只用 种颜色的边着色,这是一个判定问题。
设图 ,任意给定色数参数 , 引入布尔变量。
=1(当边 染 种颜色), =0(当边 不染 种颜色)
共有k n个逻辑变量,显然每条边必须且只能染一种色。故对应 。
对图 上每一个顶点 所关联的 条边( | (1,2,…, )),对于第 种颜色 而言,至少有 -1条边不染 ,也即 =1。但 应取遍1至 ,每个顶点有 个子句。
( (1,2,…, ), , =1… )
图G是否可 色正常边染色当且仅当| | 个子句全都取真值,因此可满足可归纳成边染色判定问题,所以图是否 -可边着色问题是NP完全的[8]。
NP问题是一类不能用每一步都唯一确定的确定性算法来解决的计算难度较大的问题。目前NP问题还找不到一种有效的解法,如果对一个NP问题的输入即做些限制,问题就可以成为P,它可能有非常快的算法。另一方面,虽然加了些限制,但问题仍然是NP完全的[9]。
- 上一篇:整函数的阶型与零点+文献综述
- 下一篇:线性回归中最小二乘估计的改进
-
-
-
-
-
-
-
当代大学生慈善意识研究+文献综述
电站锅炉暖风器设计任务书
中考体育项目与体育教学合理结合的研究
java+mysql车辆管理系统的设计+源代码
乳业同业并购式全产业链...
河岸冲刷和泥沙淤积的监测国内外研究现状
酸性水汽提装置总汽提塔设计+CAD图纸
十二层带中心支撑钢结构...
大众媒体对公共政策制定的影响
杂拟谷盗体内共生菌沃尔...