无圈3-可着色平面图与置换图的重建算法

### 无圈3-可着色平面图与置换图的重建算法 #### 1. 无圈3-可着色平面图 在平面图的无圈3-可着色问题研究中，有诸多重要发现。对于SP图（具有特定极点u和v的图），其所有3-着色都是无圈的，当且仅当所有满足c(u) ≠ c(v)的3-着色是无圈的，并且所有满足c(u) = c(v)的3-着色也是无圈的。基于此特性，存在一个线性时间的识别算法来判断SP图的所有3-着色是否无圈。 - **定理5**：存在一个线性时间算法，用于判定一个SP图的所有3-着色是否无圈。 - **证明**：SP图G的SPQ - 树T可以在线性时间内计算得出。对于T中的每个节点μ，其极点为uμ和vμ，可赋予以下值： - G(μ)是否允许c(uμ) = c(vμ)的3 - 着色。 - G(μ)是否允许c(uμ) ≠ c(vμ)且uμ和vμ之间存在双色路径的3 - 着色；G(μ)是否允许c(uμ) = c(vμ)且uμ和vμ之间存在双色路径的3 - 着色；G(μ)是否允许uμ和vμ之间存在双色路径的3 - 着色。 - G(μ)中所有c(uμ) ≠ c(vμ)的3 - 着色是否无圈；G(μ)中所有c(uμ) = c(vμ)的3 - 着色是否无圈；G(μ)的所有3 - 着色是否无圈。 根据相关引理，计算μ的这些值只需对T中μ的子节点的类似值进行简单检查。 研究还证明了识别度为4的无圈3 - 可着色平面图是NP - 难的。同时，展示了无限类的次立方和立方平面图不存在无圈3 - 着色，这与除K4外所有立方平面图都有3 - 着色的事实形成对比。目前仍有一些开放问题： - 测试次立方图（或立方图）是否允许无圈3 - 着色的时间复杂度是多少？ - 是否存在无限数量的三连通、立方且非无圈3 - 可着色的平面图？ - 测试三连通立方平面图是否允许无圈3 - 着色的时间复杂度是多少？ - 是否可以在多项式时间内测试给定平面图的所有3 - 着色是否无圈？ - 使得所有围长至少为k的平面图都是无圈3 - 可着色的最小k值是多少？目前已知k的最佳下界是5，最佳上界是7。 #### 2. 置换图的重建算法 置换图的重建问题源于著名的图重建猜想。Kratsch和Hemaspaandra提出的原像构造问题，主要处理该猜想的算法方面。这里提出了一个O(n⁸)时间的算法，用于解决置换图的原像构造问题，其中n是输入图的数量。由于输入的每个图有n - 1个顶点和O(n²)条边，输入大小为O(n³)。 ##### 2.1 图重建猜想相关概念 - **图的甲板**：图G = (V, E)的甲板是多集{G - v | v ∈ V}，其中G - v是从G中移除v及其关联边得到的图，甲板中的图是无顶点标记的。 - **原像**：如果图G和G′具有相同的甲板，则G是G′甲板的原像。 - **图重建猜想**：对于给定的n个图（n ≥ 3），最多存在一个原像。虽然小图已被验证，但该猜想尚未得到肯定或否定的证明。 ##### 2.2 相关引理和已知结果 - **凯利引理**：设G是给定甲板的任何原像，H是顶点数小于G的图，则可以从甲板唯一确定G中与H同构的子图的数量。 - 格林威尔和亨明格将该引理扩展为更一般的形式。通过这些引理可以知道原像的度序列。凯利还证明了该猜想在正则图、树和不连通图上成立。图特证明了双色秩和图特多项式是可重建的。博洛巴斯表明几乎所有图都可以从其甲板中精心选择的三个图重建。对于置换图，Rimscha证明了置换图是可识别的，并且许多完美图的子类包括完美图本身都是可识别的，部分子类是可重建的。 ##### 2.3 算法问题 与图重建猜想相关的算法问题包括： - **甲板检查**：给定图G和图的多集D，检查D是否是G的甲板。 - **合法甲板判定**：给定图的多集D，确定是否存在甲板为D的图。 - **原像构造**：给定图的多集D，构造甲板为D的图。 - **原像计数**：给定图的多集D，计算甲板为D的（两两不同构）图的数量。 Kratsch和Hemaspaandra证明了这些问题在有界度图、部分k - 树（对于任何固定k）和有界亏格图（特别是平面图）上可以在多项式时间内解决。本文提出了一个O(n⁸)时间的算法，用于解决置换图的原像构造问题。 ##### 2.4 预备知识 - **符号表示**： - 图G的补图表示为G。 - 图G中由顶点子集V′诱导的图表示为G[V′]。 - 顶点v在图G中的邻域集表示为NG(v)，闭邻域集表示为NG[v]。 - 顶点u和v是强双胞胎，如果NG[u] = NG[v]；是弱双胞胎，