（运筹学与控制论专业论文）图的多项式.pdf

声明 本人郑重声明：本论文的所有研究工作都是在导师郝荣霞副教 授的悉心指导下，由本人独立创作完成论文中所引用的已知结论均 可参见相应文献，参考文献已在论文的最后列出特别，未经作者本 人许可，任何擅自更改、抄袭或剽窃本论文之内容的行为，都将承担 相应的学术和法律责任 ；i!1!l!，。，。，。， 摘要 在研究图的相关性质及应用的很多文章中用相关的多项式不变量来刻画图 类，如特征多项式，匹配多项式，色多项式，多色多项式，t u t t e 多项式，亏 格分布多项式，全嵌入分布多项式等，如何求出图的这些多项式不变量，并通 过这些多项式讨论图的相关性质成为近些年来一直关注的课题 该文是本人于研究生阶段在图的色多项式，色唯一性，伴随多项式，图的 全嵌入分布方面得到的结果的总结 本文共分为四章： 第一章综述本文所研究课题的背景、发展现况及原有结论，阐述本人所做 工作 第二章讨论图的色唯一睫；在文献【1 8 】的基础上对两类图z 。u 兀。u 兀，u m ，- 和r ，u 只。：u - r ，u m k l 的补图的色唯一性进行讨论，得到结论： ( 1 ) 若g = 瓦，u l ：u ，u l ，u m 甄，其中瓦。( f 。j 。2 。) 足不可约图， 且( f 。f 。) ( 1 ，1 ) ，( 2 。l ；。) ( 1 ，2 ) ，则召是色唯一的 ( 2 ) 若g = r u r ：uu 只。，u m k l ，其中r 。是不可约图，n ；6 ，则 孕色唯一 第三章给出两类图的伴随多项式；推广已有图d 。，r 到两类新图d ：，只， 得到它们的伴随多项式： 慨萨。，毫矿鬻砦箍紫c 喇圳 其中0 1 ( p ) = ( g ，卢) + ( 只一1 ，p ) ，口2 ( p ) = h ( g ，p ) 把川= 。毫，1 堕糌墨箍掣( 喇i ) 其中。l ( 肛) = 2 ( g ，p ) + 肛 2 ( 只一l ，p ) ，n 2 ) = 肛 ( 只一l ，肛) 2 ( g ，p ) 一，眈( 只一l ，肛) 摘要 并讨论了当t = 4 时的不可约性 第四章给出两个图类g 和镑的全嵌入分布多项式；通过构造这两个图类 相应的覆盖矩阵，求出覆盖矩阵的秩分布多项式，从而计算出这两类图的全嵌 入分布多项式： ( 1 ) 图毋的垒嵌入分布多项式为 其中 其中 r 坛( z ，口) = 2 4 一d 鼻1 ( ) + ( 6 一4 ”) ( 。一2 ) = 0 + ，薹。( 。协竹2 ，蚴邓 ( 2 ) 图岛；的全嵌入分布多项式为 堍o ，p ) = 三* + t ( z ，f ) + 喙p ) 一玉( 可2 ) 工2 ，+ l ( b 2 ，+ 1 ，。) = ( 2 0 0 2 2 + 1 3 6 z + 4 0 ) l 2 ，一l ( b 打一l ，。) 埘+ 5 ) 萎( 7 斗o m s o r 一1 他他2 ) m ( - 钟4 2 m 关键词：色多项式；色唯一性；伴随多项式；不可约图；亏格分布多项式 全嵌入分布多项式 2 七产 2 + ； 一 d 一 1 =+ 1z 斟 + 忙十k b d k z+1 | | g 女r d 塑黑 一3 a b s t r a c t i nt h el i t e r a t u r e 、v e 矗n dm a n yp o l y n o m i “sa s s o c i a t e dt og r a p h s ，l i k et 沁 c h a r a c t e r i s t i c ，t h em a t c l l i n g s ，t h ec h r o m a t i c ，t h ep o l y c h r o m a t i c ，t h c i l l t t e ，t h e 臣e n u sd i s t r i b u t i 。na n dt h et o t a le n l b e d d i n gd i s t r i b u t i o np o l y n o m i a k h o wt o o b t a i nt h e s cd 0 1 v n o m i a li n r i a n t si no r d c rt od i s c u 8 st h eg r a p hp r o p e r t i e 8b y t h ei n f o r m a t i o nt h e yo f f e r e db e c o m e sah o tt o p i c t h i sp a p e rm a i n l yc o m p r i s e so fw h a tih a v eo b t a i n e di nt h ef i e l d so fc h r o - m a t i cu n i q u e n e s s ，a d j o i n tp 0 1 y n o m i a l sa n da l s ot h ct o t a le m b c d d i n gd 】s t r i b u t i o n p 0 1 y n o i n l a l sd u r i n gm ys t u d yi nt h er e c e i l tt h r e ey e a r s - c h a p t e ro n et o t a l l yd e s c r i b e st h eb a c k g r 。u n d ，t h ed e v e l o p m c n ts i t u a t i o n a n dt h eo b t a i n e dc o n c l u s l o n si nt h e 丘e k l so fw h a tw i l lb ei n v e s t i g a t e di n t h j s p a p e r a n dt h c ns i m p l ym e n t i o n sw h a tih a v ed o n e i nc h a p t e rt w o ，w em s c u s st h ec h r o m a t i cu n i q u e n e s so ft h eg r a p h sb a s e d o nt h c 也e s i s 【1 8 1 ，w ed i s c u s st h eu n i q u e n c s so ft h ec o m p l e m e n to fg r a p h s 。u 2 u 咒，u m k la n d r 。u r 。u r ，u m 1 ，a n do b t a j n t h e f o l l o w i n g r e s u l t s ： ( 1 ) i f g = 已。u 写。u u 乃，u m 风，w h c r c 。( k k l ；。) a r ea l l i r r c d u c i b l e g r a p h s ，a n d ( 2 f ，2 ) ( 1 ，1 ) ，( f f ) ( 1 ，2 ) ，t h 衄召i sc h r 。i n a t i c a l l yu n i q u e ( 2 ) i fg = e qu e 硷u - u 咒，u m k l ，w h e r er ，i si r r e d u c i b l c ，f o rn ，三6 ， t h e n 召i sc h t o m a t i e a l l yu n i q u e i nc h a p t e rt h r e e ，t h ea d j o i tp o l y n 。m i a l s 。ft w o “n d so fg r 印h sa r eg i v e l l ，cg e n e r a l i z et 啪k i n d so fg r a p h sd a n dj _ t ot h en e wt 、v ok n d 8o fg r a p h s 摘要 职a n d 咒，a n do b t a i nt h c i ra 由o i n tp o l y n o 工1 1 i a l s 鹊f o l l o w i n gr e s p e c t i v e l y ( 珑，p ) = 卢 键2 手5 * ! ! 二1211 1 些塑! 坐2 f ! ! 二里! 1 2 竺! 坐2 ( 礼一七一i 1 ) ! ( 2 七一礼+ i + 1 ) ! w h e r e 血l ( p ) = ( g ，卢) + ( 只一l ，p ) ，0 2 ( 肛) = ( g ，卢) m r ，肛) = 矿 三与粤 l ( 七一1 ) ! 七肛n 1 ( p ) + ( 2 七n + 2 z ) 0 2 ( p ) ( 扎一七一2 。) ! ( 2 是n 十2 。) m 2 i ) w h e r e 0 1 ( “) = 2 ( c 五，肛) + p 2 ( 只一1 ，p ) ，n 2 ( 肛) = 肛 ( 只一l ，肛) 2 ( g ，肛) 一p h ( 只一1 ，肛) a n dt h c nd i s c u s st h ei r r e d u c i b 订i t yw h e ni = 4 i nc h 印t e rf o u r ，t h et o t a le m b e d d i n gd l s t r i b u t i o np o l y n o m i a l so ft w ok i n d s o fi n t e r e s t i n gg r a p h sga n d 鼻a f eg i v c no u tb yc o n s t r u c t m gt h e 王r e s p o n d i n g o v c r l a pm a t r i c c so ft h e ma n dc a l c u l a t i n gt h cr a n kd i s t r i b u t i o np o l y n o m i a l so f t h o s eo v e r l a pm a t r i c e s ( 1 ) t h et o t a lc 1 b e d d i n gd i s t r i b u t i o np o l y n o l l l i a lo fg 讧 r i ；扛，y ) = 2 4 7 一嘴l ( ) 十( 6 一4 ”) 扛一2 ) = 0 h p r o h e r o + ，霎。( 。埘，计2 艄邓刊 ( 2 ) t h et o t a l 眦b e d d i n gd i s t r i b u t i o np 0 1 y n o r n j “o f 岛i s 玉扛，) = 上z ”，( 马r + - ，9 ) + 吃，( z ) 一i ，( 2 ) l 2 ，+ 1 ( 口2 ，+ l ，z ) = ( 2 0 0 。2 + 1 3 6 z + 4 0 ) l 扑一1 ( j 吼，一1 ，z ) =2 + 功 一 骘 一_ 、 +0 h 蝌 +z + k d ki z + 1 | 1 0 r d 摘要 枷苏s ) 兰( 7 ：1 ) a o m s 旷。他地2 h 一钟。2 。 k e y 、m r d ：c h r o m a t i cp o l y n o m i a l ic h r o m a t i cu n i q u e n c s s ；a d j o i n tp o l y n o m i a l ；i r r e d u c i b l eg r a p l l ；g e u sd i s t r i b u t i o np o l y n o m i a l ；t o t “c m b c d d i n gd i s t r i - b u t i o np o l y n o m i a l 第一章内容简介 近些年运用图的色多项式、伴随多项式，结合代数性质对图的色性( 图的 着色、色唯一性、色等价、色数等) 进行的研究很活跃特别是对色唯一性、 色等价的研究b ，r k h 。圩【1 于1 9 1 2 年作为可能攻克四色猜想的一种手段提出 图的色多项式；rcr c 8 d ，1 9 6 8 年在文献2 1 中提到了色多项式的一些性质； c h 和w h i t e h c a df 3 ，4 于1 9 7 8 ，1 9 7 9 年提出色等价图和色唯一图，即用图的 色多项式对图进行等价分类；1 9 8 7 年刘儒英引进囤的伴随多项式，讨论图的 补的色唯一性，之后出现了一系列关于色唯一性的文章，刘儒英在文献5 1 和 中分别给出路r 和圈g 及墨。一e 只ur r ) 的色唯一陛，文献【7 和 f 8 中分别给出了一类树的补图和p 形树的色唯一性；李念祖等在文献 g 中 给出森林补图的色唯一性；董凤鸣和刘彦佩教授在文献1 0 、中给出失去两条弦 的轮图的色唯一性；郝荣霞和刘彦佩教授于文献 1 6 卜p 给出了去掉任意连续弦 的轮图的补图的色多项式，在文献f 17 1 中讨论了罔b 的色唯性等 图的色性作为图论的一个重要部分，应用广泛，目前已有一些运用对色多 项式、伴随多项式、特征标等参数( 量) 性质研究而得到的关于图的色唯一性、 图的色等价的结果但是由于寻找色唯一、色等价图类没有一般的方法，这方 面的工作有待进一步完善 刘儒英在文献 18 中介绍了图的特征标r ( g ) ，分别给出当r ( g ) = o 和 月( g ) = 1 时圈类所具有的性质并对图类进行描述，本文第二章中推“此结果， 讨论了血( g ) = 一1 和且( g ) = 一2 时的情形，并在文献 1 8 的基础上对两类图 正。，u 互。u l ，u m 耳l 和r ，u r ：u 晶，u m j 的补图的色唯一性进行 讨论，得到t ( 1 ) 若g = l u l ，u u 足，u m 1 ，其中l ，( f f i 。) 是不可约图， ( 1 ) 若g = 瓦u 咒，u u 靠，u m 1 ，其中矗，( f 2 。) 是不可约图， 箜二皇直墅煎金 7 且( 2 。2 n ) ( 1 ，1 ) ，( 2 。z ；。) ( 1 ，2 ) ，则百是色唯一的 ( 2 ) 若g = r ，u r ：u u r ，u m 甄，其中r ，是不可约图，n 。6 ，则 百色唯一、 由于很多时候，我们归根于研究图的伴随多项式，所以求出并讨论图的伴 随多项式的性质，如不可约性等也成为重要工作，即通过求某些图类的色多项 式伴随多项式并讨论其不可约性，试图讨沦更多图类的色唯一性；如董风鸣， k m k o h ，k lt o e 等在等 1 l ，1 2 ，1 3 ，1 4 文献中通过讨论了色多项式研究图的 色唯一性， n l b i g g s 在 15 j 等文献中给出一些研究色多项式的代数方法。但 目前为止，仅知道很少几类图的色多项式的具体计算公式，如上面提到的路r 和g 的色多项式，文献( 2 3 ，2 4 中给出的d 。的伴随多项式，以及文献f l o ，1 6 中得到了所有失去连续弦的轮图w 1 的补图的色多项式；文献f 1 0 ，1 7 中给出 了r 的伴随多项式的具体表达式本文在第三章中应用色函数f 2 5 ，2 6 的伴 随函数计算两类图磁和的伴隧多项式， nc 驯= 点。矿娑掣器高蔫掣c 叫删 其中8 i ( p ) = 而( g ，卢) + ( 只“瑚，如( p ) = ( g ，芦) 嘏川= 。磊旷1 坚鬻端筹蔫掣c 喇 其中凸t ( 弘) = 危2 ( c ：，弘) + p 铲( 只一j ，芦) ，8 2 ( p ) = 芦 ( 只一- ，p ) f 2 ( g ，芦) 一p 矗( 最一i ，卢) 7 并讨论了当i = 4 时的不可约性 本文第二章，第三章讨论的图皆为有限的，无向，无环简单图，凡未声明 的记号和术语均参见文献【2 0 j 、第二章介绍的定义、结果均适合于第三章 图的嵌入理论是拓扑学一个重要的研究方向，嵌入理论主要研究的问题有 图的可嵌入理论和计数理论1 9 7 9 年，刘彦佩教授在图的嵌入表示 3 0 的基 础上，揭示了联树法1 9 8 7 年，g r 0 8 s 和f u r s t 在文献【38 中系统地研究了 箜二主虚奎笪佥 8 嵌入空间的不变量及其层级关系，考察了一个图在所有可定向闭曲面上的所有 嵌入的分布，即亏格分布多项式 1 9 8 9 年，n u s t 等在文献口9 】中首先得到 c l o s c d - o n dl a d d e rl 。和c o b b l c s t o n ep a t h s 厶的亏格分布多项式，之后，g r o s s 等在文献f 3 1 】中得到了环束风的亏格分布的计算公式， 2 0 0 0 年t e s a r 在文 献f 3 2 中计算得到r i “g l el a d d e r s 岛的亏格分布多项式， 亏格分布多项式包含的信息量远远超过最大亏格与最小亏格，因此其难度 也相应加大，但是亏格分布多项式讨论的仅仅是一个图在所有可定向曲面上的 嵌入，1 9 9 4 年c h e n 等将亏格分布多项式推广到全嵌入分布多项式，即增加 了图在不可定向曲面上的嵌入的分布多项式，至此可以得到图的嵌入的全面信 息目前为止，已经得到全嵌入分布多项式的图类很少，方法也具有一定的局 限性在文献 3 3 】中c h e n 运用【3 4 中m o h a r 提出的覆盖矩阵。通过选择适 当的生成树，已经给出了如项链图r 及l 。， 的全嵌入分布多项式；j i nh o k w a k 在文献【3 5 】中通过加边术的方式给出了环束和双极图的全嵌入分布多项 式；本文第四章中，将文献【3 5 】中的图推广到两类标准类圈图g 和露，并通 过构造这两类图的覆蓥短阵得到它# 强全嵌入分布多项式： ( 1 ) 图g 的全亏格分布多项式为 0 ( z ，g ) ：2 4 一d 鼻。( g ) + ( 6 一4 ) ( z 一2 ) 其中 d ：( # ) = ( 1 + z ) 卜_ 1 d 备1 ( z ) + z ( 1 + ：) 卜_ d ；矗1 ( z ) 十2 二2 ( 七 + ，霎。( 。埘，计2 ，邓7 ( 2 ) 图强的全嵌入分布多项式为 龟，0 ，) = 工2 r + 1 ( 日2 r + - ，) + 卦( z ) ；，( 2 ) 箜二主良查笪佥 9 其中 l 2 r 十l ( b 2 ，+ l ，彳) = ( 2 0 0 。2 + 1 3 6 z + 4 0 ) l 2 ，一1 ( b 2 卜1 ，z ) 枷积s 川) 薹( 7 二1 ) a 1 。他拙2 ) m ( - 钟。2 2 m 凡在第四章中未提到的术语和名词均参见g r o s s 和t u c k c r 的著作 3 6 】或 者w h i t e 的著作 3 7 】 第二章图的色唯一性 2 。l相关定义 对于图g ，设y ( g ) ，e ( g ) 分别表示图g 的顶点集合、边集合，且设虿 表示图g 的补图g tug 2u g t 表示无公共顶点的t 个图g l ，g 2 ，g t 的并，n g 表示n 个g 的并以p ( g ，a ) 记图g 的色多项式，两个图g 和h 称为色等价的，当且仅当p ( g ，a ) = p ( 胃，a ) 如果从p ( g ，a ) = p ( h ，a ) 可推 出图g 和日为同构的，则称图g 为色多项式唯一的，以下简称色唯一的 定义2 1 1 若图g 的生成子图g o 的每个分支都是完全图，则称g o 为g 的 理想子图 用6 ；( g ) 表示图g 的具有p 一 个分支的理想子图的个数，p 是g 的顶点 个数，g 为g 的补图，则由文献【1 8 中的定理1 5 可得 p p ( g ， ) = 6 。( 0 ) m t = 1 其中 刈：= a ( a 一1 ) ( a 一2 ) ( a i + 1 ) 定义2 1 2 多项式 ( g ，。) = 留饥( g ) 护1 称为图g 的伴随多项式，将 ( g ，。) 表为； a ( g ，z ) = z “( g ) 1 ( g ，z ) 其中o ( g ) 是 ( g ，茹) 中系数不为零的且次数 最低的项的次数如果 l ( g ，o ) 在有理数域上不可约，则称g 是不可约图 若从 ( g ，a ) = ( 日，a ) 可推出g 呈日，则称图g 为伴随唯一的图g 是 色唯一的当且仅当其补图g 是伴随唯一的 引理2 1 3 口印设图g 有个分支g 1 ，g 2 ，g k ，则 ( g ，茁) = ( g l ，z ) ( g 2 ，z ) ( g ，z ) 第二章图的色唯一性 引理2 1 4 酬设图g 有p ( g ) 个顶点，g ( g ) 条边，a ( g ) 个三角形，且度序 列为d 1 ，如，- 一，d 口，则 6 0 g = 1 ； 6 1 g = 叮( g ) ； 幻c g ，= 4 c g ，+ ( 。g ! + 1 ) 一；薹a ； 定义2 1 5 设，( z ) = 矿十6 1 矿- 1 十b 2 z ( n 一2 ) + + 6 。为z 的多项式，其中 6 l ，6 2 ，k 为非负整数，定义 r c ，2 。一( 。；。) 十，乏i ： 且定义r ( g ) = 兄 ( g ，。) ) ，其中g 是圈， ( g ，。) 为它的伴随多项式 引理2 1 6 肛剐设图g 有七个分支g 1 ，g 2 ，瓯，那么 r ( g ) = r ( g ；) 设p ，口，a 和r 分别为p ( g ) ，g ( g ) ，j 4 ( g ) 和r ( g ) 的简记，且设q = p + 卢，卢一1 用r 和g 分别表示有n 个顶点的路和圈协：表示把玛的一个顶点和只一。 的一个l 度点重迭后得到的图，r 表示将b 。一2 的1 度点与蚝重迭后得到 的图将具有n 个顶点且度序列为( 1 ，1 ，1 ，2 ，2 ，2 ，3 ) 的树称为t 一形树，简 记为兀若具有n 个顶点的t 一形树的唯一3 度点到3 个l 度点的三条路长 分别为f l ，f 2 ，f 3 ，则此树用矗( z l ，2 2 ，f 3 ) 表示，以 ( f 1 ，f 2 ，f 3 ) 简记 ( l ( f l ，f 2 ，f 3 ) ) 引理2 1 7 口甜设g 为一个具有n 个顶点的非平凡图，则 ( i ) r ( g ) 1 ，且等号成立当且仅当g 兰r 2 ) 或g 竺k 3 ( i ) r ( g ) ：0 ，当且仅当g 望( 五或g 皇d 。或g 竺( n 4 ) ( 1 i i ) 冗( g ) = 一1 ，口1 ，当且仅当g 掣咒( n 6 ) 或g 型硒一e 第二章图的色唯一性 2 2主要结果 在文献【1 8 】中给出了引理2 1 7 中几类用r ( g ) 来表征的图类，本文推广 其结果，得到兄( g ) = 一1 及月( g ) = 一2 等时的具体图类，分别为图一1 中的 a ，b ，c ，d ，e 、f 图一1 中的不为三角形上的边均为长度不小于1 的路，圆表示圈长不小于 4 的圈，a 类中的图记为。，b 类中的图依次记为，m 。，k ；f 类中最后一 个图为凰 b c d x y 么_ _ 1 ，则将与h l 为 非平凡的连通图矛盾，所以日，与矗。o = 1 ，2 ，r ) 中某一个同构不妨设 凰兰，则同理可证马竺( j = 2 ，3 ，t ) ，结合( 2 3 ) 式得z = m = n 所以定理2 2 4 得证 定理2 2 5 若g = r ：u r 。u - u r ，u m a ，l ，其中r 、是不可约图，n ：6 ： 则召色唯一 证明由定理2 2 4 中式( 2 2 ) 及引理2 1 3 得 r 矿n ( 噩，) = 。h l ( 只。) ( 25 ) i = 1 = l 其中，o ( g ) = m + a ( r 。) 式( 2 5 ) 右端为不可约多项式在有理数域上的难一分解，则j 口互1 ，2 ，r ， 使得 ( 风，z ) = 一 l ( f n ，z ) ，目z ，口2o ( 26 ) l 且 设9 ( z ) = n 。日 l ( r 。，z ) ，则由引理2 1 ，6 及引理2 1 7 得 r 幻 ) ) = 一f b f 1 6 第二章圈的色唯一性 1 7 所以r ( h ( 日1 ，。) ) = r ( 9 ( z ) ) = 一l b i 若一i b i 一1 ，则即r ( ( 日1 ，z ) ) = 一l b l 一1 ，又由定理2 2 1 的证明过程可知必存在图，不妨设为g 。使得 r ( g 。，) = 一i b l 一1 ，( i = 1 ，2 ，2 ) ，即玩兰g 。，此与式( 2 6 ) 矛盾 所以只能为凰鲁u ，d r 。，又一l _ 日i 0 i 0 ：戛，“妻2 1 ( 三川) 。2 ( 咖“= 。聂，堇旷“( 。一女二川j 。2 ( 脚矿 = 。妻，“争( 。一：二赋咖“ = 。“争告攀蕞等端矿 + 扩 ” z 观+ z 肛 吼 、c + 驴 。脚馏唧 = = 压 冉 葛脚 哪 一 驴 一 揖 | l 堑三兰堕差里塑堡堕堑堑塞 2 4 当z 旦； ! ! 二型 ( 佗一5 一七) j ( 2 七一扎+ 5 )8 ( 南，几，“) ( n 5 ) 其中s ( 七，n ，p ) = i p 3 + ( 7 奄一n + 5 ) 肛2 + ( 1 2 七一4 n + 2 0 ) 肛+ ( 4 七一2 n + 1 0 ) 更一般地，我们也可以计算其他一些伴随多项式满足线性递推式的图的伴随多 项式的具体形式 定理3 2 8 ( 只，p ) = k 警 型! 坐! 幽坐二竺望型趔 ( n 一七一2 i ) ! ( 2 岛一礼十2 z ) ! m 2 i ) 其中。1 ( p ) = 2 ( c ；，p ) + 芦 2 ( 只一i ，肛) ，n 2 ( p ) = 肛 ( 只一i ，肛) f 2 五( g ；，肛) 一灿 ( 只一l ，弘) 证明 设 g = ( r ，p ) 扩 n 2 i 第三章两类图的伴随多项式 由引理3 2 4 中的( 3 6 ) 式，得 9 一 ( f 袅，p ) z 班一 ( f 刍+ l ，p ) z 2 件1 = ( 露，p ) 矿z 2 ( e ，p ) 护- 2 = 9 2 ( e + 2 ，p ) 。4 = z 2 卢 a ( 最，芦) + ( 最十。，弘) ) 。“ n 2 in 2 2 = p z 2 9 + 十肛z ( e ，肛) 护 n 2 件1 = p z 2 9 + + p z ( g + 一 ( e ”p ) z 2 2 ) 这里9 + 是细t 的简写于是上式可以重新写为 ( 1 一p z 一肛z 2 ) g + = ( 1 一芦茁) ( f 玉，肛) z 2 2 + ( f 戋+ l ，卢) 。2 计1 由引理3 2 ，5 中的( 3 9 ) ，( 3 1 0 ) 式，得 ( 1 p 。一p z 2 ) g + = 0 1 ( p ) z 班+ n 2 ( 肛) z 2 。+ 1 其中口l ) = 2 ( g ，p ) + p 2 ( 只一1 ，肛) ，且n 2 ( 肛) = 卢 ( 只一1 、肛) 2 ( g ，卢) 肛 ( 只一1 ，p ) j 这样， g ：f 去 0 1 ( p ) z 2 t + 口2 ( 卢) z 2 州】 9 。i i 二i ：i i i 【0 1 ( p j 。+ 0 2 【卢) 。j 与定理3 ，2 6 的证明过程相似地，可以得到定理3 2 8 注3 ：当 = 3 时，定理3 2 8 的形式与定理3 1 1 中的( 3 4 ) 式一致，即 定理3 2 8 是( 3 4 ) 式的推广当i - 4 时，由定理3 2 8 的结果得 推论3 2 9 蚓川2 。蓦扩4 两焉赫啪，w ) ( n 8 ) 其中s ( 而，n ，p ) = 七肛4 + ( 1 1 七一n + 8 ) p 3 + ( 4 0 七一8 n + 6 4 ) 芦2 + ( 5 2 七一1 6 n 十 1 2 8 ) p + ( 2 0 七一8 n + 6 4 ) ， 笪三童堕耋堕盟生堕垄垄塞 2 6 3 3关于 】( d ：，肛) 和九l ( 碍，p ) 的不可约性的猜想 在文献【2 4 ，1 7 中给出了图d 。和r 为不可约图的一些例子，这里我们 已经在推论3 2 7 和推论3 ，2 9 得到了 ( d ：，芦) 和 ( 砰，肛) 的具体表达式，运 用m a t h e m a t i c 可以计算得到下列结果，通过这些我们讨论它们的不可约性 ，l ，t l h l l ( d ：，肛) ( 叫，p ) d ：o ，p ) d 4 3 ，p ) d ：6 ，p ) 2 + 8 “+ 6 卢2 + p 3 8 十2 7 p + 2 6 卢2 + 9 肛3 + p 4 = 2 + 2 2 肛+ 4 6 p 2 + 3 4 卢3 + 1 0 p 4 + p 5 = 1 2 + 8 1 肛+ 1 6 7 肛2 + 1 4 9 肛3 + 6 4 卢4 + 1 3 p 5 + p 6 = 2 + 5 8 p + 3 0 1 p 2 + 6 1 6 p 3 + 6 2 4 p 4 + 3 4 2 ，户+ 1 0 3 肛6 + 1 6 2 7 + 矿 丘l ( d ；8 ，肛)= 2 + 7 4 p + 4 8 4 p 2 + 1 2 6 0 p 3 + 1 6 6 2 肛4 + 1 2 3 2 p 5 + 5 3 4 芦6 + 1 3 4 p 7 + 1 8 肛8 + 卢9 1 ( d ：l ，p ) 1 ( _ d 墨，p ) = l ( d 主4 ，p ) 2 0 + 3 4 9 p + 1 8 6 9 p 2 + 4 6 8 6 3 + 6 5 1 2 灿4 + 5 4 4 7 5 十2 8 4 9 6 + 9 3 7 p 7 + 1 8 8 p 8 + 2 1 p 9 + p l o 2 + 1 1 2 p + 1 0 9 0 p 2 + 4 2 5 7 p 3 + 8 6 4 6 p 4 + 1 0 2 9 6 芦5 + 7 6 4 4 p 6 + 3 6 3 5 p 7 + 1 1 0 6 p 8 + 2 0 8 肛9 + 2 2 p l o + “1 1 2 + 1 3 4 肛+ 1 5 5 1 p 2 + 7 2 1 6 p 3 + 1 7 5 8 9 芦4 + 2 5 4 5 4 p 5 + 2 3 3 8 7 肛6 + 1 4 1 2 8 + 5 6 7 8 p 8 + 1 5 0 2 p 9 + 2 5 l 芦1 0 + 2 4 肛“+ p 1 2 堑三重要差里盟堡堕垒堑壅 2 7 l ( d ；5 ，p ) = 2 4 + 5 9 5 p + 4 5 1 0 p 2 + 1 6 1 5 9 肛3 + 3 2 7 4 7 卢4 + 4 1 1 9 7 肛5 + 3 3 8 8 0 灿6 + 1 8 7 0 0 弘7 + 6 9 7 2 p 8 + 1 7 3 l p 9 + 2 7 4 弘1 0 + 2 5 卢1 1 + 卢1 2 1 ( d 品，卢) = 2 + 2 1 2 肛+ 3 8 3 6 芦2 + 2 7 9 3 弛3 + 1 0 7 9 0 0 卢4 + 2 5 2 8 2 4 且5 + 3 8 8 0 7 6 肛6 + 4 0 8 9 1 8 弘7 + 3 0 4 2 6 6 肛8 + 1 6 2 2 6 0 p 9 + 6 2 2 1 6 p l o + 1 6 9 9 7 “1 1 + 3 2 2 6 p 1 2 + 4 0 4 p 1 3 + 3 0 p 1 4 + 弘1 5 设4 表示以下所有数字( 图的顶点个数) 的集合，可以验证：对任意札4 ， 1 ( d ：，p ) 是不可约的 691 01 31 6 1 8 2 l2 22 4 2 53 0 3 3 3 43 74 0 4 2 4 5 4 6 4 84 95 45 7 5 8 6 1 6 4 6 6 6 9 7 0 7 27 37 88 l8 2 8 58 8 9 09 3 9 49 6 9 71 0 21 0 51 0 61 0 9 对于图霹，有 l ( 碌，p ) = 4 + 3 2 卢+ 6 0 p 2 + 4 1 p 3 + l l p 4 + “5 l ( 碟，p ) = 4 + 4 8 p + 1 2 8 肛2 + 1 3 3 肛3 + 6 2 “4 十1 3 p 5 十“6 l ( f 盎，p ) = 4 + 9 2 p + 4 2 8 p 2 + 8 1 7 肛3 十7 8 3 肛4 + 4 0 7 卢5 + 1 1 6 芦6 + 1 7 肛7 + “8 九1 ( 聪，肛) = 4 + 1 2 0 芦+ 7 0 4 p 2 + 1 7 0 9 卢3 + 2 1 3 7 p 4 + 1 5 l o p 5 + 6 2 4 芦6 + 1 4 9 肛7 + 1 9 p 8 + p 9 l ( 磴，肛) = 4 + 2 2 8 p + 2 3 8 4 肛2 + 1 0 3 4 5 p 3 + 2 3 9 3 弘4 + 3 3 1 9 8 “5 + 2 9 3 6 8 p 6 + 1 7 1 1 l p 7 + 6 6 3 3 p 8 + 1 6 9 l 卢。+ 2 7 2 p l o + 2 5 “1 1 + 肛1 2 箜三童堕耋堕堂堡堕堑堕壅 2 8 1 ( 聪，p ) ，( f 品，p ) 4 + 3 2 0 肛+ 4 5 8 4 p 2 + 2 7 1 4 9 肛3 十8 6 4 3 8 p 4 + 1 6 7 7 3 9 “5 + 2 1 2 8 2 3 卢6 + 1 8 3 9 8 7 p 7 + 1 1 0 8 9 2 p 8 + 4 7 0 0 4 p 9 + 1 3 9 4 0 p l o 十2 8 2 9 肛1 1 十3 7 4 卢1 2 + 2 9 p 1 3 + p 1 4 4 + 3 7 2 肛+ 6 1 4 0 p 1 7 + 4 1 8 0 9 p 3 + 1 5 3 3 7 4 p 4 十3 4 4 7 7 3 p 5 + 5 1 0 8 6 1 p 6 + 5 2 1 5 1 0 p 7 + 3 7 6 6 5 2 p 8 + 1 9 5 1 1 2 p 。+ 7 2 6 7 2 卢1 0 + 1 9 2 7 7 肛1 1 + 3 5 5 0 芦1 2 + 4 3 l 卢1 3 + 3 1 p 1 4 + 卢1 5 设8 为以下数字的集合，则对任意n 日， ，( 瑶，p ) 是不可约的 1 0 1 2 1 61 82 42 83 03 43 64 0 4 24 64 85 25 4 5 86 06 46 67 0 7 27 67 88 28 48 89 09 49 61 0 0 1 0 21 0 61 0 81 1 2 1 1 4 1 1 81 2 01 2 41 2 6 1 3 0 由集合4 和口中的数字，我们给出两个关于这两类图的不可约性的猜想： 猜想3 3 1 若 1 ( d ：，p ) 是不可约的，则 1 ( d 鲁2 4 ，p ) 也是不可约的，且基于 以下这些数字序列： 691 01 31 61 82 12 2 2 4 2 5 3 0 可以列举出所有不可约的 1 ( d i ，p ) 猜想3 3 2 若 l ( 碟，p ) 是不可约的，则 l ( 砖1 8 ，p ) 也是不可约的 问题；讨论了d ：和碍的不可约性，我们希望得到在这些不可约图中哪些是 色唯一的 第四章特殊图类的全嵌人分布多项式 4 1预备知识 对于图g ，图g 在顶点”处的边的循环序，称为图g 在”点处的旋给 图g 的每一个节点规定一个旋，则这些旋一起组成图g 的一个纯旋系统 若图g 的n 个顶点u 1 ， 2 ， 。处的度数分别为d 1 ，d 2 ，一，d 。，图g 的 纯旋系统的总个数记为，。，则 n b = ( d 。一1 ) 1 4 = l 设图g = v e ) ，图g 的个广义旋系统p = ( ”，e - ) 定义为由图g 的一个纯 旋系统”和边集e 的子集且组成，其中日中的边为扭曲的，或者称为是1 一 型的；e 一易中的边被称为是不扭曲的，或者是0 一型的 显然的，在图的一个广义旋系统中若e - = 0 则对应于一个纯旋系统这 里，用冗g 和p g 分别表示图g 的广义旋系统和纯旋系统的集合 假设固定图g 的一棵生成树丁，则t 一旋系统的集合妒苫对应于图g 的 l 妒5 1 个嵌入若在这f 礤1 个嵌入中，有咖个平面嵌入，o 。个亏格为i 的嵌入 和6 ，个叉冒为j 的嵌入，i ，j = l ，2 ，则图g 与树t 有以下关系式： 塔( z ，) = 印+ o ；+ 矿 巧( z ，g ) 叫做图g 的t 树分布多项式明显的，晤( z ，) 的可定向部分，蓦吼z 2 与文献 3 8 】中j o n a t h a nl g r o s 8 和m e r r i c kl f u r s t 介绍的图的亏格分布一 致为方便起见，本章中将啦叫做图g 的准亏格分布多项式，且记作 = 1 玷( z ) 图g 的树分布曙( z ，f ) 与生成树t 的选择无关，见 3 3 第四章特殊图类的垒嵌入分布 图g 的全嵌入分布多项式坫( z ，g ) 即定义为 七( z ，) = 聒( z ，g ) 设在一个有n ( n22 ) 个顶点的圈的每个顶点增添m ( m 1 ) 个环，将所 得到的图叫做标准类圈图，记作焉，且记它的全嵌入分布为腧( 。，) 本章中，尝试得到群和铱的全嵌入分布，即当n = r ，m = 1 和m = 2 时的情形图一4 和图一5 中分给出了靠和鳔的图形 图一4 图一5 4 2覆盖矩阵和它们的秩分布多项式 设螈为定义在g f ( 2 ) 上的一个r r 有如下形式的对称矩阵 4 = 露( 。o ，z l ，- ，z ，一l ，掣l ，可，一1 ) z 0掣1 1z 1 珈一2 0 玑一1 0 孙一2 弘一1 o0 z r - 2 0 0 坼一l 3 0 笪堕差鳖丛里差盟垒垦坌查 3 l 所有变量z o ，z h 一，。，f 1 ，* 一1 皆定义在g f ( 2 ) 上且设协为所有 4 的集合定义集合协的秩分布多项式为d ，( ：) = d ，( 阱，z ) = 釜oq 。4 ，即： 对每个秩z ，在协中恰有q 个矩阵的秩为t 另外一个定义在g f ( 2 ) 上的r r 的对称矩阵耳，形式如下： s r = 肆( z o ，z 】，r ，z ，一l ，0 ，- - ，o ) 00 00 00 - o ，一2 0 o0 - 0 z ，一1 设耳( z ) 表示鼻的集合的秩分布多项式，则 引理4 2 1 声纠 耳( z ) = ( 1 + z ) 引理4 2 。2 归彰 d ，( 。) = d ，( 妒，z ) = 2 2 2 ( 2 z + 2 ) 一1 十( 1 + 。2 2 2 ) ( 2 = + 1 ) 一1 设 4 中恰有女个变量协满足协= l ，( j = 1 ，r 一1 ) ，记这个矩阵为 带，且记此矩阵集合的秩分布多项式为聊( z ) ，则显然：讲( ：) = d r ( 。) 且有 定理4 2 3 d ：( z ) = ( 1 + z ) r 一一1 _ d 2 + ，0 ) + ；( 1 + ：) 一1 骘一1 ( 。) 瑚，萎，( 。埘，计2 第四章特殊图类的全嵌入分布 其中1 r 一1 ，特别的 ( t ) d ? ( z ) ( 埘) 研- 1 ( = ) 证明 ( 1 ) 显然，当