关于图论课程教学中对染色问题的研究.pdf

Advances in Education 教育进展教育进展,2023,13(10),7943-7946 Published Online October 2023 in Hans.https:/www.hanspub.org/journal/ae https:/doi.org/10.12677/ae.2023.13101233 文章引用文章引用:初亚男,赵操.关于图论课程教学中对染色问题的研究J.教育进展,2023,13(10):7943-7946.DOI:10.12677/ae.2023.13101233 关于图论课程教学中对染色问题的研究关于图论课程教学中对染色问题的研究 初亚男，赵初亚男，赵 操操 苏州科技大学数学科学学院，江苏 苏州 收稿日期：2023年9月18日；录用日期：2023年10月17日；发布日期：2023年10月24日 摘摘 要要 图论起源图论起源于著名的哥尼斯堡七桥问题，是离散数学的重要分支。它在计算科学、社会科学和自然科学于著名的哥尼斯堡七桥问题，是离散数学的重要分支。它在计算科学、社会科学和自然科学等多个领域都有广泛应用。本文主要研究广义等多个领域都有广泛应用。本文主要研究广义Petersen图的非正常点染色问题，构造满足条件的染色图的非正常点染色问题，构造满足条件的染色方式。旨在帮助学生更好地理解方式。旨在帮助学生更好地理解图论图论基本基本概念概念，掌握图论中的基本技巧方法，从而培养学生科学解决，掌握图论中的基本技巧方法，从而培养学生科学解决问题的问题的能力能力。关键词关键词 非正常非正常染色染色，广义，广义Petersen图，邻点图，邻点 Research on Coloring Problem of Graph Theory in Curriculum Teaching Yanan Chu,Cao Zhao School of Mathematical Sciences,Suzhou University of Science and Technology,Suzhou Jiangsu Received:Sep.18th,2023;accepted:Oct.17th,2023;published:Oct.24th,2023 Abstract Graph theory,which originated from the famous Seven Bridges problem,is an important branch of discrete mathematics.It has extensive applications in many fields such as computing science,so-cial science and natural science.In this paper,we mainly study improper coloring of generalized Petersen graphs and construct a coloring with certain requirement.It aims to help students un-derstand the basic concepts and skills in graph theory,so as to guide student to develop the ability of solving scientific problems.Keywords Improper Coloring,Generalized Petersen Graph,Neighbors 初亚男，赵操 DOI:10.12677/ae.2023.13101233 7944 教育进展 Copyright 2023 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 随着计算机科学的飞速发展，图论作为离散数学的一个重要分支，越来越成为各个领域研究的热点。纵观图论发展史，“四色猜想”是其中一个非常著名的问题，它与“费马猜想”，“哥德巴赫猜想”并称世界三大数学猜想。“四色猜想”的内容是：任何一张地图都可用四种颜色进行染色使得拥有共同边界的国家染以不同颜色。1976 年，Appel 和 Haken 1宣称他们借助计算机历时 1200 个小时证明了该猜想，即“四色定理”。但关于它的理论性证明至今无人给出。在四色定理的推动下，图的染色问题受到国内外学者的高度关注，由此衍生出多种类型的染色问题，如图的点染色，边染色，点和边全染色以及列表染色等等。有兴趣的读者可从文献2 3 4中了解关于图染色问题的更多文献。图的点染色问题是指用不同颜色对一个图 G 的顶点集进行染色，使得相邻顶点染色不同，所需的最小颜色数记为()G。于是，四色定理可以转化为图的点染色问题，即将每个地区看作图中的一个顶点，相邻的地区之间用一条边连接，通过求证点染色问题的最小颜色数为 4，从而确定地图需要 4 种颜色。1985 年，Burr 和 Jacobson 等人5对图的点染色做进一步推广，提出非正常点染色的概念。设12,kd dd是 k 个非负整数。如果图 G 的点集 V 可以被剖分成 k 个子集12,kV VV，使得对iV中的每个点 v，至多id个邻点与 v 同属于子集iV，1ik，则称 G 是非正常()12,kd dd-可染的，简称()12,kd dd-可染的。当120kddd=时，即为正常染色。于是，四色定理又可以表述为：每个平面图是()0,0,0,0-可染的。近年来，图的非正常染色问题受到国内外学者的广泛关注，其研究对象为禁子圈的平面图和具有度数限制的图等，感兴趣的读者可参见文献6 7 8 9 10了解更多该方面的文献。本文以图的非正常点染色问题为切入点，研究特殊图类的非正常 2-染色问题。第二节介绍图论的基本定义和广义 Petersen 图的概念，第三节将给出广义 Petersen 图(),2G n的非正常 2-染色结果的证明。2.基本概念基本概念 本文所研究的图是有限且无重边，无环的简单图，未定义的概念和符号参见文献11。定义定义 2.1 11设(),GV E=是一个简单图，其中 V 表示点集，E 表示边集。对任意的点,u vV，如果uvE，则称 u 和 v 邻接，u 和 v 互称为邻点，u 在图 G 中的所有邻点的个数称为 u 的度数，记为()d u。如果对任意的vV，()d vk=，则称 G 是一个 k-正则图。定义定义 2.2 11设123nu u uu是图 G 中 n 个点的序列，如果对所有的1,i jn，()iju uE G当且仅当iu和ju是连续点，则称123nPu u uu=是 G 中的一条路。进一步地，如果1nuu=，则称 P 是一个圈。定义定义 2.3 12设 3-正则图 G 的顶点集和边集分别为：01210121,;,nnVu u uuv v vv=，1,|0,1,1iii ii i rEu uu v v vin+=，其中下标取模 n，5n，0rn，称 G 为广义 Petersen 图，记(),G n r。当2r=时，5n=和6n=的情形见图 1。3.广义广义 Petesen 图的非正常图的非正常 2-染色染色 定理定理 3.1 12()()3,24G n。根据定理 3.1，至少需要 3 种颜色对广义 Petersen 图(),2G n进行正常点染色。若允许某些相邻顶点染相同颜色，即非正常染色，则可达到降低色数的效果，从而在实际问题中将起到节约资源的目的。我们Open AccessOpen Access初亚男，赵操 DOI:10.12677/ae.2023.13101233 7945 教育进展 用数字 1 和 2 分别代表颜色，且允许每个染以颜色 1(或 2)的点至多有一个邻点与其染色相同，得到如下结果。(a)G(5,2)(b)G(6,2)Figure 1.We use numbers 1 and 2 to denote color red and blue in the proof of Theorem 3.2,respectively 图图 1.在定理 3.2 的证明中，红色和蓝色分别用数字 1 和 2 表示 定理定理 3.2(),2G n是()1,1-可染的。证明证明：令(),2GG n=，01210121,;,nnVu u uuv v vv=。我们将分别对点集011,nu uu和011,nvvv进行染色，记染色为 c，其染色方式如下：首先考虑外圈0 11 0nu uuu，令偶下标顶点染颜色 1，奇下标顶点染颜色 2，即对每一个,0,1,2,1i in，如果()02imod，则令()1ic u=，如果()12imod，则令()2ic u=。接下来考虑011,nvvv，分下述两种情形：情形情形 1 n 为奇数。此时内部圈为0 2 431 1 342 0nnnnv v vvvv vvvv。令()()012nc vc v=，()21nc v=。对每一个奇数,1,3,5,4j jn，令21jk=+。如果()02kmod，则令()()11jjc vc v+=；如果()12kmod，则令()()12jjc vc v+=(5n=时的染色见图 1)。首先考虑iv，0,1,1,ni，根据(),2G n的定义，iv与1iv+，1iv都不邻接。如果出现()()431nnc vc v=，那么由于 n 是奇数，按照染色规则，有()()422nnc uc u=，即与2nv(或4nv)染相同颜色 1 的邻点只有4nv(或2nv)，并且对每个2in且4in，至多一个邻点iu与iv染色相同；如果()()432nnc vc v=，很容易验证，对每个0,1,1,ni，至多一个邻点iu与iv染色相同。类似地，可验证011,nu uu中的点：只有0u和1nu相邻且有相同颜色 1，而对于1,2,2,ni，至多一个邻点iv与iu染色相同。情形情形 2 n 为偶数。此时内部两个圈分别为：0 2 42 0nv v vvv和1 31 1nv vvv。首先，考虑022,nv vv。对每一个(),01,22k kn，如果()02kmod，令()22kc v=；如果()12kmod，则令()21kc v=。再来考虑131,nv vv。对每一个(),01,22k kn，如果()02kmod，则令()211kc v+=；如果()12kmod，则令()212kc v+=(6n=时的染色见图 1)。类似于情形 1，对每个0,1,1,ni，考虑iu，容易验证至多一个邻点iv与其染色相同；再考虑022,nv vv，按照染色规则，()02c v=，若出现()()202nc vc v=，则由于 n 是偶数，结合染色规则，有()()021nc uc u=；最后对131,nv vv中的点分析类似。无论哪种情形，至多一个邻点与iv染色相同，0,1,1,ni。定理得证。初亚男，赵操 DOI:10.12677/ae.2023.13101233 7946 教育进展 4.注记注记 注意到，定理 3.2 的结论是最好可能的，即不存在一种染色方式使得(),2G n是()1,0-可染的。如在对()6,2G的染色过程中，假设所有染颜色 2 的点不邻接。对 u0染颜色 2，则 u1和 u5需染颜色 1，因为 v1和 v5相邻，所以染色不能相同。(否则，或者出现两个相邻点染颜色 2，或者出现 v1和 v5都有两个邻点与其染相同颜色 1，矛盾。)又由于 v3与 v5，v1都邻接，故无论 v3染哪种颜色均产生矛盾。本文主要研究了广义 Petersen 图的非正常 2-染色，图论中还有许多类似问题不仅可以激发学生的学习兴趣，还可以锻炼与培养学生的逻辑思维能力和创造力。参考文献参考文献 1 Appel,K.and Haken,W.(1977)Every Planar Map Is Four Colorable,Part II.Reducibility.Illinois Journal of Mathe-matics,21,491-567.https:/doi.org/10.1215/ijm/1256049012 2 Lin,Q.Z.,Hou,J.F.and Liu,Y.(2012)Acyclic Edge Coloring of Graphs with Large Girths.Science China Mathemat-ics,55,2593-2600.https:/doi.org/10.1007/s11425-012-4442-7 3 Yang,F.and Wu,J.L.(2022)The Total Coloring of K5-Minor-Free Graphs.European Journal of Combinatorics,102,103510.https:/doi.org/10.1016/j.ejc.2022.103510 4 吴狄,许宝刚,许怡安.围长21l+且无长奇洞图的染色问题J.中国科学,2023,53(1):103-120.5 Andrews,J.and Jacobson,M.(1985)On a Generalization of Chromatic Number.Congressus Number,47,33-48.6 Borodin,O.V.and Kostochka,A.V.(2014)Defective 2-Coloring of Sparse Graph.Journal of Combinatorial Theory,Series B,104,72-80.https:/doi.org/10.1016/j.jctb.2013.10.002 7 Borodin,O.V.,Kostochka,A.and Yancey,M.(2013)On 1-Improper 2-Coloring of Sparse Graphs.Discrete Mathe-matics,313,2638-2649.https:/doi.org/10.1016/j.disc.2013.07.014 8 Choi,I.and Raspaud,A.(2015)Planar Graphs with Girth at Least 5 Are(3,5)-Colorable.Discrete Mathematics,338,661-667.https:/doi.org/10.1016/j.disc.2014.11.012 9 Chu,Y.N.,Sun,L.and Yue,J.(2019)Note on Improper Coloring of 1-Planar Graphs.Czechoslovak Mathematical Journal,69,955-968.https:/doi.org/10.21136/CMJ.2019.0558-17 10 Li,X.W.,Liu,J.and Lv,J.-B.(2022)Every Planar Graph with Girth at Least 5 Is(1,9)-Colorable.Discrete Mathemat-ics,345,112818.https:/doi.org/10.1016/j.disc.2022.112818 11 Bondy,J.A.and Murty,U.S.R.(2008)Graph Theory.Springer,Berlin.12 林育青.广义 Petersen 图(),GP n k的着色J.山西师范大学学报(自然科学版),2010,24(4):8-11.