（基础数学专业论文）色轨道多项式的性质及其应用.pdf

原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得凼苤直太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大学。作者今后 使用涉及在学期间主要研究内容或研究成果，须征得内蒙古火学就读期间导师的同意；若用 于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：逛 指导教师签名： 日 期：趟血牛 日期： 删 色轨道多项式的性质及其应用 摘要 组合计数和图的着色是组合数学与图论的重要内容，而p 6 1 y a 计数定理和计 算图色数的色多项式是研究它们的主要工具，在文献【3 】中，杜清晏教授将两者 结合，定义了色轨道多项式和色本原多项式，并提出了p 图$ 1 s c 一图的概念本 文对它们进行了研究，主要做了下述工作： 1 给出了p 一图色轨道多项式和色本原多项式的一些性质； 2 在给定子群p 的条件下，如何计算具体的简单标号图的p 一图色本原多项式； 3 针对项链的一些具体的计算公式，做了进一步的讨论； 4 给出了p 一图色本原多项式在化学上的一些应用 关键词：图，色轨道多项式，色本原多项式，项链计数公式； 2 p r o p e r t ya n da p p l i c a t i o no f t h ec h r o m a t i co r b i tp o l y n o m i a l a b s t r a c t c o m b i n a t o r i ce n u m e r a t i o na n dt h ec o l o r i n go fg r a p ha r ei m p o r t a n tp a r t so fc o m b i n a - t o r i cm a t h e m a t i c sa n dg r a p ht h e o r y ，a n dp 6 1 y at h e o r e ma n dt h ec h r o m a t i cp o l y n o m i a la r e m a j o rm e t h o d so fs t u d y i n gt h e m i n 3 ，p r o f e s s o rd uq i n g y a np u tt h eb o t ht o g e t h e r ，a n d g a v et h ed e f i n i t i o n so ft h ec h r o m a t i co r b i ta n dt h ec h r o m a t i cp r i m i t i v ep o l y n o m i a l ，a l s o i n t r o d u c e dt h ec o n c e p t i o n so fp g r a p ha n ds c g r a p h i nt h i st h e s i s ，w es t u d yt h ep r o p e r t i e so fc h r o m a t i co r b i tp o l y n o m i a l so fp g r a p ha n dt h ep r i m i t i v ec h r o m a t i cp o l y n o m i a lo f p g r a p ha n ds c g r a p h t h em a i nr e s u l t sa r ea sf o l l o w s ： 1 t h ep r o p e r t i e so ft h ec h r o m a t i co r b i tp o l y n o m i a la n dt h ep r i m i t i v ec h r o m a t i cp o l y n o m i a lo fp g r a p ha r ei n t r o d u c e d ； 2 w h e nt h eg r o u ppi sg i v e n ，h o wt oc o m p u t et h ep r i m i t i v ec h r o m a t i cp o l y n o m i a lo f p g r a p h ； 3 f u r t h e rr e s u l t sa r ed i s c u s s e da b o u tt h ec o n c r e t ec o m p u t a t i o nf o r m u l a so fn e c k l a c e ； 4 s o m ei n s t a n c e so ft h ep r i m i t i v ec h r o m a t i cp o l y n o m i a lo fp g r a p ha p p l i e di nc h e m i s t r y a r eg i v e n k e y w o r d s ：g r a p h ，c h r o m a t i co r b i tp o l y n o m i a lp r i m i t i v ec h r o m a t i cp o l y n o m i a l ， c o m p u t a t i o nf o r m u l a so fn e c k l a c e ； 3 第一章引言 1 1 组合数学的历史回顾 组合数学( c o m b i n a t o r i c s ) ，又称组合分析( c o m b i n a t o r i a la n a l y s i s ) ，它是研究离散 结构的存在、计数、分析和优化等问题的一门学科组合数学是一门古老而又新兴的数学 分支我国古人早在河图、洛书中已对一些有趣的组合问题给出了正确的解答近 代随着计算机的出现，组合数学这门学科得到了迅猛的发展，成为了一个重要的数学分 支组合数学的发展改变了传统数学中分析和代数占统治地位的局面现代数学可以分为 两大类：一类是研究连续对象的；另一类就是研究离散对象的，比如说组合数学组合数学 不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如在计 算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用微积分和近代数学 的发展为近代的工业革命奠定了基础而组合数学的发展则是奠定了本世纪的计算机革命 的基础 组合学正式源起于莱布尼兹( g o t t f r i e dw i l h e l m ，l e i b n i ，1 6 4 6 - - 1 7 1 6 ) 的研究，莱布尼 兹在论组合的艺术中首次在近代数学的意义下使用“组合”一词，“组合分析( a n a l y s i s ) ” 一词最早出现在尼古拉斯( p n i e h o l s o n ) 1 8 1 8 年的论文“e s s a y so nt h ec o m b i n a t o r i a la n a l y s i s ” 中，“组合学( c o m b i n a t o r i e s ) ”一词则较早地出现在列维1 9 4 0 年发表的“o n am e t h o do ff i n i t e c o m b i n a t o r i c sw h i c ha p p l i e st ot h et h e o r yo fi n f i n i t eg r o u p s ”一文中，“c o m b i n a t o r i c s ”即是 “c o m b i n a t o r i a lm a t h e m a t i c ”的缩写组合学最早是和数论及概率计算交叉在一起的一些著 名的数论函数如欧拉函数咖( 礼) 、麦比乌斯函数p ( n ) ，分拆函数p ( 几) 等，至今仍是组合学讨 论的对象，而概率的方法一直足求解组合问题的一种重要方法2 0 世纪9 0 年代以来，由于计 算机科学的迅猛发展使组合学改变了旧有的面貌，形成了富有生命力的新兴数学分支组 合数学的发展大致分为以下几个阶段： 1 1 7 世纪6 0 年代以前，这是以帕斯卡论算术三角形( 1 6 6 5 ) 及莱布尼兹论组合的艺 术( 1 6 6 6 ) 此期间组合学主要研究的内容是排列数和组合数( 不重和可重) 计算公式；排 列数之间的关系( 即一些恒等式) ；以及整数分拆等一些问题，这两部著作给出了组合学 中最基本的计算公式和原则从这两部著作中所涉及的一些内容来看，组合学作为一 门学科已具雏形 2 1 7 世纪6 0 年代至2 0 世纪6 0 年代，这一时期，组合学在研究内容、研究方法以及在其它学 科中的应用等方面都取得了很大的进展，同时受到数论、概率论和化学等推动而迅速 发展，得到了一般的存在性定理和计算原理1 9 0 1 年德国数学家内析( e n e t t ，1 8 4 8 1 9 1 9 ) 出版的第一本组合学教科书组合学教程，英国数学家麦克马洪( p a m a c m a h o n ) 5 1 1 组合数学的历史回顾 的两大卷组合分析于1 9 1 5 - - 1 9 1 6 年出版爱多士( p a u le r d o s ，1 9 1 3 - - 1 9 9 6 ) 关于组 合学的经典论文集计数的艺术也全面地总结了先前互不关联的计数技巧问题 1 9 3 6 年英国统计学家费舍尔( r a f i s h e r ，1 8 9 0 - - 1 9 6 2 ) 等人成功地应用正交拉丁方 于麦f f l 统计实验中，这极大地促进了现代组合学的形成；同时，在组合问题研究中开 始大量引入其它数学学科的知识，不断地充实了组合学的研究内容 3 2 0 世纪6 0 年代至现在，罗塔( g i a n - - c a r l o r o t a ) 对现代组合学的建立作了重要工作，包括 呼吁建立组合学这门学科、组织讨论班、编撰组合学论文集、组织召开组合学会议、创 立专门的学术刊物他和同事们发表了现代组合学的系列基础性论文( 共1 0 篇) ，把组合 学与其它数学学科联系起来1 9 5 8 年4 月在美国哥伦比亚( c o l u m b i a ) 召开了第十届应用 数学会议( t h e t e n t hs y m p o s i u m i n a p p l i e d m a t h e m a t i c s ) ，会后由美国数学会 h 版组合 分析一书组合学的专fj 期刊组合论杂志( j o u r n a lo f c o m b i n a t o r i a lt h e o r y ) 于1 9 6 5 年 创刊1 9 6 9 年在牛津大学召开了第一届组合学的专门会议 6 0 年代后，组合学逐渐发展成为一个独立的数学分支，由于组合学在其它学科中的重 要应用，又产生了一些新的数学分支，如组合几何、组合矩阵、组合拓扑、组合代数等等 组合数学不仪在软件技术中有重要的应用，在企业管理，交通规划，战争指挥，金 融分析等领域都有重要的应用在美国有一家用组合数学命名的公司，他们用组合数学的 方法来提高企业管理的效益，这家公司办得非常成功此外，试验设计也是具有很大应用 价值的学科，它的数学原理就足组合设计用组合设计的方法解决工业界中的试验设计问 题，在美国已有专门的公司开发这方面的软件最近，德国一位著名组合数学家利用组合 数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注 组合计数理论是组合学中一个最基本的研究方向，主要研究满足一定条件的安排方 式的数目及其计数问题特别地，在研究置换群的性质时引出的p 6 1 y a 计数定理是组合计数 理论中重要的定理它是枚举有限结构个数的一个基本工具，它计算了在个集合上产生 的等价类的个数由于许多计数问题都可以纳入这个表述框架，所以它的产生对组合学， 特别是计数理论的发展起了十分重要的作用，使得一类计数问题可以用这个定理来解决 柯西( c a u e l l y a u g u s t i n ，1 7 8 9 1 8 5 7 ，法) 首次在1 8 4 5 年的“m e m o i r e s u rd i v e r s e sp r o p r i e t e sr e m a r q u a b l e sd e ss u b s t i t u t i o n sr e g u l i e r e so ui r r e g t l l i e r e s ，e td e ss y s t e m e sd es u b s t i t u t i o n s c o n j u g e e s ( s u i t e ) ”中谈到这一定理的模糊形式弗罗贝尼乌斯( f g f r o b e n i u s l 8 4 9 - - 1 9 1 7 ， 德) 在1 8 8 7 年的论文“u b e rd i ec o n g r u e n zn a c he i n e ma u sz w e ie n d l c h e ng r u p p e ng e b i l d e t e n d o p p e l m o d u l ”中给出了这一定理较清晰的论述并给出一个证明而伯恩塞德( w i l l i a m b u r n s i d e ，1 8 5 2 - - 1 9 2 7 ，英) 的“奇数阶群的一些性质”在1 9 0 0 年发表，他再次提出了这一 定理波$ t j 、w _ ( p 6 1 y a ，1 8 8 7 1 9 8 5 ，匈) 在1 9 3 7 年的“关于群、图与化学化合物的组合计数方 法”中对这一定理加以精确化，并用于研究组合学中的计数问题，因此后来学者建议把这 6 第一章引言 一引理称为c a u c l l y - - f r o b e n i u si 理 p 6 1 y a 计数定理最初足为了解决化学碳水化合物的计数1 8 7 5 年，凯莱曾运用树图并 应用生成函数给出过有关化学碳水化合物计数的方法，但此法复杂且难以操作，所以 这种方法在当时没有产生太大的影响，之后，一些化学家和数学家们也提出了许多方法 来解决有关化学碳水化合物计数，直到二十世纪2 0 年代，由一位化学家a c l u n n 和数学 家j k s e n i o r 的题为“i s o m e r i s ma n dc o n f i g u r a t i o n ”论文中指出排列群的数学理论系统方法 正好适用于同构体的计数问题，这是波利亚重要工作的先声波利亚计数理论不仅对化合 物计数研究很重要，而且也足图论和组合学发展的一个里程碑1 9 3 7 年，波利亚在“关于群、 图与化学化合物的组合计数方法”的论文中提出一个中心定理，即p 6 1 y a 计数定理p 6 1 y a 定 理在2 0 世纪中叶被予以推广，d eb r u i j n 定理即是显著一例，它从两个方向推广- j p 6 1 y a 定 理，一是利用组合学中的另一有力工具一麦比乌斯反演一去计算一般有限群作用下的轨 道，二是把p d l y a 定理纳入群不变量理论的架构，变成是某条定理的特殊情况 图论是组合数学的一个分支，图论中的图指的是一些点以及连接这些点的线的总 体通常用点代表事物，用连接两点的线代表事物问的关系，图论则是研究事物对象在 上述表示法中具有的特征与性质的学科关于图论的文字记载最早卅现在欧拉1 7 3 6 年的论 著中，他所考虑的原始问题有很强的实际背景图论的发展已有2 0 0 多年的历史，它发源 于1 8 世纪普鲁士的柯尼斯堡在柯尼斯堡的普莱格尔河上有七座桥将河中的岛及岛与河岸 联结起来，一共有四块陆地问题是要从这四块陆地中任何一块开始，通过每一座桥正好 一次，再回到起点欧拉在1 7 3 6 年解决了这个问题，他用抽象分析法将这个问题化为第一 个图论问题：即把每一块陆地用一个点来代替，将每一座桥用联接相应的两个点的一条 线来代替，从而相当于得到一个图欧拉证明了这个问题没有解，并且推广了这个问题， 给出了对于一个给定的图可以某种方式走遍的判定法则这项工作使欧拉成为图论( 及拓 扑学) 的创始人这是图论发展的萌芽时期最具代表性的问题，那时不少图论问题都是嗣 绕着游戏而产生的 从1 9 世纪中叶到1 9 3 6 年，图论主要研究一些游戏问题：迷宫问题、博弈问题、棋盘 上马的行走线路问题一些图论中的著名问题如四色问题( 1 8 5 2 年) $ 1 h a m i l t o n 环游世界问 题( 1 8 5 6 年) 也开始出现同时出现了以图为工具去解决其它领域中一些问题的成果1 8 4 7 年 德国的克希霍夫( g r k i r c h o f f ) 将树的概念和理论应用于工程技术的电网络方程组的研究 1 8 5 7 年英国的凯莱( a c a y l e y ) 也独立地提m 了树的概念，并应用于有机化合物的分子结构 的研究中1 9 3 6 年匈牙利的数学家哥尼格( d k o n i g ) 写出了第一本图论专著有限图与无限 图的理论( t h e o r yo fd i r e c t e da n du n d i r e c t e dg r a p h s ) 标志着图论作为一门独立学科 四色猜想是世界近代三大数学难题之一，毕业于伦敦大学的弗南西斯格思里 ( f r a n c i sg u t h r i e ) 发现了一种有趣的现象：“每幅地图都可以用四种颜色着色，使得有共同 7 1 2 组合数学的研究现状及发展 边界的国家着上不同的颜色”这个结论能不能从数学上加以严格证明呢? 1 8 5 2 年l o 月2 3 日， 他的弟弟就这个问题的证明请教他的老师、著名数学家德摩尔根，摩尔根也没有能找 到解决这个问题的途径，从此，有越来越多的数学家和对此感兴趣的学者们开始研究这 个问题到目前为止，最好的结果可能就是，1 9 7 6 年，在j k o c h 的算法的支持下，美国数学 家阿佩尔( k e n n e t ha p p e l ) 与哈肯( w o l f g a n gh a k e n ) 在美国伊利诺斯大学的两台不同的电子 计算机上，用了1 2 0 0 个小时，作了1 0 0 亿判断，终于完成了四色定理的证明四色猜想的计 算机证明轰动了世界，当时中国科学家也有在研究这原理它不仅解决了一个历时1 0 0 多 年的难题，而且有可能成为数学史上一系列新思维的起点虽然到目前为止，它还没有被解 决，但是人们在寻求解决方法的过程中，提出了很多新的理论和思想，可以说它对图论的 发展，尤其是对着色理论、平面图理论、代数拓扑图论等分支的发展起到了推动作用 1 9 1 2 年b i r k h o f f 为解决著名的四色问题首次引进色多项式的概念，1 9 3 2 年w h i t n e y 进一 步将此概念扩充到任意图上，并建立了一些基本结果，其后关于色多项式的研究深人开 展，积累了许多成果，并产生不少新课题，诸如，对色多项式系数的研究、如何去判断一 个多项式足否足色多项式以及图的色唯一性等等，成为图论中一个热门研究领域人们一 直都热衷于色多项式系数的研究，目的是想找出什么样的多项式足色多项式，有关色多 项式系数的一些结论总结如下： 1 设g 是含m 条边1 个分图的n 阶图，则 ( a ) x ( g ，k ) 是n 次多项式； ( b ) x ( a ，k ) 中护的系数为1 ； ( c ) x ( g ，k ) 中护一1 的系数为一m ； ( d ) x ( a ，k ) 中常数项为0 ； ( e ) x ( g ，七) = 兀x ( a i ，七) ，式中g 是g 的第i 个连通分支； ( f ) x ( g ，七) 中系数非零的最低次幂是g 的连通分支数目1 2 g 是一个图，有n 个顶点，m ( m 1 ) 条边，贝o x ( a ，k ) 中一定含有k ( k 一1 ) 的因式； 3 令g 是一个图，n 个顶点，m ( m 1 ) 条边，则) ( ( g ，k ) 中系数的和为零 4 若图g 的色数是七，当仇七时，则o ，m 一1 是图g 的色多项式的根； 5 图的色多项式无负根 1 2 组合数学的研究现状及发展 美国政府成立了离散数学及理论计算机科学中一i , , d i m a c s ( - 与p r i n c e t o n 大学，r u t g e r s 大 学，a t & t 联合创办的，设在r u t g e r s 大学) ，该中心已是组合数学理论计算机科学的重要研 8 第一章引言 究阵地美国国家数学科学研究所( m a t h e m a t i c a ls c i e n c e sr e s e a r c hi n s t i t u t e ，由陈省身先生 创立) 在1 9 9 7 年选择了组合数学作为研究专题，组织了为期一年的研究活动日本的n e c 公 司还在美国设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该 中心主任r t a r j a n 是组合数学的权威美国另外一个重要的国家实验室s a n d i a 国家实验室 有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究， 在美国政府以及国际学术界都具有很高的地位由于生物学中的d n a 的结构和生物现象与 组合数学有密切的联系，各国对生物信息学的研究都很重视，这也足组合数学可以发挥 作用的一个重要领域据说i b m 也将成立一个生物信息学研究中心由于d n a 就是组合数 学中的一个序列结构，美国科学院院士，近代组合数学的奠基人r o t a 教授预言，生物学 中的组合问题将成为组合数学的一个前沿领域t h o m s o ns c i e n c e 公司创刊的一份电子刊物 离散数学和理论计算机科学，它的内容涉及离散数学和计算机科学的众多方面由于计 算机软件的需求，组合数学已成为一j 既广博又深奥的学科，需要很深的数学基础，逐 渐成为了数学的主流分支本世纪公认的伟大数学家盖尔芳德预言组合数学和几何学将足 下一世纪数学研究的前沿阵地这一观点得到国际数学界的赞同加拿大在m o n t r e a l 成立了 试验数学研究中心，他们的思路可能和吴文俊院士的数学机械化研究中心的发展思路类 似，使数学机械化，算法化，不仅使数学为计算机科学服务，同时也使计算机为数学研 究服务除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥 地利、瑞典、意大利、西班牙等国家都建立了各种形式的组合数学研究中心近几年，南 美国家也在积极推动组合数学的研究澳大利亚，新两兰也组建了很强的组合数学研究机 构值得一提的足亚洲的发达国家也十分重视组合数学的研究日本有组合数学研究中心， 并且从美国引进人d 。，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这 样使日本的组合数学这几年的发展极为迅速台湾、香港两地也从美国引进人4 ，大力发 展组合数学新加坡，韩国，马来西亚也在积极推动组合数学的研究和人爿培养台湾的数 学研究中心也正在考虑把组合数学作为重点方向来发展世界各地对组合数学的如此钟爱 显然是有原因的，那就是没有组合数学就没有计算机科学 1 3 主要内容介绍 色轨道多项式以及色本原多项式是杜清晏教授首次提出来的，本文就色轨道多项式 以及色本原多项式的相关性质以及它们在化学上的应用作了一些讨论，本文大致包含三 部分的内容，第一部分是引言，主要介绍了组合数学的历史与发展，第二部分是一些基本 概念、引理和定理，第三部分进一步讨论了关于p 一图的色轨道多项式，色本原多项式的一 些性质，以及与项链的具体的计数公式相关的性质，还举了一些相关的例子在第二章介 绍了它们的概念以及一些已有的相关结论，第三章是本文的主要结论 9 第二章预备知识 2 1 基本概念 本文涉及到的有关组合数学和图论的基本术语，请参见【1 】， 2 】 定义2 1 1n 阶标号图1 9 是指一对( y ( g ) ，e ( 9 ) ) ，其中y ( 9 ) 是一个n 元集合，且e ( 9 ) 是 y ( 9 ) 上的二元子集，y ( 9 ) 和e ( g ) 中的元素分别称为图9 的顶点集和边集 令表示n 元集合 l ，2 ，礼) ，在所做的加法运算是模n 的，对于n 阶标号图夕， 设v ( g ) = ，g n 表示顶点集是的所有标号图的集合，g ，h g 。，当e ( g ) e ( ) 时， 记为g 设a y ( 9 ) ，9 陋】表示a 的导出子图，在没有特别明确地强调图的标号的情 况下，通常的图就用g ，h 来表示，g ，r ：d 。，分别表示n 阶圈，路，空图，完全图 令) ( ( 9 ) 表示图g 的顶点着色的色数，x ( g ，后) 表示图9 的色多项式，表示不小于x 的最小整 数设( m ，n ) 和h ，几】分别表示正整数i t i 和n 的最大公约数和最小公倍数，仇ln 表示i n 整除n ， 妒( n ) 是欧拉函数，即小于等于n 且与n 互素的正整数的数目，设九( 礼) = r o l l m 几，( 仇，n ) = d ) 和蛐( 礼) = i 咖( n ) i ，容易得到妒d ( 几) = 妒( n d ) 定义2 1 2 翻 1 ) 令品是集合 k 上的对称置换群，即是 k 上的所有置换的集合，e 是岛的单位元，且厶= e ) 是晶的单位子群； 2 ) 若姨& 的一个子群，则p 以一种自然的形式作用在g 。上：对任意的7 r p 和9 g 。，丌( 夕) g 。，且其边集是l r ( e ( g ) ) = 7 r ( i ) ，丌( 歹) ) m ，j e ( 夕) ) ； 3 ) 当7 r ( 9 ) = g ( i e 7 r ( j e 7 ( 9 ) ) = e ( 9 ) ) ，称7 r 是9 的自同构群，夕的所有的自同构构成的集合记 为a ( 9 ) 若k ，令s n k = 7 r 鼠1 7 r ( 乱) = 让，对于任意的u k ) ，称s n k 是s 的k 稳 定子群： 4 ) 对于任一置换7 r 岛，用c ( 丌) 表示置换丌循环分解的圈数一个置换被称为是正则的，若 它的每个圈的长度相等 定义2 1 3 【司令腹品的一个子群，仃阶p 置换一图g 或简单地说p 图醍指p 作用在g n 上产 生的一个轨道，当9 g ，称g 是9 的一个p 一图且9 是g 的一个标号图特别地，有下面的结论 1 ) 一个晶图被称为是凡阶非标号图； 2 ) 一个s n k 一图被称为是几阶局部标号图； 1 0 第二章预备知识 3 ) 一个厶图被简单地看作是标号图； 4 ) 当p = a ( ) ，g g 时，其中 c n ，称标号图愚和9 分别是p 一图g 的结构图和约束图由标 号图 和9 所确定的p 图g 称为是s c - i 蚕； 5 ) 当p a ( 9 ) 时，p 图就被称为图9 的一个自同构子群图，或简称为4 一图； 6 ) 设p 和促品的子群，且9 ，h g 。，今g 和鼢别表示一h f 社- q p 一图和q 一图，当9 笺h 时，可以写为g 兰，。或g 笺h ，这是合理的，因为p 一图g 本身就是一个等价类； 7 ) 设9 g ，且g 是图夕的p 一图，当9 具有某些性质时，可以说弛有这些性质比如说夕是 连通的，则弛是连通的 定义2 1 4 【翻设9 g 。，9 的一个正常七着色是指这样的一个函数盯：y ( 9 ) 一 l ，2 ，七 ， 且具有性质：当i 和衍目邻时，盯( i ) 盯( j ) ，对于每个正整数后，令x ( 9 ，七) 表示9 的一个正常七着 色 众所周知，x ( 9 ，七) 是阶为n 的具有整系数的一个多项式 定义2 1 5 翻 1 ) 令丌岛，图9 的一个( 丌，后) 着色是这样定义的：盯是图9 的一个正常诺色，且满足口( 丌( u ) ) = 盯( ) ，对所有的u y ( 9 ) ； 2 ) 令g g ，丌& ，且7 r 可以分解为圈c 1 ，q ，图g 与丌相关的商图g 丌是这样定义 的：v ( a ) = a ，q ，c m ) ，且g 和岛相邻当且仅当存在u a 和u c j ( u 和雄 图夕中相邻) ，且当g 中有9 的相邻顶点时，则在g 丌的g 中有环，这时9 7 r 无正常着色， 当所有的g ( 1 i m ) 均无9 的相邻顶点时，9 丌是简单图； 3 ) 令7 r & ，对每个k 1 ，定k x ( g ，丌，七) 表示图9 的( 7 r ，忌) 着色 定义2 1 6 【翻今陡& 的一个子群，g 是n 阶p 一图，丌p ，给出如下的定义： 1 ) 若k x ( 9 ) ，且( g ，k ) = ( 9 ，o ) l g g ，其中仃是图9 的一个正常七着色 ，令( 9 ，口) u p ( g ，) ，定义7 r ( 9 ，盯) = ( 丌( 9 ) ，仃7 r 一1 ) ，这样的话，就得到了p 在u p ( g ，南) 上的自然作用； 2 ) g 的一个七着色，是指p 怍用在u e ( c ，七) 上的一个轨道； 3 ) 对于每个正整数后，令x p ( g ，忌) 表示g 的七着色的数目，称x p ( c ，七) 是p 一图g 的色多项式或 图9 的色轨道多项式，其中9 g ； 4 ) 令_ p ( g ，) = l p n a ( g ) l x p ( a ，后) ，其中9 g ，称勋( g ，南) 是p 一图g 的色本原多项式 11 2 2 基本引理和定理 定义2 1 7 【翻设9 g 。，睁p 是a 例的子群，脚g 分别是9 的q 一图和p 一图，若叉p ( g ，凫) = 叉q ( g ，七) ，则称盼p 关于9 是一致的，i s ) o q 忌p 从上面的定义，可以看出关系“忌”是等价关系，若q 矛e i p 是a ( 9 ) 的子群，又由于叉p ( g ，k ) = i pna ( g ) x p ( g ，七) = i p x p ( g ，庇) ，叉q ( ，尼) = i qna ( g ) i x p ( h ，七) = i q x q ( h ，后) ，从而 有x p ( g ，k ) = ( i p i i q ) x q ( h ，尼) 定义2 1 8 设g 是一个图，u ，u y ( g ) ，x e = u ，u ) ，w 冒v ( g ) 1 1 图g 。e 的定义如下： ( a ) v ( a 0e ) = ( v ( a ) 一 u ，u ) u 叫) ； ( b ) e ( g oe ) = z ，y ) e ( g ) i z ，y u 或u ) u x ，叫 i 在g 中z 一乱或z u ； 2 ) 图g + e 和g e 的定义如下： ( a ) 若e 岳e ( g ) ，用g + e 来表示在图g 上加一边e 而得到的图； ( b ) 若e e ( g ) ，用g e 来表示在图g 上去掉一边e 而得到的图 定义2 1 9 在集合a 上定义一种关系“ ”且其满足： 1 对集合a 中的一切元素a ，都满足a n ； 2 对于集合a 中两个元素n 并口6 ，如果a - b ，且6 a ，则a = 6 ； 3 对于集合a 中三个元素a 、6 和c ，如果a _ b ，2 _ b c ，则a ，妒( n d ) 砭( 七) 命题2 2 3 【3 i 殳h ，g g 。，n = r t ，h 竺g ，g 兰7 g ，e ( h ) = 作，i + 1 小) 和e ( 9 ) = i ，i + r l ie n ) g 是由构造图h t t 乡o 束图g 需确定的s d 图，e p = a ( h ) 则 当n 是奇数时， x p ( g ，惫) = 击 d i 。，即妒( n d ) ( 七一1 ) 4 ( 4 ，7 + ( 一1 ) 4 ( d ，7 ( 七一1 ) 】( d ，7 ) 当谛廓是偶数时， x p ( g ，七) = 去 妒( n d ) ( 七一1 ) 抛7 + ( 一1 ) 讹7 ( 七一1 ) p a l n ，d t r + 罢【( 七一i ) t + ( 一1 ) 。( 七一1 ) r 2 ) 当旋偶数，提奇数时， x p ( e ，k ) = 去 妒( 凡d ) 【( 七一1 ) 讹+ ( 一1 ) 洲7 ( 七一1 ) p a l n ，d 伊 + 罢七( 忌一1 ) 。2 【( 七一1 ) 。+ ( 一1 ) 。( 忌一1 ) 】( r 一1 ) 2 ) 令，d ( n ) 表示满足护l n 的最大整数i n 命题2 2 4 翻设 ，9eg 2 。，h 型q n ，g 竺n k 2 ，z ( h ) = “i ，i + 1 2 。) 和e b ) = i ，i + n m 2 n g 是由构造图 和约束图9 需确定的s d 图，且p = a ( ) 则 x p ( g ，尼) = 击d l n ，f 2 ( d ) ：，2 机) t ( n d ) k ( k 一1 ) 】d + 礼【】i ：( 免一1 ) 】n 2 命题2 2 5 【翻设 ，g g n ，h 兰g ，g 兰0 几，g 是由构造图尼和约束图夕需确定的s d 图， e p = a ( ) 则 当n 是奇数时， x p ( o ，克) = 击【d i 。妒( n d ) k d + n k ( n + 1 ) 2 】 当n 是偶数时， x p ( g ，七) = 去【m ( i o ( n d ) k d + 掣尼n 2 1 4 第二章预备知识 命题2 2 6 【翻设九，g g 。，h 兰g ，g 竺，漩由构造图 和约束图9 所确定的s d 图， 且p = a ( ) n x p ( a ，七) = 击七( 七一1 ) - ( 七一几+ 1 ) 1 5 第三章主要结论 3 1 关于色轨道多项式以及具体的项链计数公式的性质的讨论 在色轨道多项式的集合上定义一个二元关系：设g , 矛i h 分别是g 的p 图和h 的q 一图，若 对于每个非负整数k ，满足x p ( g ，后) x q ( h ，忌) ，则记为x p ( g ，忌) x q ( h ，后) 命题3 1 1 在【2 上定义的“ ”是个半序关系 证明：为了说明“ ”是个半序关系，只需验证其满足定义首先自反性是显然的；其次， 如果有x p ( g ，七) - 1x q ( h ，角) 和x q ( h ，k ) x p ( a ，七) ，且l j x e ( a ，k ) x q ( h ，后) 和 x q ( 日，k ) x p ( g ，k ) 则对所有的k 成立，已o x p ( a ：k ) = x q ( h ，忌) ；最后，如果有x p ( g ，k ) _ x q ( h ，尼) ，x q ( h ，后) x r ( i ，后) ，目i j x p ( a ? 后) x q ( h ，七) ，x q ( h ，七) x r ( i ，后) ，贝u 有) ( 尸( g ，忍) ) ( r ( ，_ l c ) ，x p ( g ，惫) - 4x n ( r ：惫) 也就成立了 据群论的知识有不等式厶p a ( 9 ) ，其中p 是月( 夕) 的子群，再根据定理2 2 1 则有不等式) ( j 。( 日，七) 2x p ( a ，后) x a ( 9 ) ( r ，后) 成立，其中g 、h 和r 分别足9 的p 一图、厶一图 和a ( 9 ) 图，k 是任一非负整数，这也说明了上而定义的半序集是有界的 对于一个图，它的子图的自同构群不一定是原图的自同构群，根据这一点，可以把定 理2 2 7 的条件放宽一些 定理3 1 1 设夕，h g 。，蹄q 是品的子群，q p ，令g 和盼别是夕的p - 图和q - 图，若hc g ，且q n a ( h ) p na ( 夕) ，则有x p ( h ，后) x q ( g ，后) 证明：证明详见文献【3 】 类似于上面，也可以利用定理2 2 7 ，来定义集合和关系，这两个定义没有多大的区 别，在这儿就不去定义了 由定理2 2 2 和引理2 2 2 ，有下面的结论： 定理3 1 2 设p 是鼠的一个子群，g g n ，使9 的p 图，且七1 ，则有： 1 ) 当i p n a ( 9 ) i = 1 时，叉p ( g ，南) = x ( g ，后) ； 2 ) 当0 k 2 = p ( 2 ) ) ( ( 暖，k ) - t - 妒( 1 ) x ( c g ，k ) = 天( 四，k ) + x ( 曙，k ) = x ( c 4 ，k ) + x ( h 2 ，k ) = ( 七1 ) 7 ( 南一3 ) 4 - ( 七一1 ) 3 ( 七3 2 k 2 一k + 3 ) + 忌( 七一1 ) ( 七一2 ) 2 ( 一5 k 3 + 3 2 k 2 7 0 k + 5 0 ) 当约束陶一定时，圈一s c 图的色本原多项式足确定的，反过来当某个多项式足圈的 色本原多项式，那么它对应的约束图足不是一定的呢? 这有待于进一步去解决 定理3 1 9 设g 笺gu 是9 g n + m 的无标号图，且p = a ( 9 ) ，则： 2 2 第三章主要结论 1 ) 当几和m 是两个不同的奇数时， - p ( g ，七) = 妒( 礼d ) f ( 七一1 ) d + ( 一1 ) d ( 七一1 ) 】 d i 几，d l 妒( m d ) ( 尼一1 ) d + ( 一1 ) d ( 七一1 ) 】 d i m d 1 2 ) 当n 和破两个不同的偶数时， - p ( g ，七) = ( 妒( 凡d ) 【( 七一1 ) d + ( 一1 ) d ( 南一1 ) 】- f 等后( 后一1 ) n 2 ) d i n ，d # l 。 ( 妒( m d ) 【( 七一1 ) d + ( 一1 ) 4 ( 七一1 ) 1 + 等尼( 七一1 ) m 2 ) d i m ，d # l “ 3 ) 当凡是奇数，m 是偶数时， 叉p ( g ：七) = 妒( n d ) 【( 血一1 ) d + ( 一1 ) d ( 七一1 ) 】 d i n ，d 1 ( 妒( m d ) 【( 七一1 ) 4 + ( 一1 ) 4 ( 后一1 ) 】+ 等角( 七一1 ) “2 ) d i m ，d 9 1 4 ) 当提偶数，m 是奇数时， _ p = ( 妒( n d ) 【( 七一1 ) d + ( 一1 ) d ( 忍一1 ) 】+ 芸七( 七一1 ) n 2 ) d i n ，4 1 。 妒( m d ) 【( 尼一1 ) 4 + ( 一1 ) 4 ( 七一1 ) 】 d i m ，4 # 1 证明：设丌a ( g ) ，7 r n a ( 岛) ， f f m a ( ) ，记7 r = ( 丌n ，7 r 。) ，7 r i 。和丌i 。表示置换丌限制 在g 和上的置换，其中n 和m 是两个不同的非负整数，则根据p 一图的色本原多项式的定 义有 _ p ( g ，后) = x ( g ，7 r ，后) 7 r a ( g ) = x ( g ，7 1 n ，后) ) ( ( c m ，后) 丌i ”n a ( 1 ：k )7 r i n m a ( i ? m ) 再据命题2 2 1 就有了上面的结论 对于多个圈的并，也有类似的结论；当然对于构造图是一些圈的并，约束图是上一章 命题中提到的一些约束图的并，这样得n s c 图也有类似的结论记 i om 是奇数， 啦2 11 族偶数 2 3 3 2 举例 定理3 1 1 0 设g 竺u ：= 1g 。是9 g 。，+ n ：+ + 。的无标号图，且p = a ( 9 ) ，则： 叉j p ( g ，忌) = n ( 妒( 毗d ) ( 后一1 ) d + ( 一1 ) d ( 七一1 ) 】+ 啦等尼( 后一1 ) 等) o = 1d i n 。，d 1 3 2 举例 这一节的主要内容是用前面介绍的p 图g 的色本原多项式来计算具体图的色本原多 项式，而图是化学上的一些分子式，这也是色本原多项式的一种应用最早把图用于纯化 学内容的足c r u mb r o w n ，他用图来描述共价键的结构式在化学上由c 、h 两种元素构成的 分子式有很多，下面就对其几类进行一些分析，总的要求是：设h 有k 个不同的能级，连 结同一个c 的h 具有不同的能级，所谓能级是指微观粒子所处的能态，微观粒子系统在 束缚态中只能处于一系列不连续的，分立的稳定状态，这些状态分别具有一定能量，它 们的数值各不相等p =