一种将布尔可满足性问题转化为3-着色问题的方法

本发明涉及计算机科学领域，尤其涉及一种将布尔可满足性问题（SAT）转化为3‑着色问题的方法。该方法通过特定的图结构和着色约束，将SAT公式中的变量和子句映射为图的顶点，并通过边表示逻辑约束，使得布尔公式的求解转化为图着色问题。本发明包括以下几个步骤：S1，读取SAT问题，初始化拓扑图的邻接矩阵；S2，设定固定着色点，将其与相关图顶点作必要连接；S3，按顺序每次选取两个SAT变量，在图中新增中间图顶点，并按照SAT中的逻辑关系和本发明设定的规则在图中连接；S4，循环进行S3直至所有变量的逻辑关系在图中具有完整的描述；S5，最终形成3‑图着色图。本发明提供的转化方法简化了SAT问题的结构，使其能够应用现有的图论算法，提供了大规模问题求解并行化能力的可能性，并使得解的可视化分析更加直观。该方法具有提高解的可视化程度以及简单快速转化的优点。