（基础数学专业论文）平面图的着色问题.pdf

，乒 l j 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特别加以标注和 致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其他同志的研究成果对本人的 启示和所提供的帮助，均已在论文中做了明确的声明并表示谢意。 学位论文作者签名：圆! 刍! ! 盘 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：遇生竺支舯教师签名磅芬吮指导教师签名：幺翌丝! 生 签名日期：知ff年勿月2 ，日 j j 鼻。 1 x 辽宁师范大学硕士学位论文 摘要 本文主要讨论图的着色问题，通过讨论图的色多项式的零点问题，分析对图着色保 证相邻的两个顶点不同色的最少方法数目，进而得到一些特殊情形图着色的等价条件 而图的色多项式与相对应的纽结多项式和p o t t s 模型的分拆函数相关联，因此本文涉及 到了关于统计力学和纽结的相应结论 本文的主要研究方法是对顶点着色提供一个新的研究渠道，即计算先前的图移除自 身的一部分之后的图的色多项式，得到后者的着色数目，并通过前后图着色数目的对比 进行一些题目的讨论并通过归纳法得到一些一般的结论为了完成这项工作，首先需要 一些准备和对图论知识、纽结理论及统计力学的知识的回顾然后对一些特殊的图形分 门别类地进行讨论：第1 组讨论的是“n 一圈环绕树 的着色数目；第2 组讨论的是“n 一 弧一移除”对图的着色数目的影响；第3 组是“树一移除”对图的着色数目的影响；第4 组讨论的是“刀一圈一移除”对图的着色数目的影响；第5 组讨论的是“图架桥 对图的 着色数目的影响；第6 组讨论的是“去掉重复边 对图着色数目的影响；第7 组讨论的 是“以一圈环绕图”的着色数目 对于平面图上建立的p o t t s 模型，以上对原有图做的变化的分析都可以应用到对 p o t t s 模型分拆函数发生的变化的分析中，而统计力学中的很多热力学变量都可以由分 拆函数计算得到，因此会得到相应的对统计力学的应用 对于与平面图对应的纽结的投影图，以上对原有图做的变化也可以应用到纽结方括 号多项式中，得到关于纽结的相应的结论 关键词：图着色；色多项式；p o t t s 模型；纽结 4l ， ，j 引上l_，1i_、_-，iill一 ， 一 平面图的着色问题 c o l o r i n g o i lt h eg r a p h a b s t r a c t t h e m a i nc o n t e n to ft h i sp a p e ri sd i s c u s s i n gg r a p hc o l o r i n g ，t h r o u g hd i s c u s s i n gt h ez e r o s o fg r a p h s c h r o m a t i cp o l y n o m i a l ，i ta n a l y z e st h en u m b e ro fw a y st ov e r t e x - c o l o rt h eg r a p h w i t hc o l o r ss ot h a tn ot w oa d j a c e n tv e r t i c e sr e c e i v et h es a m ec o l o r g r a p hc o l o r i n gp r o b l e m h a sc o n n e c t i o nw i t hk n o tp o l y n o m i a la n dt h ep o t t sm o d e l h e n c e ，t h i sp a p e rr e f e r st ok n o t t h e o r ya n ds t a t i s t i c a lm e c h a n i c s t l l ep u r p o s eo ft h i sr e v i e wi st oi n t r o d u c ean e wa p p r o a c ha b o u tv e r t e x c o l o r i n g w e w i l lc o m p u t et h el a t e rg r a p h sd i c h r o m a t i cp o l y n o m i a lw h e nt h ef o r m e rg r a p hh a sr e m o v e da 少a r to n e t h r o u g hc o m p a r i n gw i t ht h ef o r m e rd i c h r o m a t i cp o l y n o m i a l ，s o m et o p i e sw i l lb e l d i s c u s s e da n dw ew i l lg i v es o m eg e n e r a lc o n c l u s i o n s t oa c c o m p l i s ht h i s ，i ti sn e c e s s a r yt o r e f o r m u l a t ea n dr e w o r kt h ee x i s t i n ga n dk n o w nr e s u l t si nk n o tt h e o r y , g r a p ht h e o r ya n d s t a t i s t i c a lm e c h a n i c s t h e ni l l u s t r a t i v ec a l c u l a t i o n s f o rv a r i o u sf a m i l i e so fg r a p h sa r e p r e s e n t e d ：t h ef i r s td i s c u s s e dg r o u po fg r a p h sa r e ”t r e e sa r o u n dn - c i r c u i t ”；t h es e c o n d d i s c u s s e dg r o u po fg r a p h sa r e ”n a r c m o v e ”；t h e 1 i r dd i s c u s s e dg r o u po fg r a p h s a r e ”t r e e s m o v e ”：1 1 1 ef o r t hd i s c u s s e dg r o u po fg r a p h sa r e ”n c i r c u i t m o v e ”；1 1 1 ef i f t hd i s c u s s e d g r o u po fg r a p h sa r e ”u n k n o w ng r a p h + b r i d g e ”；t h e s i x t hd i s c u s s e dg r o u po fg r a p h sa r e n l i n k m o v e ”：t h es e v e n t hd i s c u s s e dg r o u po fg r a p h sa r e ”b n k n o w ng r a p h sa r o u n dn 。c i r c u i t ” s o m ei m p l i c a t i o n sf o rc o r r e l a t i o n so ft h es t a t i s t i c a lm e c h a n i c sa r em e n t i o n e d 劢e p a r t i t i o nf u n c t i o ni sau s e f u lq u a n t i t yt o d e t e r m i n e i tw a sa l r e a d yp r o v e dt h a tv a _ r l o n s t h e r m o d y n a m i cq u a n t i t i e sc a l lc a l c u l a t ef r o mt h ep a r t i t i o nf u n c t i o n t h e s ec a s e sa r ea l s oa p p l i e dt os q u a r eb r a c k e to f t h ea s s o c i a t e da l t e r n a t i n gk n o t k e yw o r d s ：g r a p hc o l o r i n g ；c h r o m a t i cp o l y n o m i a l ；p o t t sm o d e l ；k n o t i i f-、l、一、l 一i lilliiilifllllllii卜 i 1-，x。，射 ， ： j ， & 辽宁师范大学硕十学位论文 目录 摘 要i a b s t r a c t i i 弓i言1 1 预备知识2 1 1 图论中的一些定义2 1 2 纽结和平面图3 1 3 图的多项式和四色猜想。4 1 4 统计力学中的p o t t s 模型5 1 5 纽结多项式6 1 6 图的多项式与p o t t s 模型的分拆函数的关系6 1 7 图的多项式与纽结多项式的关系。7 1 8 纽结多项式和p o t t s 模型的分拆函数的关系7 2 通过多项式的零点讨论图着色8 2 1 “m 圈环绕树”的着色问题8 2 2 “m 弧移除”的着色问题l1 2 3 “树移除”的着色问题1 2 2 4 “m 圈移除”的着色问题1 3 2 5 “图架桥 的着色问题。15 2 6 “去掉重复边 的着色问题1 7 2 7 “k 圈环绕图 的着色问题1 8 3 在统计力学中的应用2 4 4 在纽结中的应用3 0 结论3 3 参考文献3 4 攻读硕士学位期间发表学术论文情况3 5 致谢3 6 1-，、丫 叫，丁一_1_ r ： j 嘻 蕾 辽宁师范大学硕七学位论文 己i言 l目 纽结理论1 7 在发端时，本是出于揭示化学元素本质的动机，而在发展的大部分时间 里，它是拓扑学的一部分，被看做纯理论的研究纽结理论的主要课题，是寻求既有强 的分辨不同纽结的能力，又易于计算的同痕不变量1 9 2 8 年，美国数学家阿历山大取得 了重大突破，他给每个纽结联系上一个多项式不变量在纽结领域一个惊喜的发现是一 个新的纽结不变量，即琼斯多项式及其与统计力学的联系现在它不仅成了许多数学分 支的交叉点，而且参与了对图论着色的研究中因为平面图对应着交错纽结，而交错纽 结的方括号多项式与图的双色多项式相联系本文在阅读关于纽结多项式的文献中受 到启发，力图研究在色多项式中涉及到的关于图的着色的问题 在统计力学【8 - 1 2 】中，物理学家为了对相变进行定性分析，创造出了抽象定义的系统 模型，在模型中像压力和热熔这样的宏观量可以作为某些参数的函数明确的计算出来 统计力学中建立的一个常用的模型i s i n g 模型的分拆函数是纽结的彳厂厂不变量【7 】，一般 化i s i n g 模型得到一类特殊模型，即p o t t s 模型如果p o t t s 模型的每个顶点允许有g 个 自旋，则它可以推导出纽结的琼斯多项式y ( f ) ，其中满足等式：q = 2 + t + t 一 k a s t e l e g n 和f o r t u i np o t t s 第一次发现了力学模型与图论的联系，而e s s a m 和t s a l l i s 发现了模型的分拆函数与图的色多项式也存在定的联系【1 3 1 ，因此可将物理模型应用到 对图的着色的分析中由此讨论出了许多图论关于着色的新成果 有了这些关联，一些相应的结论是否可以在三者之间传递昵? 本文就是在分析研究这些成果的基础上，重点研究图的着色问题：发现通过移除图 的一部分，一些情况图的着色受到影响，而另外一些情况对图的着色没有影响，从而通 过归纳分析得到一些一般的结论并探讨在统计力学及纽结中存在的相应的变化 本论文共分为四个部分第一部分回顾所需的预备知识，尤其对图的色多项式、 p o t t s 模型的分拆函数和纽结多项式的关系进行阐述：第二部分通过多项式的零点讨论 图着色；第三部分讨论对相同的图进行变化，其对应的p o t t s 模型的分拆函数的变化情 况；第四部分讨论对相同的图进行变化，其对应的纽结的多项式的变化 平面图的着色问题 1 预备知识 1 1 图论中的一些定义 在本节中我们给出图论中已有的定义1 1 - 6 1 定义1 1 ：一个图是一个三元组，这个三元组包含一个顶点集v ( g ) ，一个边集e ( g ) 和一个关系，使得每一条边和两个顶点( 不一定是不同的点) 相关联，并将这两个顶点 称为这条边的端点若一条边的端点数为1 个，则称其为一条弧 定义1 2 ：图日称为图g 的子图，如果v ( h ) v ( g ) ，e ( h ) e ( g ) 定义1 3 ：设咒是一个正整数，我们定义一个n 一弧是一个包含行条边，n + 1 个顶点 的图，满足下面的性质：将边记为4 ，4 ，4 l ，顶点记为a o ，口1 ，吼，对于每一个， 彳，的端点是口卜。和口，图1 1 1 中的( 口) 、( b ) 、( c ) 分别表示卜弧、2 一弧、3 一弧 - 多 i ( 6 ) ( c ) (2 ) 图1 1 1 定义1 4 ：设n 是一个正整数，一个以一圈定义为一个包含r 个顶点和疗个边的图g ， 满足下面的性质：顶点记为a l , 口：，口。，边记为4 ，4 ，4 ，对于每一个j ，4 的端点 是口产l 和口，( 这里口。= 口。) 图1 1 2 中的( 口) 、( 6 ) 、( c ) 和( d ) 分别表示卜圈、2 一圈、 3 一圈和4 一圈 oo 入 r ( a )( 6 ) ( d ) ( c ) 图1 1 2 v 一 ： 7 气 辽宁师范大学硕士学位论文 定义1 5 ：一个树定义为无圈的连通图 定义1 6 ：设g 和h 是两个图，厂是一个一一映射，将v ( c ) 映到v ( h ) ，g 也是一 个一一映射将e ( g ) 映到e ( h ) ，0 = ( f ，g ) 我们称0 是g 到日的同痕，如果满足下面 的性质：任意的顶点x 是边么的端点当且仅当f ( x ) 是边g ( 彳) 的端点如果这样的同痕 映射秒存在，则称图g 和图日是同痕的 图论一般研究的就是同痕图的一些性质，在没有特别说明的前提下，接下来我们讨 论所涉及的图都是指同痕图 1 2 纽结和平面图 究竟是什么将纽结理论和图论联系起来? 定义1 7 ：我们考察纽结在平面上的投影图 7 - 8 ，每一个交叉点都有如图1 2 1 的 两种情形，如果我们不考虑上穿线和下穿线，则得到与纽结投影图相对应的几何图我 们称这个几何图为原纽结投影图的万有图例如图1 2 2 就是三叶结投影图和它的万有 图 o l i i 从一个纽结万有图，我们可以按下面的方式构作对应的平面图首先将万有图不相 邻的一部分区域涂黑，保证无限区域的部分不涂黑然后在每个涂黑区域确定一个顶 点，涂黑区域之间的交叉点为边，就得到平面图( 见图1 2 3 ) 这样我们就通过纽结 的万有图构造了平面图进一步，我们有下面的引理： 引理1 1 ：万有图和平面图是一一对应的【1 0 】 这样一来，我们可以将关于图的理论的研究放到对纽结的研究中 平面图的着色问题 1 3 图的多项式和四色猜想 我们首先介绍图的双色多项式z ( g ) ，它有两个变量g 和 ，满足下面三个条件： 1 z ( o ) = g 2 z ( og ) = q z ( g ) 3 z ( ) ：z ( 一) ：z ( ) + 亿( 夕) ：( ) z ( ) 由归纳法， z ( a 。) = ( g + 力”1 z ( g ) 当y = 一1 时， e ( g 。) = ( q 1 ) 州p ( g ) 当q 2 时，尸( 瓯) 0 当且仅当p ( g ) 0 从而定理的结论成立 注：这说明当用两种及两种以上颜色的时候，“树一移除 对图的着色没有影响 2 4 “朋一圈一移除”的着色问题 命题2 5 ：设图q 由q 一2 添加一个3 一圈p 得到，q 一2n e 是一个顶点( 见图2 4 1 ) ， 则当q 3 时，尸( 瓯) 0 当且仅当尸( 瓯一2 ) 0 ， -hoo-r。 平面图的着色问题 证明： 矧_ z ( 笋) 堋笋) ：z ( 尹) + 记( 尹) + 记( 尹) + v 2 z ( ) ：( g + 2 v ) z ( 一) + v 2 ( 1 + v ) z ( q 一：) = ( g + 2 v ) ( q + 1 ，) z ( g 。一2 ) + 1 ，2 ( 1 + dz ( q 一2 ) = ( g + 2 v ) ( q + y ) + v 2 ( ，+ 1 ) 】z ( q 一2 ) 当v = 一1 时， p ( q ) = ( q 一2 ) ( g 一0 p ( g , 一2 ) 当q 3 时，p ( g 。) 0 当且仅当p ( g 盹) 0 从而命题的结论成立 注：这说明当用三种及三种以上颜色的时候，“3 一圈一移除”对图的着色没有影响 定理2 4 ：设图q 由g 添加一个m 一圈p 得到，g n p 是一个顶点( 见图2 4 2 ) ， 则有 ( 1 ) 当m 是偶数时，如果q 2 ， ( 2 ) 当m 是奇数时，如果q 3 ， 贝up ( g 。) 0 当且仅当p ( g ) 0 ； 贝0p ( g 。) 0 当且仅当e ( o ) 0 注意：p 去掉一条边后的图是树 - 0 、iij1，j 群 ： p 辽宁师范火学硕士学位论文 证明： z ( q ) = z ( g u 乙) + v z ( g u 己一。) = ( g + v ) “一1 + ，( g + v ) “一2 + + v “一3 ( g + y ) 2 】z ( g ) + y ”一2 z ( g u s ) = 【( g + v ) ”一1 + 1 ，( g + ，) 廓一2 + + 1 ，掰一2 ( g + ，) z ( g ) + ，”一1 z ( g 。u 鼻) = ( g + y ) m 一1 + v ( g + v ) ”2 + + v 朋一2 ( g + 1 ，) + 1 ，”一1 ( ，+ 1 ) 】z ( g ) ( g + ，) 卅。1 1 一( j l ) 8 1 】 = 【型l + 1 ，“一1 ( y + 1 ) z ( g ) 1 一二 g + 1 ， ：【妞丛虹望二盟+ v m - ! ( v + 1 ) 】z ( g 。) g 当，= 一1 时， p ( g 。) = 型【( 9 一1 ) ”一一( - d 利l p ( g ) g 当肌是偶数时，尸( 瓯) = ( q - d ( q - 1 ) ”1 + 1 】p ( g ) ， 此时，如果q 2 ，则p ( q ) 0 当且仅当p ( g ) 0 ： 当m 是奇数时，p ( 瓯) = ( g 一1 ) 【( 口- 1 ) 掰。1 1 p ( g ) ， 此时，如果q 3 ，则尸( 瓯) 0 当且仅当p ( g ) 0 从而定理的结论成立 注：这说明当使用两种及两种以上颜色( m 为偶数) 或者使用三种及三种以上颜色 ( r r 为奇数) 时，“m 一圈一移除对图的着色没有影响 2 5 “图架桥 的着色问题 定理2 5 ：设图q 由g 添j o 【im 一弧厶得到，g n 厶是厶的两个端点( 见图2 5 ) ， 则有 ( 1 ) 当m 为奇数时，如果g 3 ，则p ( 瓯) 0 当且仅当p ( g ) 0 ； ( 2 ) 当m 为偶数时，如果q 2 ，则p ( 瓯) 0 当且仅当以g ) 0 p i - _ _ k 一 平面图的着色问题 证明： l 氐砖咚 z ( g 。) ：z ( 此) + 亿( 此) = 【( g + v ) 辨+ v ( g + v ) ”一1 + v 2 ( g + v ) ”一2 + + y ”( g + v ) 】z ( g ) 当1 ，= 一i 时， 以q ) = 【( g 1 ) 州- ( q - 1 ) ”- 1 + ( g 一1 ) ”一2 + + ( 一1 ) ”( q - o p ( g ) 设瓯= ( g 一1 ) ”- ( q - 1 ) 耐一1 + ( g 一1 ) ”2 + + ( 一1 ) ”( q - 1 ) 三_ s m = ( q - 1 ) - 1 - ( q - 1 ) “- 2 + + ( 一1 ) ”- 1 ( g 1 ) + ( 一1 ) ” 口一1 三= ( g 一1 ) ”+ ( 一1 ) ” 口一l 瓯：盟 ( g 一1 ) m + ( 一1 ) m 】 g 当朋为奇数时，瓯：q - l ( g 一1 ) 辨一1 】，此时当g 3 时，瓯o ； g 当优为偶数时，瓯：盟 ( g 1 ) m + 1 】，此时当g 2 时，最o g ( 2 3 ) ( 2 4 ) - ： ，- i _ - y 七 r k - 辽宁师范大学硕十学位论文 由此可见，当m 为奇数时，如果q 3 ，则p ( 瓯) 0 当且仅当p ( g ) 0 ；当m 为偶 数时，如果q 2 ，则尸( g 。) 0 当且仅当p ( g ) 0 从而定理的结论成立 注：这说明当使用两种及两种以上颜色( m 为偶数) 或者使用三种及三种以上颜色 ( m 为奇数) 时，“m 一桥一移除对图的着色没有影响 2 6 “去掉重复边”的着色问题 命题2 6 ：如果图g 。存在两个相同端点的边，去掉其中一条重复边后的图记为q ( 见图2 6 ) ，则p ( 瓯) = p ( q ) 慕 g h 、 。 g 图2 6 矾z 。啪记。基， - z ( e m ( 1 + 邮( 众)= z ( g ：) + ，( 1 + 力z ( ) 当 ，= 一1 时， p ( q ) = p ( q ) 从而命题结论成立 注：这说明“去掉一条重复边 对图的着色没有影响 定理2 6 - 设g 。存在m 条有相同端点的边i t ( k = 1 ，z ) ，去掉其中m - 1 条边后的 图记为q ，则p ( q ) = p ( q ) 平面图的着色问题 z ( q ) = z ( g 。) + 1 ，( 1 + v ) 】 当y = - 1 时，p ( g 。) = p ( 晓) 从而定理结论成立 注：这说明“去掉m 一1 条重复边”对图的着色没有影响 2 7 “后一圈环绕图”的着色问题 命题2 7 ：设图g 。仅有一个3 一圈，g 。余下的部分是任意图，其中g 。有n 个顶点( 见 图2 7 1 ) ，则当g 3 时，尸( q ) o 当且仅当p ( - - ) p ( 八) p ( 勺) o 注意：任意图在图2 7 1 中记为7 - ，a 和勺 证明： z ( 印- z ( 知) + 记( 炉吲) - z ( 知) + 谄( 柏) + v z ( 内h ：z ( 潲)：z ( 用) + 谄( 席) + v z ( 胸) + v ：z ( 潲) 圳知心。, 眵r t 。以岛) + v 2 z 。肩，十：z ( 勺) + 讫() + 泌( 以n( 用) 十 亿。属h ：z 。肩h ：z 。肩h ，z 。肩， 娟一讲z 。肩心。知。用i t 。 岛) + 、 ， _ j f i j j i i。 辽宁师范大学硕士学位论文 比。足勺1 当1 ，= 一1 时， 利用引理2 和引理3 ， 删钾。肩m 。a 眵 q h 。名h 。以岛h 。属， ：1 2p ( 侈) 尸( 以) p ( 勺) + 尸( 谚) 尸( 以) j p ( 勺) 一 三p ( 眵) p ( 以) p ( 勺) ：( 兰+ 1 一三) p ( 够) 尸( 八) 户( 勺) ：( q - l x ：q - 2 ) p ( 膨) p ( ) p ( 弋刁) q 当g 3 时，以q ) o 当且仅当p ( 易) p ( ) p ( 叼) o 从而命题结论成立 注：这说明当用三种及三种以上颜色的时候，原图的着色与移除3 一圈后的不相连的 图有关 命题2 8 ：设图q 仅有一个4 一圈，q 余下的部分是任意图，其中q 有以个顶点( 见 图2 7 2 ) ，则 当g 2 时，p ( q ) 0 当且仅当p ( 队) p ( 严) p ( 初) p ( 7 ) o 平面图的着色问题 注意：任意图在图2 7 2 中记为义，严，叼和弓7 证明： 邵沪z 。葛心。z ( 瓯) = z ( 矿。矿) + 亿( ) + 亿( 同上) 队严 c k 臣 卟 唑 = z ( 叨矿) + 亿( 碉1 7 ) + 亿( i 1i i ) + 1 ，2 z ( 叼y ) + v z ( 同上) 义严 队严 队一义产 亿。h 训善h 引夥h s z 。哆，十亿( 叼c 7 ) + ，2 z ( ) + v z z ( 叼y) + v( 初陌7 ) 十 ，川嗲。岛昌h ：z 。岛够，+ 儿( 和h ：z ( 哆) 娟一z 。哆心。：z 。琴心。：，+ z 。心。岛州z 。心。善，+ z 。夥心。岛侈心。和心。哆， 当v = 一1 时， - y ， f u 0 7 i 辽宁师范人学硕士学位论文 义严义严义严义严 p ( q ) = 一1 3p ( 明 矿) + p ( 叼矿) 一4p ( 叼 矿) + 了6p ( 初少) gg9 ：巡：坠呈p ( 义) 尸( 严) p ( 叼) p ( 锣) g 。 设( g ) = 9 3 - 4 q 2 + 6 q - 3 ，则厂( g ) = 3 q 2 8 q + 6 在厂( g ) 中，判别式 o 恒成立由此可知厂( g ) 是增函数，当q = 2 时，( g ) 0 ，所以当q 2 时， 厂( g ) 0 因此当g 2 时，p ( q ) 0 当且仅当p ( 义) p ( 严) p ( 初) p ( 7 ) 0 从而命题的结论成立 注：这说明当用两种及两种以上颜色的时候，原图的着色与移除4 一圈后的不相连的 图有关 命题2 9 - 设图瓯仅有一个5 一圈，g 。余下的部分是任意五个图，且这五个图互相 不连通，其中q 有刀个顶点( 见图2 7 3 ) ，则当q 3 时，p ( q ) 0 当且