平面图的变换与着色的性质

Moves and Coloring Properties for Planar Graph

摘要: 本文研究了平面图着色的性质，给出了平面图的变换，包括树形变换、三角形变换(n-圈变换)和桥变换等，并且利用图的双色多项式证明了这些变换不改变着色数，进而研究了某些平面图的着色性质。

Abstract: This paper studies the coloring properties of planar graph, gives their moves including tree-move triangle-move (n-circle-move), bridge-move, and proves that these moves don’t change coloring number by using dichromatic polynomial. Furthermore, the coloration of some planar graphs is studied.

1. 引言

纽结理论的核心问题之一就是分类，不论是早期的Alexander多项式 [1]、Conway多项式 [2] 到上个世纪八十年代的中后期的Jones多项式 [3] 在纽结分类中发挥了重要的作用，推进了纽结理论和相关领域的发展。Kauffman [4] 一般化了Jones多项式，给出了Jones多项式存在比较初等的数学证明，同时利用这些方法证明了纽结理论中泰特猜想。随着纽结理论研究的深入，其研究成果和方法在统计力学 [3] [5] 和生物DNA分子重组 [6] 等领域都得到了广泛的应用，而且促进了这些领域的发展，特别是Kauffman [4] 还发现了纽结理论与图论有着密切的联系，即纽结的投影图与它的平面图是一一对应的，因此建立了纽结多项式和平多图多项式的联系，进而将图论的有些研究与纽结理论研究结合在一起，把平面图着色的问题转化为多项式根的性质，因此为平面图着色问题的研究提出新的方法，充分体现了纽结理论发展的活力。

本文分为二个部分，第一部分主要介绍了平面图基本概念和性质，特别是给出图的双色多项式的性质和本文需要的一些结果。第二部分给出了图的变换，主要是研究了平面图在这些变换下着色的不变性。

2. 预备知识

定义2.1 一个图是一个二元组，这个二元组包含一个顶点集 $V\left(G\right)$，一个边集 $E\left(G\right)$ 使得每一条边和两个顶点相关联，不同的两边不能相交非顶点，并将这两个顶点称为这条边的端点。如果 $V\left(G^{\prime }\right)\subseteq V\left(G\right)$， $E\left(G^{\prime }\right)\subseteq E\left(G\right)$，那么称图 $G^{\prime }$ 为图G的子图。

定义2.2 设n是一个正整数，定义一个n-弧是一个包含n条边， $n+\text{1}$ 个顶点的图，满足下面的性质：将边记为 $A_1,A_2,\cdots A_n$，顶点记为 $a_0,a_1,\cdots ,a_n$，对于每一个j， $A_j$ 的端点是 $a_{j-1}$ 和 $a_j$。图1是3-弧。

Figure 1. 3-arc

图1. 3-弧

定义2.3 设n是一个正整数，一个n-圈定义为一个包含n个顶点和n个边的图G，满足下面的性质：顶点记为 $a_0,a_1,\cdots ,a_n$，边记为 $A_1,A_2,\cdots A_n$，对于每一个j， $A_j$ 的端点是 $a_{j-1}$ 和 $a_j$ (这里 $a_0=a_n$ )。图2是4-圈。如果一个图中没有圈，并且是连通的，则称为树形。

Figure 2. 4-loop

图2. 4-圈

定义2.4 设G和H是两个图，f是一个一一映射，将 $V\left(G\right)$ 映到 $V\left(H\right)$，g也是一个一一映射将 $E\left(G\right)$ 映到 $E\left(H\right)$， $\theta =\left(f,g\right)$。称 $\theta$ 是G到H的同痕，如果满足下面的性质：任意的顶点x是边A的端点当且仅当 $f\left(x\right)$ 是边 $g\left(A\right)$ 的端点。如果这样的同痕映射 $\theta$ 存在，则称图G和图H是同痕的。

注：图论一般研究的就是同痕图的一些性质，本文中的图都是指在平面中的图，因此也可以称为平面图。其实下面的很多讨论对三维空间的图也是成立的。

定义2.5 纽结是 $S^3$ 空间中与 $S^1$ 同胚的简单闭曲线；环链就是 $S^3$ 中由若干互不相交纽结组成的子空间。

纽结的Alexander多项式、Conway多项式和Jones多项式等都是可以通过纽结的投影图来进行计算的，由于它们都纽结的同痕不变量，所以与投影图的选取是无关的。而投影图就与平面图有着密切的关系。

首先介绍图的双色多项式 $Z\left(G\right)$ [1] [3]，它有两个变量q和v，满足下面三个条件：

(1) $Z\left({•}_{}^{}G\right)=q$

(2) $Z\left({•}_{}^{}G\right)=qZ(\; G\; )$

(3) $Z$ () $=Z$ () $+vZ$ ()

引理2.1 [7] 在双色多项式 $Z\left(q,v\right)$ 中，当 $v=-1$ 时，双色多项式特殊化为色多项式 $P\left(G\right)$。 $P\left(G\right)$ 表示对图G的顶点用q种颜色着色，并保证相邻的两个顶点不同色的着色的方法数目。

例子：Z () $=q^3+3v{q}^2+3v^{2}q+v^{3}q$，当 $v=-1$ 时， $P\left(G\right)=q^3-3q^2+2q=q\left(q-1\right)\left(q-2\right)$ 恰好是平面图三角形着色数目。

引理2.2 [8] 如果图G是子图H和K的不交并，那么 $P\left(G\right)=P\left(H\right)P\left(K\right)$。

引理2.3 [8] 如果图G是子图H和K的并，满足 $H\cap K$ 是一个顶点，那么

$qP\left(G\right)=P\left(H\right)P\left(K\right)$。

3. 平面图的变换及其着色性质

这部分给出平面图的变换，利用双色多项式来研究这些变换对平面图着色性质的变化情况。

3.1. 树形变换的着色问题

先看一下一种特殊树形——“m-弧变换”的情形，可以得到：

命题3.1 设图 $G_n$ 是由G添加m-弧 $L_m$ 构成，且 $L_m\cap G^{\prime }$ 是一个顶点，则当 $q\ge 2$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G_{n-1}\right)\ne 0$。

证明 首先考虑 $m=1$，则 $G_n$ 是由 $G_{n-1}$ 添加1-弧构成(见图3)。

Figure 3. 1-arc

图3. 1-弧图

由计算可得， $Z\left(G_n\right)=Z$ () $+vZ\left(G_{n-1}\right)=qZ\left(G_{n-1}\right)+vZ\left(G_{n-1}\right)=\left(q+v\right)Z\left(G_{n-1}\right)$。

由引理2.1可知，当 $v=-1$ 时， $P\left(G_n\right)=\left(q-1\right)P\left(G_{n-1}\right)$，所以 $q\ge 2$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G_{n-1}\right)\ne 0$。其次，一般情形计算有， $Z\left(G_n\right)={\left(q+v\right)}^{m}Z\left(G^{\prime }\right)$，当 $v=-1$ 时， $P\left(G_n\right)={\left(q-1\right)}^{m}Z\left(G^{\prime }\right)$，所以， $q\ge 2$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G_{n-1}\right)\ne 0$。从而结论成立。

定理3.1 设图 $G_n$ 由 $G^{\prime }$ 添加树 $T_m$ 得到，其中 $T_m$ 有m个顶点， $T_m\cap G^{\prime }$ 是一个顶点(见图4)，则当 $q\ge 2$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。

Figure 4. Tree

图4. 树形图

证明 利用命题3.1，由归纳法， $Z\left(G_n\right)={\left(q+v\right)}^{m-1}Z\left(G^{\prime }\right)$，当 $v=-1$ 时， $P\left(G_n\right)={\left(q-1\right)}^{m-1}P\left(G^{\prime }\right)$，所以 $q\ge 2$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。从而结论成立。

注 图 $G^{\prime }$ 是有G去掉树形得到的，把这种变换称为树形变换，该定理这说明树–变换不改变图的着色数。

3.2. “m–圈–变换”的着色问题

命题3.2 设图 $G_n$ 由 $G_{n-1}$ 添加一个3-圈P得到， $G_{n-1}\cap P$ 是一个顶点(见图5)，则当 $q\ge 3$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G_{n-1}\right)\ne 0$。

Figure 5. Graph with 3-loop

图5. 带3-圈的图

证明 通过计算可得： $Z\left(G_n\right)=\left[\left(q+2v\right)\left(q+v\right)+v^2\left(v+1\right)\right]Z\left(G_{n-2}\right)$，当 $v=-1$ 时， $P\left(G_n\right)=\left(q-2\right)\left(q-1\right)P\left(G_{n-1}\right)$，所以， $q=3$ 时， $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G_{n-1}\right)\ne 0$。从而结论成立。

定理3.2 设图 $G_n$ 由 $G^{\prime }$ 添加一个m-圈P得到， $G^{\prime }\cap P$ 是一个顶点(见图6)，则有

(1) 当m是偶数时，如果 $q\ge 2$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$ ；

(2) 当m是奇数时，如果 $q\ge 3$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。

证明

$\begin{array}{c}Z\left(G_n\right)=Z\left(G^{\prime }\cup T_m\right)+vZ\left(G^{\prime }\cup P_{m-1}\right)\\ =\left[{\left(q+v\right)}^{m-1}+v{\left(q+v\right)}^{m-2}+\cdots +v^{m-3}{\left(q+v\right)}^2\right]Z\left(G^{\prime }\right)+v^{m-2}Z\left(G^{\prime }\cup P_1\right)\\ =\left[{\left(q+v\right)}^{m-1}+v{\left(q+v\right)}^{m-2}+\cdots +v^{m-2}\left(q+v\right)\right]Z\left(G^{\prime }\right)+v^{m-1}Z\left(G^{\prime }\cup P_1\right)\\ =\left[{\left(q+v\right)}^{m-1}+v{\left(q+v\right)}^{m-2}+\cdots +v^{m-2}\left(q+v\right)+v^{m-1}\left(v+1\right)\right]Z\left(G^{\prime }\right)\\ =\left[\frac{{\left(q+v\right)}^{m-1}\left[1-{\left(\frac{v}{q+v}\right)}^{m-1}\right]}{1-\frac{v}{q+v}}+v^{m-1}\left(v+1\right)\right]Z\left(G^{\prime }\right)\\ =\left[\frac{\left(q+v\right)\left[{\left(q+v\right)}^{m-1}-v^{m-1}\right]}{q}+v^{m-1}\left(v+1\right)\right]Z(\; G\; \prime \; )\end{array}$

当 $v=-1$ 时， $P\left(G_n\right)=\frac{q-1}{q}\left[{\left(q-1\right)}^{m-1}-{\left(-1\right)}^{m-1}\right]P\left(G^{\prime }\right)$，所以，当m是偶数时，

$P\left(G_n\right)=\left(q-1\right)\left[{\left(q-1\right)}^{m-1}+1\right]P\left(G^{\prime }\right)$，此时，如果 $q\ge 2$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。当m是奇数时，

$P\left(G_n\right)=\left(q-1\right)\left[{\left(q-1\right)}^{m-1}-1\right]P\left(G^{\prime }\right)$。此时，如果 $q\ge 3$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。从而定理的结论成立。

Figure 6. Graph with m-loop

图6. 带m-圈的图

注 如果把“m-圈-变换”称为三角形变换，该定理说明三角形变换不改变图的着色数。

推论3.1 设图 $G_n$ 仅有一个m-圈， $G_n$ 余下的部分是树 $T_n$，其中 $G_n$ 有n顶点，则有

(1) 当m是偶数时，如果 $q\ge 2$，则 $P\left(G_n\right)\ne 0$ ；

(2) 当m是奇数时，如果 $q\ge 3$，则 $P\left(G_n\right)\ne 0$。

证明 首先看一个特殊情形，设图 $G_n$ 仅有一个3-圈， $G_n$ 余下的部分是树 $T_n$，其中 $G_n$ 有n个顶点(见图7)，由定理3.1可知，树形不改变着色数，所以， $P\left(G_n\right)=P\left(3\text{-}圈\right)=P\left(三角形\right)$，从而当 $q=3$ 时，结论成立。

Figure 7. Graph of 3-loop

图7. 3-圈的图

对于一般情形有 $P\left(G_n\right)=P\left(m\text{-}圈\right)=P\left(多边形\right)$，由定理3.1和定理3.2，结论成立。

3.3. 桥变换的着色问题

命题3.3 设 $G_n$ 存在m条有相同端点的边 $l_k\left(k=1,\cdots ,m\right)$，去掉其中 $m-1$ 条边后的图记为 ${G^{\prime }}_n$，则 $P\left(G_n\right)=P\left({G^{\prime }}_n\right)$。

证明 如果图 $G_n$ 的两个顶点 $x,y$ 存在两个相同端点的边，去掉其中一条重复边后的图记为 ${G^{\prime }}_n$ (见图8)， $Z\left(G_n\right)=Z\left({G^{\prime }}_n\right)+vZ$ () $=Z\left({G^{\prime }}_n\right)+v\left(1+v\right)Z$ ()，当 $v=-1$ 时， $P\left(G_n\right)=P\left({G^{\prime }}_n\right)$。一般情形同理可证。

Figure 8. Graph of multiple edges

图8. 带多重边的图

注 该命题说明在图中如果有两个顶点多重边相连，就可以看成只有一个边相连，这样不改变着色数。如图8中， $G_n$ 经过这种变换得到 ${G^{\prime }}_n$，称这种变换为桥变换。从而说明桥–变换不改变图的着色性质。

定理3.3 设图 $G_n$ 由 $G^{\prime }$ 添加m-弧 $L_m$ 得到， $G^{\prime }\cap L_m$ 是 $L_m$ 的两个端点(见图9)，则有

(1) 当m为奇数时，如果 $q\ge 3$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$ ；

(2) 当m为偶数时，如果 $q\ge 2$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。

Figure 9. Graph with bridge

图9. 带桥的图

证明： $Z\left(G_n\right)=Z$ () $+vZ$ ()

$=\left[{\left(q+v\right)}^m+v{\left(q+v\right)}^{m-1}+v^2{\left(q+v\right)}^{m-2}+\cdots +v^{m-1}\left(q+v\right)\right]Z\left(G^{\prime }\right)+\left(1+v\right)Z(\; G\; ″\; )$

当 $v=-1$ 时， $P\left(G_n\right)=\left[{\left(q-1\right)}^m-{\left(q-1\right)}^{m-1}+{\left(q-1\right)}^{m-2}+\cdots +{\left(-1\right)}^{m-1}\left(q-1\right)\right]P(\; G\; \prime \; )$

当m为奇数时，如果 $q\ge 3$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$ ；

当m为偶数时，如果 $q\ge 2$，则 $P\left(G_n\right)\ne 0$ 当且仅当 $P\left(G^{\prime }\right)\ne 0$。

从而结论成立。

注 该定理是命题3.3的一般化，因此也称进行了桥变换。同时由引理2.2和引理2.3，可以讨论其它图的着色性质。由于纽结投影图与平面图是一一对应关系，所以它们的有些变换是相互转化的，比如：纽结投影图的 $R1$ 变换就对应图的树形变换。

基金项目

国家自然科学基金(No. 11471151)，辽宁省教育厅(No. LJ2019004)的资助。