应用数学进展  >> Vol. 10 No. 5 (May 2021)

平面图的变换与着色的性质
Moves and Coloring Properties for Planar Graph

DOI: 10.12677/AAM.2021.105160, PDF, HTML, XML, 下载: 41  浏览: 92  国家自然科学基金支持

作者: 韩友发, 刘 佳, 孔令天:辽宁师范大学数学学院,辽宁 大连;阎昕明:广东第二师范学院数学系,广东 广州

关键词: 图着色双色多项式图变换纽结Graph Coloring Dichromatic Polynomial Graph Move Knot

摘要: 本文研究了平面图着色的性质,给出了平面图的变换,包括树形变换、三角形变换(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.

文章引用: 韩友发, 刘佳, 孔令天, 阎昕明. 平面图的变换与着色的性质[J]. 应用数学进展, 2021, 10(5): 1508-1514. https://doi.org/10.12677/AAM.2021.105160

1. 引言

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

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

2. 预备知识

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

定义2.2 设n是一个正整数,定义一个n-弧是一个包含n条边, n + 1 个顶点的图,满足下面的性质:将边记为 A 1 , A 2 , A n ,顶点记为 a 0 , a 1 , , 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 , , a n ,边记为 A 1 , A 2 , 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 ( G ) 映到 V ( H ) ,g也是一个一一映射将 E ( G ) 映到 E ( H ) θ = ( f , g ) 。称 θ 是G到H的同痕,如果满足下面的性质:任意的顶点x是边A的端点当且仅当 f ( x ) 是边 g ( A ) 的端点。如果这样的同痕映射 θ 存在,则称图G和图H是同痕的。

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

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

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

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

(1) Z ( G ) = q

(2) Z ( G ) = q Z ( G )

(3) Z () = Z () + v Z ()

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

例子:Z () = q 3 + 3 v q 2 + 3 v 2 q + v 3 q ,当 v = 1 时, P ( G ) = q 3 3 q 2 + 2 q = q ( q 1 ) ( q 2 ) 恰好是平面图三角形着色数目。

引理2.2 [8] 如果图G是子图H和K的不交并,那么 P ( G ) = P ( H ) P ( K )

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

q P ( G ) = P ( H ) P ( K )

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

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

3.1. 树形变换的着色问题

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

命题3.1 设图 G n 是由G添加m-弧 L m 构成,且 L m G 是一个顶点,则当 q 2 时, P ( G n ) 0 当且仅当 P ( G n 1 ) 0

证明 首先考虑 m = 1 ,则 G n 是由 G n 1 添加1-弧构成(见图3)。

Figure 3. 1-arc

图3. 1-弧图

由计算可得, Z ( G n ) = Z () + v Z ( G n 1 ) = q Z ( G n 1 ) + v Z ( G n 1 ) = ( q + v ) Z ( G n 1 )

由引理2.1可知,当 v = 1 时, P ( G n ) = ( q 1 ) P ( G n 1 ) ,所以 q 2 时, P ( G n ) 0 当且仅当 P ( G n 1 ) 0 。其次,一般情形计算有, Z ( G n ) = ( q + v ) m Z ( G ) ,当 v = 1 时, P ( G n ) = ( q 1 ) m Z ( G ) ,所以, q 2 时, P ( G n ) 0 当且仅当 P ( G n 1 ) 0 。从而结论成立。

定理3.1 设图 G n G 添加树 T m 得到,其中 T m 有m个顶点, T m G 是一个顶点(见图4),则当 q 2 时, P ( G n ) 0 当且仅当 P ( G ) 0

Figure 4. Tree

图4. 树形图

证明 利用命题3.1,由归纳法, Z ( G n ) = ( q + v ) m 1 Z ( G ) ,当 v = 1 时, P ( G n ) = ( q 1 ) m 1 P ( G ) ,所以 q 2 时, P ( G n ) 0 当且仅当 P ( G ) 0 。从而结论成立。

注 图 G 是有G去掉树形得到的,把这种变换称为树形变换,该定理这说明树–变换不改变图的着色数。

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

命题3.2 设图 G n G n 1 添加一个3-圈P得到, G n 1 P 是一个顶点(见图5),则当 q 3 时, P ( G n ) 0 当且仅当 P ( G n 1 ) 0

Figure 5. Graph with 3-loop

图5. 带3-圈的图

证明 通过计算可得: Z ( G n ) = [ ( q + 2 v ) ( q + v ) + v 2 ( v + 1 ) ] Z ( G n 2 ) ,当 v = 1 时, P ( G n ) = ( q 2 ) ( q 1 ) P ( G n 1 ) ,所以, q = 3 时, P ( G n ) 0 当且仅当 P ( G n 1 ) 0 。从而结论成立。

定理3.2 设图 G n G 添加一个m-圈P得到, G P 是一个顶点(见图6),则有

(1) 当m是偶数时,如果 q 2 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

(2) 当m是奇数时,如果 q 3 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

证明

Z ( G n ) = Z ( G T m ) + v Z ( G P m 1 ) = [ ( q + v ) m 1 + v ( q + v ) m 2 + + v m 3 ( q + v ) 2 ] Z ( G ) + v m 2 Z ( G P 1 ) = [ ( q + v ) m 1 + v ( q + v ) m 2 + + v m 2 ( q + v ) ] Z ( G ) + v m 1 Z ( G P 1 ) = [ ( q + v ) m 1 + v ( q + v ) m 2 + + v m 2 ( q + v ) + v m 1 ( v + 1 ) ] Z ( G ) = [ ( q + v ) m 1 [ 1 ( v q + v ) m 1 ] 1 v q + v + v m 1 ( v + 1 ) ] Z ( G ) = [ ( q + v ) [ ( q + v ) m 1 v m 1 ] q + v m 1 ( v + 1 ) ] Z ( G ′ )

v = 1 时, P ( G n ) = q 1 q [ ( q 1 ) m 1 ( 1 ) m 1 ] P ( G ) ,所以,当m是偶数时,

P ( G n ) = ( q 1 ) [ ( q 1 ) m 1 + 1 ] P ( G ) ,此时,如果 q 2 ,则 P ( G n ) 0 当且仅当 P ( G ) 0 。当m是奇数时,

P ( G n ) = ( q 1 ) [ ( q 1 ) m 1 1 ] P ( G ) 。此时,如果 q 3 ,则 P ( G n ) 0 当且仅当 P ( G ) 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 2 ,则 P ( G n ) 0

(2) 当m是奇数时,如果 q 3 ,则 P ( G n ) 0

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

Figure 7. Graph of 3-loop

图7. 3-圈的图

对于一般情形有 P ( G n ) = P ( m - ) = P ( ) ,由定理3.1和定理3.2,结论成立。

3.3. 桥变换的着色问题

命题3.3 设 G n 存在m条有相同端点的边 l k ( k = 1 , , m ) ,去掉其中 m 1 条边后的图记为 G n ,则 P ( G n ) = P ( G n )

证明 如果图 G n 的两个顶点 x , y 存在两个相同端点的边,去掉其中一条重复边后的图记为 G n (见图8), Z ( G n ) = Z ( G n ) + v Z () = Z ( G n ) + v ( 1 + v ) Z (),当 v = 1 时, P ( G n ) = P ( G n ) 。一般情形同理可证。

Figure 8. Graph of multiple edges

图8. 带多重边的图

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

定理3.3 设图 G n G 添加m-弧 L m 得到, G L m L m 的两个端点(见图9),则有

(1) 当m为奇数时,如果 q 3 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

(2) 当m为偶数时,如果 q 2 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

Figure 9. Graph with bridge

图9. 带桥的图

证明: Z ( G n ) = Z () + v Z ()

= [ ( q + v ) m + v ( q + v ) m 1 + v 2 ( q + v ) m 2 + + v m 1 ( q + v ) ] Z ( G ) + ( 1 + v ) Z ( G ″ )

v = 1 时, P ( G n ) = [ ( q 1 ) m ( q 1 ) m 1 + ( q 1 ) m 2 + + ( 1 ) m 1 ( q 1 ) ] P ( G ′ )

当m为奇数时,如果 q 3 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

当m为偶数时,如果 q 2 ,则 P ( G n ) 0 当且仅当 P ( G ) 0

从而结论成立。

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

基金项目

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

参考文献

[1] Alexander, J.W. (1928) Topological Invariants of Knots and Links. Transactions of the American Mathematical Society, 30, 275-306.
https://doi.org/10.1090/S0002-9947-1928-1501429-1
[2] Conway, J.H. (1970) An Enumeration of Knots and Links, and Some of Their Algebraic Properties. Computational Problems in Abstract Algebra, New York, 29 August-2 September 1970, 329-358.
https://doi.org/10.1016/B978-0-08-012975-4.50034-5
[3] Jones, V.F.R. (1989) On Knot Invariants Related to Some Statistical Mechanical Models. Pacific Journal of Mathematics, 137, 311-334.
https://doi.org/10.2140/pjm.1989.137.311
[4] Kauffman, L.H. (1988) New Invariants in the Theory of Knots. The American Mathematical Monthly, 95, 195-242.
https://doi.org/10.1080/00029890.1988.11971990
[5] Wu, F.Y. (1992) Knot Theory and Statistical Mechanics. Modern Physics, 64, 1099-1131.
https://doi.org/10.1103/RevModPhys.64.1099
[6] Sumners, D.W. (1990) Untangling DNA. The Mathematical Intelligencer, 12, 71-80.
https://doi.org/10.1007/BF03024022
[7] Adams, C.C. (2004) The Knot Book. W. H. Freeman and Company, New York.
[8] 韩友发, 亢云凤, 董婷. 平面图的多项式与着色[J]. 辽宁师范大学学报, 2017, 40(3): 289-292.