图的染色问题在排课表中的应用+文献综述(4)
排课表问题是图是否 可边着色的问题。即给定图 和正整数 ，问是否存在 的一种只用 种颜色的边着色，这是一个判定问题。
设图 ,任意给定色数参数 , 引入布尔变量。
=1(当边 染 种颜色)， =0（当边 不染 种颜色）
共有k n个逻辑变量，显然每条边必须且只能染一种色。故对应 。
对图 上每一个顶点 所关联的 条边（ | (1,2,…, )）,对于第 种颜色 而言，至少有 -1条边不染 ，也即 =1。但 应取遍1至 ，每个顶点有 个子句。
（ (1,2,…, ), , =1… ）
图G是否可 色正常边染色当且仅当| | 个子句全都取真值，因此可满足可归纳成边染色判定问题，所以图是否 -可边着色问题是NP完全的[8]。
NP问题是一类不能用每一步都唯一确定的确定性算法来解决的计算难度较大的问题。目前NP问题还找不到一种有效的解法，如果对一个NP问题的输入即做些限制，问题就可以成为P，它可能有非常快的算法。另一方面，虽然加了些限制，但问题仍然是NP完全的[9]。
上一篇：整函数的阶型与零点+文献综述
下一篇：线性回归中最小二乘估计的改进