6色图顶点着色算法 [英] 6 Color Graph Vertex Coloring Algorithm

问题描述

我试图使一个算法在C ++中，将颜色的平面图形的顶点最多6种颜色。我只是在寻找一些伪code如何去了解这帮助我上手。任何帮助是AP preciated。谢谢你。

I'm trying to make an algorithm in C++ that will color the vertices of a planar graph with at most 6 colors. I was just looking for some pseudo code how to go about this to help me get started. Any help is appreciated. Thanks.

推荐答案

请参阅：

两个线性时间算法五，着色一个平面图 由大卫Matula，贝纳Shiloach，罗伯特·塔扬的

TWO LINEAR-TIME ALGORITHMS FOR FIVE-COLORING A PLANAR GRAPH by David Matula, Yossi Shiloach, Robert Tarjan

（只是谷歌这一点，你会发现文件的PDF）。

(Just Google this and you'll find a PDF of the paper).

所以这是一纸5着色为O（n）时间的平面图形，但它与一个算法的简单描述了6着色开始。这里是重要的提取物（道歉的格式，这仅仅是一个PDF刮）：

So this is a paper on 5-coloring a planar graph in O(n) time, but it starts with a simple description on an algorithm for 6-coloring. Here's the important extract (apologies for the formatting, this is just a PDF scrape):

算法的6色。给定一个n顶点的平面图G的邻接表   形式，本算法确定的G。步骤1. 6-着色〔建立   度的列表]对每个j，其中0-的J - N - 1，形成了双重＆LT; ＆LT;链接   的度数为j G的所有顶点的列表。    - 第2步：[标签顶点最小的程度为止。对于我= N，N - 1，N * - 1 ,. 。 。 ，1指定非空洞Ĵ度的第一个顶点   最小Ĵ顶点吨/我的列表。删除从第j度表六。   对于每一个顶点U，这是在相邻G将TLI，并保持在一定   度清单，说楼从JR度表，然后插入U'删除ü在   在J9 - 1度列表。第3步：[颜色顶点。]对于i = 1,2，... 。 。 ，   N，指定顶点T）我最小的颜色值（其中必须有一些   1和6之间的整数）不是发生在邻近的顶点   吨）i的已着色

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.

这篇关于6色图顶点着色算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！