c++ - 6 色图顶点着色算法

Question

我正在尝试用 C++ 编写一个算法，该算法将使用最多 6 种颜色为平面图的顶点着色。我只是在寻找一些伪代码来帮助我开始。任何帮助表示赞赏。谢谢。

Answer 1

参见:

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

(只需 Google 一下，您就会找到该论文的 PDF 文件)。

所以这是一篇关于在 O(n) 时间内对平面图进行 5 着色的论文，但它首先是对 6 着色算法的简单描述。这是重要的摘录(对格式表示歉意，这只是一个 PDF 文件):

ALGORITHM 6 COLOR. Given an n vertex planar graph G in adjacency list form, this algorithm determines a 6-coloring of G. Step 1. [Establish degree lists.] For each j where 0- j - n - 1, form a doubly < < linked list of all vertices of G of degree j. - Step 2. [Label vertices smallest degree last.] For i = n, n - 1, n*- 1,. . . , 1 designate the first vertex of the non-vacuous j degree list of smallest j as vertex t/i. Delete vi from the j degree list. For each vertex U’ that was adjacent to tli in G and remains in some degree list, say f, delete u’ from the jr degree list and insert u’ in the j9 - 1 degree list. Step 3. [Color vertices.] For i = 1,2,. . . , n, assign vertex t)i the smallest color value (which must be some integer between one and six) not occuring on the vertices adjacent to t)i that have already been colored.