6色图顶点着色算法

Question

我试图在C++中创建一个算法，它将用最多6种颜色对平面图的顶点进行着色。我只是在寻找一些伪代码来帮助我开始工作。任何帮助都是非常感谢的。谢谢。

Answer 1

请参见：

五色平面图的两种线性时间算法: David Matula，Yossi Shiloach，Robert Tarjan

(只要在谷歌上搜索一下，你就会找到一份PDF格式的报纸)。

这是一篇关于在O(n)时间内5-着色平面图的论文，但它从一个6-着色算法的简单描述开始。以下是重要的摘录(对格式设置表示歉意，这只是一个PDF刮伤)：

算法6色。给出n个邻接表形式的顶点平面图G，该算法确定G的6-着色。步骤1。建立度表。对于每一个j，其中0- j-n- 1，形成一个双<链表的所有G的G度.-步骤2.标号顶点最小度.对于i= n，n- 1，n*- 1，。。，1指定最小j的非空j度列表的第一顶点为顶点t/i，从j次列表中删除vi。对于在G中与tli相邻且仍在某种程度列表中的每个顶点U‘，例如f，从jr度列表中删除u’并在j9 -1度列表中插入u‘。第三步颜色顶点。I= 1,2，。。，n，指定顶点t)i最小的颜色值(必须是1到6之间的整数)，在与t相邻的顶点上没有出现。

。