图顶点染色问题是一个被广泛研究的组合优化问题。在理论上图顶点染色问题已经被证明是NP难的。图顶点染色问题的研究不仅因为其计算的复杂性而具有学理价值,也因为其广泛的应用而具有实际应用价值。已有大量的实际应用问题被建模为图顶点染色问题加以求解。求解图顶点染色问题的算法大致分为两类。一类是近似染色算法,该类算法包括构造算法、局部搜索算法、进化算法,以及一些其他的启发式算法。另一类是精确染色算法。精确染色算法以遍历问题的搜索空间为基础,这导致其染色能力比近似算法弱。但精确方法能判定一个图不可用K种颜色染色的能力使其具有不可替代的价值。图顶点颜色问题的解空间随着顶点个数的增多指数级增长,这给精确图染色算法带来了巨大的挑战。因此为了提高精确图染色算法的性能,需要采取各种措施,尽最大可能地减小染色问题的搜索空间。通常,染色问题的顶点选择策略、单颜色传播方法、回溯方法和消除颜色对称性的方法是减小搜索空间的几种常见重要技术,具有重要的作用。论文以精确图顶点染色算法为介质,研究了K染色问题中蕴含的隐含约束关系。隐含约束关系能够描述不相邻接的顶点之间的染色约束。论文建立了隐含约束的描述方法,采用合取范式来编码隐含约束关系,详细讨论了隐含约束关系的发掘方法。论文以一个回溯搜索的图顶点精确染色算法backGCP为基础,详细研究了顶点选择策略、单颜色传播方法、回溯方法、消除颜色对称性的方法等重要技术。通过深入研究图顶点染色中的隐含约束关系,论文实现了基于冲突分析的动态发掘隐含约束关系的方法。这种模式既保持了顶点染色的原始结构特征,又高效利用了隐含约束关系的发掘、利用、管理等技术。新算法cdclGCP在隐含约束的指导下实现了智能的回溯操作,并且通过利用隐含约束,有效剪裁了染色问题的搜索空间。染色实验表明,通过发掘并利用隐含约束关系,改进后的算法cdclGCP能够显著剪裁染色问题的搜索空间。新算法在DIMACS测试库中获得了很好的染色结果,并且能够求证出一个开放DIMACS算例4-Fullins-5的色数。上述研究表明,隐含约束关系能够被用来剪裁顶点染色问题的搜索空间。虽然随机图中蕴含的隐含约束关系非常复杂,相应的学习过程以及维护管理大量的隐含约束的开销太大,这些因素使得算法染色过程变得更慢。但是对于结构图来说,冲突驱动隐含约束学习技术能够很好地利用图形的结构特征,使得到的隐含约束更短更有效,非常显著地改进了算法cdclGCP的染色性能。