平面图着色：一种启发式算法

"平面图着色的一个启发式算法" 本文主要介绍了一种启发式算法，用于解决平面图的着色问题。平面图着色是指给定一个平面图，使用尽可能少的颜色来给图的各个顶点着色，使得相邻的顶点颜色不同。这个问题在计算机科学和图论中具有重要意义，其复杂性属于NP-hard类别，意味着找到最优解通常是非常困难的。 该算法的基础是构建输入图G的最大独立集S。最大独立集是由不相邻的顶点组成的一个集合，使得集合中任意两个顶点之间没有边相连。在本文中，特别强调了S应包含出现在G的最大奇数圈数中的顶点。奇数圈是指有奇数条边的简单闭合路径。选择这样的顶点集合是为了优化着色过程，因为奇数圈的处理对于3-着色（使用三种颜色）是关键。 为了构建最大独立集S，算法采用输入平面图G的内面图Gf进行预序遍历。内面图指的是平面图在内部区域的边和顶点的表示。通过这种方式，算法能够识别并选择与最多奇数面相关的顶点。预序遍历是一种树遍历方法，它首先访问根节点，然后递归地遍历左子树和右子树，从而帮助构造部分极大独立集。这些部分独立集的并集即构成最大独立集S。 在得到最大独立集S之后，算法接着处理图G与S的补图GS。由于GS是多边形树，所以它是3-可着色的，这意味着可以用不超过三种颜色对其进行着色。通过对GS的着色，可以有效地解决原图G的关键顶点着色问题，从而逐步推进整个图的着色过程。 关键词涵盖了3-着色图、极大独立集、平面图以及独立路。3-着色图是指可以用三种颜色进行着色的图；极大独立集是图中最大的不相邻顶点集合；平面图是可以在平面上绘制且边不相交的图；独立路则是在图中不包含相邻顶点的路径。 这篇论文提出了一种利用最大独立集策略的启发式算法，用于解决平面图的着色问题，特别是在3-着色方面。这种方法试图通过优化特定结构来简化原本复杂的着色问题，为解决NP-hard问题提供了一种可能的实用途径。