（计算数学专业论文）一些图的独立多项式的单峰型性质.pdf

摘要 摘要 图的独立集的研究是图论中最原始的问题之一，图论研究中的一些经典问题，如： 棋盘问题( c h e s sb r o a d ) ，图的匹配( m a t c h i n g ) 问题、着色( c o l o r i n g ) 问题，c l i q u e s ( 团) 、支配集( d o m i n a t i n gs e t s ) 等都和独立集密不可分( 例如t 图g 的匹配是其线图 的独立集，图g 的团是其补图的独立集) ；在编码学、计算机科学理论和网络理论等方 面也都会涉及到图的独立集的同题因此图的独立集的研究既有重要的理论意义又有着 广泛的实际应用，也正因为如此。对图的独立集的研究一直非常活跃e r d s s 和m o s e r 等一批学者对此做了深入的研究 本文主要来讨论一些图的独立多项式的单峰型性质 第一章主要介绍了图的基本概念以及单峰型性质 第二章主要证明了l e v i t 和m a n d r e s c u 提出的猜想( 以后称其为l m 猜想) ；蜈蚣 树( c e n t i p e d e s ) 的独立多项式只有实零点 第三章在l e v i t 和m a n d r e s c u 所研究的蜈蚣树的基础上，进一步研究毛毛虫树( c a t e r - p i l l a r s ) 、v e r t e b r a t e 树的独立多项式的单峰型性质 第四章主要讨论一类图的独立多项式的指标 关键词；单峰的，对数凹的，独立集，独立多项式，指标，蜈蚣树，毛毛虫树 大连理工大学硕士学位论文 t h e u n i m o d a l i t y o f i n d e p e n d e n c ep o l y n o m i a l so f s o m e g r a p h s a b s t r a c t t h er e s e a r c ho f i n d e p e n d e n ts e t so f g r a p hi so n eo f t h em o s t o r i g i n a lp r o b l e m s i ng r a p h t h e o r y s o m ec l a s s i c a lp r o b l e m so fg r a p ht h e o r ya r ea l li n d i s c e r p t i b l ew i t hi n d e p e n d e n t s e t s ( f o re x a m p l e ，am a t c h i n go fg r a p hi sai n d e p e n d e n ts e t o fi t sl i n eg r a p h ，a n da c l i q u eo fg r a p hi sai n d e p e n d e n ts e to fi t sc o m p l e m e n tg r a p h ) i n d e p e n d e n ts e t so fg r a p h a p p e a ri nt h ef i e l do fc o d i n g ，c o m p u t e rs c i e n c et h e o r ya n dn e t w o r kt h e o r y t h u s ，t h e r e s e a r c ho fi n d e p e n d e n ts e t so fg r a p hi sh i g h l ya c t i v e s o m es c h o l a r s ，e r d s sa n dm o s e r ， h a de m b e d d e dr e s e a r c h e d 。 t h et h e s i sm a i n l yd i s c u s st h eu n i m o d a l i t yo fi n d e p e n d e n c ep o l y n o m i a l so fs o m e g r a p h s i ti sd i v i d e df o u rc h a p t e r s t h ef i r s to fw h i c hi n t r o d u c e sb a s i cc o n c e p t so fg r a p ha n du n i m o d a l i t y t h es e c o n dc h a p t e rm a i n l yv e r i f i e st h el m c o n j e c t u r e ：t h ei n d e p e n d e n c ep o l y n o m i - a l so fc e n t i p e d e sh a v eo n l yr e a lz e r o s t h et h i r dc h a p t e rf u r t h e ri n v e s t i g a t e st h eu n i m o d a l i t yo f i n d e p e n d e n c ep o l y n o m i a l s o fc a t e r p i l l a r sa n dv e r t e b r a t e s t h ef o r t hc h a p t e rm a i n l yd i s c u s s e st h em o d eo fi n d e p e n d e n c ep o l y n o m i a l so fac l a s s o f g r a p h s k e yw o r d s ：u n i m o d a l ；l o g - c o n c a v e ；i n d e p e n d e n ts e t s ；i n d e p e n d e n c ep o l y n o m i a l s ； m o d e ；c e n t i p e d e s ；c a t e r p i l l a r s i i 大连理工大学硕士学位论文 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。 作者签名：粒! 謇日期：甚堕：；：! 前言 前言 图的独立集的研究是图论中最原始的问题之一，图论研究中的一些经典问题，如。 棋盘问题( c h e s sb r o a d ) ，图的匹配( m a t c h i n g ) 问题、着色( c o l o r i n g ) 问题、团 ( c l i q u e s ) 、支配集( d o m i n a t i n gs e t s ) 等都和独立集密不可分( 例如；图g 的匹配是 其线图的独立集，图g 的团是其补图的独立集) ；在编码学、计算机科学理论和网络理 论等方面也都会涉及到图的独立集的问题因此图的独立集的研究既有重要的理论意义 又有着广泛的实际应用，也正因为如此，对图的独立集的研究一直非常活跃 e r d b s 和m o s e r ( 1 9 7 0 ) 最先考虑了具有n 个顶点的图的极大独立集( m a x i m a l i n d e p e n d e n ts e t s ) 的数目和刻画( 实际上，他们考虑的是对偶的问题，也就是极大团的 数目和刻画) ，m o o n 和m o s e r ( 1 9 6 5 ) 完全解决了这个问题1 9 8 6 年w i l f 对连通图提 出了同样的问题，他得到了树的极大独立集的数目，s a g a n ( 1 9 8 8 ) 进一步描述丁树的 极大独立集，g r i g g s 等( 1 9 8 8 ) 进一步得到了般连通图的极大独立集的数目和刻画 本文将考虑图中各种基数的独立集的数目( 称为独立集数列) 及其分布，一个很自 然的研究途径是通过独立集数列的发生函数，这也是组合数学中最重要的计数手段，进 而我们的研究对象是图的独立多项式( g u t m a n 和h a x a r y , 1 9 8 3 ) 传统的对图的独立集 的研究只是考虑给定图的极大独立集的基数( 即图的极大独立数) 及数目，对应到良覆盖 图( w e l l - c o v e r e dg r a p h s ，r a v i n d r a ，1 9 7 7 ) 是其独立多项式的阶数及首项系数，相对 来说是局部的研究，而我们将是考虑整个的独立集数列，可以想象这更具有挑战性在本 文中，我们将研究良覆盖图的独立多项式的如下一些性质( 将其统称为单峰型性质) 。 是否良覆盖图的独立多项式的所有零点都是实数，其系数( 也就是独立集数列) 是否是 单峰的甚至对数凹的等等由著名的n e w t o n 不等式可知，如果一个多项式( 其系数是 非负的) 的所有零点都是实数，那么该多项式的系数是单峰的我们熟知图的匹配多项 式的所有零点都是实数( h e i l m a n na n dl i e b ，1 9 7 2 ) ，以及图的匹配多项式是其线圈的 独立多项式，然而一般来说良覆盖图的独立多项式并没有这么好的性质 b r o w n ，d i l c h e r 和n o w a k o w e k i ( 2 0 0 0 ) 给出了良覆盖图的独立多项式零点的界 ( b r o w n 和n o w a k o w s k i 也描述了一般图没有这样的界存在，2 0 0 1 ) ，并猜想良覆盖图 的独立多项式是单峰的( 即独立集数列是单峰的) ，尽管最近m i c h a e l 和t r a v e s ( 2 0 0 3 ) ， l e v i t 和m a n d r e s c u ( 2 0 0 3 ) 否定了这个猜想，然而相关的r o l l e r - c o a s t e r 猜想仍然没 有解决关于优覆盖图( v e r yw e l l - c o v e r e dg r a p h s ) 的独立多项式是否是单峰的问题也 没有解决，只是l e v i t 和m a n d r e s c u ( 2 0 0 3 7 ) 给出了一类优覆盖图的独立多项式是单 峰的 大连理工大学硬士学位论文 1 9 8 7 年，a l a v i ，m a l d e ，s c h w e n k 和e r d b s 猜想树的独立多项式是单峰的，然而目前 还不清楚良覆盖树的独立多项式是否具有草峰性，所以此猜想还尚未解决h a m i d o u n e ( 1 9 9 0 ) 证明了每个c l a w - f r e e 图的独立多项式是单峰的，进一步猜想c l a w - f r e e 图的独 立多项式的零点都是实数( 此猜想也没有得到解决) ；l e v i t 和m a n d r e s c u ( 2 0 0 2 1 1 及 2 0 0 3 5 ) 证明了良覆盖树可由一些良覆盖s p i d e r 树之并得到以及良覆盖s p i d e r 树的独 立多项式是单峰的，进而也证明了蜈蚣树( c e n t i p e d e s ) 的独立多项式是单峰的，之后， 他们猜想蜈蚣树( c e n t i p e d e s ) 的独立多项式的零点都是实数 本文对此猜想进行了证明，并在螟蚣树的基础上讨论毛毛虫树( c a t e r p i l l a r s ) 、v e r - t e b r a t e 树的独立多项式的单蜂型性质及一类图的独立多项式的指标 2 第一章基本概念 第一章基本概念 1 1图的基本概念和性质 现实世界的许多事例用图形来描写可能是方便的，这种图形是由一个点集以及这个 点集中的某些点对的连线构成的例如，点可以表示人，连线表示一对朋友；或者，用点 表示通讯站，而连线表示通讯线路注意：在这类图形中，人们主要感兴趣的是给定两 点是否有一根线连接，而连接的方式则无关紧要这类事例的数学抽象就产生了图的概 念 一个图g 是指一个有序二元组( v ，e ) ，其中y 和e 是不相交集，且e 是y 的 不同元素的无序对所构成的子集，v = v c o ) 是g 的顶点集，e = e ( g ) 是边集， e 中的一条边似，” 是指连接着顶点u 和口的一条边，记作u ” 在一个图g = ( u e ) 中，若t ，u v ，而e = u e ，也记作e = ( u ，口) ，此 时，称u 和 是邻接的，记作ua d j ，否则记作un a d j ；e 和，口均称为是关 联的。“和“均称为是e 的端点若两条不同的边e - 和e o 有一个公共的端点，则称 8 l 和8 2 是邻接的，记作e la d j e 2 ，否则记作8 1n o 矗e 2 与一点t 邻接的所有的点的 集合称为u 的邻域，记作( u ) ，进一步，有m = ( u ) t j u 对于图g = ( k e ) 与g = ( v ，e ) ，若v cv ，ce 则称图g = ( ，e ) 是 图g = ( v e ) 的子图，记作g jcg 如果g 中包含着g 中连接v 。中的任意两顶点 的所有的边，则称g ，是g 的诱导子圉或是由v 。生成的，记作g i g 。我们也可以在 g 中增加或删除一些顶点和边而得到新的图，若wcv ( v ) 则g w = c v w 】是在 g 中删掉w 中的所有顶点和与中的顶点关联的所有的边而得到的g 的子图类似 的。e ce ( g ) 。则g e = ( g ) ，e ( g ) e ) 若w = 如) 且= u 。) 则我们可 以简单地记作g 一 和g 一“u 如果u ，u 是g 中的不相邻的两个顶点，则称g + u v 是在g 中连接u 和”得到的图 设口v ( g ) ，g 中与 关联的边的数目称为 ( 在g 中) 的度，记作d e g g ”或简记 作d e g d e g 口。0 和1 的点分别称为g 的孤立点和端点( 注：条边的端点和一个图 的端点有不同的意义) 记a ( g ) = m a x d e g g ， y ( g ) ) ，与6 ( g ) = m i n d e g g ，u y ( g ) ) ，分别称为g 的最大度与最小度 在个图g 中，若( g ) = 6 ( g ) = r ，则对所有的 v ( a ) 。均有d e g u = r ，这 样的图称为是r 度正则的，并记作d e g g = r p 一1 度正则的图中任何两点均邻接， 3 大连理工大学硕士学位论文 称为完全图，记作0 度正则的图( 顶点数为p ) 中一条边也没有，称为全不连通 圉或空圉，记作 若札o ，u l ，“n v ( g ) ，e l ，e 2 ，e ”e ( e ) 且e i = 牡t 一1 u ， = 1 ，2 ，n ， 则交替序列“0 8 1 “1 8 2 “2 e 。称为一条( 联结t o 和u 。的) 通道，u o 和u 。均称为它 的端点，其中线的数目n 称为它的长度；若u o = u 。，则称这条通道是闭的，否则是 开的；若一条通道中所有的点钍均不同( 从而所有的边均不同) ，称其为一条道路一 条闭道路中除u o = u 。外，其余的点均不同( 从而所有的边均不同) ，称其为一个圈， 长度为n 的道路和圈分别记作r 和g 如果g 的顶点集和边集都有限，则称其为有限图；如果g 既没有圈也没有两条边 连接同一对顶点，则称其为简单图； 4 第一章基本概念 5 1 2 图的独立多项式及相关结论 5 1 2 1 图的独立多项式及其性质 设g = ( v e ) 是简单图，s c y ( g ) ，若s 中任意两个顶点都不是邻接的，则称s 是g 的一个独立集( i n d e p e n d e n ts e t ) ；任取u v ( c ) 一s ，s t 3 “) 不是独立集，则称 s 是g 的一个极大独立集；若g 中已无独立集，使得l | i s l ，则称s 是g 的 个最大独立集，此时，记口( g ) ；l s i ，口( g ) 叫做g 的独立数以后我们用i k ( g ) 表示g 中基数为七的独立集的数目，则称多项式 塑 k ( g ) 一， i o = 1 七= 0 是g 的独立多项式( i n d e p e n d e n c ep o l y n o m i a l ) ( 1 5 1 ) ，记作，( g ；z ) 或g ( 。) 如图1 2 1 所示，两个黑色顶点构成一个极大独立集，也是最大独立集，o ( g ) = 2 ， 其相应的独立多项式是t1 + 6 x + 5 x 2 f i g 1 2 1 注：由独立集的定义可知t ( 1 ) 图g 的每个顶点构成一个独立集 ( 2 ) 极大独立集不是唯一的，它的基数不一定是最大的，但它的元素数日已达到极 限，即不可能再加入其他顶点而不破坏它的独立性 在计算各类图的独立多项式及寻找其递归公式时，下面的结论( 也是独立多项式的 性质) 是非常有用的工具相关结果可参见文献 1 5 l 、【3 】、【1 9 】我们引进一个记号： 设g 1 ，g 2 是两个简单图。g 是g 1 ，g 2 的不相交并( d i s j o i n tu n i o n ) ，其中g 的顶点是v ( a 1 ) 与v ( a 2 ) 的不相交并，边集也是e ( g 1 ) 与e ( g z ) 的不相交并，记作 g = g t g 2 我们知( 3 1 、【1 5 】、【1 9 1 ) ， ，( g 1i ig 2 ；善) = i ( g 1 ；x ) ，( g 2 ；z )( 1 2 1 ) 以及， 5 大连理工大学硕士学位论文 定理1 2 1 圈g = ( 1 i , e ) ，w v ，u 口e 及uc v ，其中u 使得g 【卅是g 的 一个完全子图，则有， ( i ) ，( g ；。) = ( g t i ；z ) + x z ( a n m ；3 7 ) ( 越) ，( g ；z ) = z ( a u ；。) + 。i ( g 一扣】；z ) v e u ( i i i ) ，( g ；z ) = ，( g u v ；x ) 一。2 j - ( g n u 】u 扣】；。) 6 第一章基本概念 1 2 2几个重要的多项式 本节主要介绍一些与独立集及独立多项式有密切联系的概念； 1 团( c l i q u e ) 在简单图g = ( u e ) 中，若s 是y 的子集，使得g s 】是完全 图( 即s 中的任意两点都有边连接) ，则称s 是g 的一个团对于团s 若不存在团， 使得scs ，则称团s 是g 的个最大团将m a _ x i s i ，s 是g 中的最大团1 称为g 的 团数，记作c t ( g ) 团与独立集的关系：s 是g 的团当且仅当s 是g 的补图的独立集( 这n a 概念是 互补的) 例如：图1 2 2 1 中， 1 ，3 ，4 ，6 ) 、 1 ，2 ，4 、 4 ，5 ) ， 4 ，7 ) 均是最大团，且d ( g ) = 4 由 1 ，3 ，4 ，6 生成的完全子图在图中用粗线表示，在补图中对应的最大独立集的顶点用 圈表示( 如图1 2 2 2 ) 12 f i g 1 2 2 1 36 2 5 4 7 f i g 1 2 2 2 3 2 匹配及匹配多项式在简单图g = m e ) 中，设m 是e 的一个子集，它的 元素是g 中的边，并且这些边中的任意两条在g 中均不相邻( 即任意两条边都没有公 共的端点) ，则称m 为g 的个匹配若g 没有另外的匹配m ，使得i m | i m i ，则 称m 为g 的一个最大匹配用p ( a ，七) 表示g 中基数为k 的匹配集的数目，则多项式 郭 ( 一1 ) p ( g ，七) 矿埘，p ( c ，o ) = 1 ， = o 称为图g 的匹配多项式 众所周知，任意图的匹配多项式都只有实零点 4 】从而，由牛顿不等式( 将在1 3 中给出) 可知，任意正匹配多项式的系数形成一个对数凹序列为了我们的目的，我们 将只考虑正匹配多项式基p ( a ，) 。n m ，p ( g ，o ) ：1 k = o 图的独立集与图的匹配相类似，都是从独立性的概念来定义的，前者是图的不相邻 7 大连理工大学硕士学位论文 的顶点的集合，后者则是图的不相邻的边的集合，尽管如此，独立集却没有类似匹配理 论的独立集理论而且，目前还没有一个求图的最大独立集的有效算法 3 线图( 1 i n eg r a p h )非空图g 的线图l ( g ) 是以e ( g ) 为顶点集的图，并且若 q ，e j e ( g ) ，则( e i ，勺) f 陋( g ) ) 甘在g 中，岛的端点是q 的端点 例如。图1 2 2 4 中连接黑顶点所构成的图即是图1 2 2 3 的线图 f i g 1 2 2 3 髟 p i g 1 2 2 4 匹配、团、独立集的关系； ( 1 ) g 的匹配集与g 的线图，的独立集对应，而独立集又与j r 的补图7 的团对应，因 此，可以利用找团的算法找到所有最大的匹配集【l o 】 ( 2 ) 任意图g 的正匹配多项式等价于g 的线图l ( g ) 的独立多项式【1 5 ，p r o p o s i t i o n1 】 4 覆盖集( c o v e r i n gs e t )在简单图g = ( v e ) 中s c v ( a ) ，且g 的每一 边至少有一个端点属于s 。则称s 是图g 的一个覆盖；若s 是一个覆盖，w s ， s 一 ”) 不是覆盖，则称s 为一个极小覆盖；若s 是个覆盖，但已无覆盖，使得 拶l l s l ，则称s 为g 的一个最小覆盖；用c ( a ) 表示g 中最小覆盖的顶点数，且 c ( a ) 称为g 的覆盖数如图1 2 2 5 中的黑色顶点是一个极小覆盖，同时也是最小覆 盖，c ( g ) = 4 覆盖集与独立集的关系；s v ， f i g 1 2 2 5 8 第一章基本概念 ( 1 ) s 是一个独立集，当且仅当y s 是覆盖集【4 0 ( 2 ) s 是极小覆盖集，当且仅当y s 是极大独立集 5 支配集( d o m i n a t i n gs e t ) 简单图g = 似e ) ，s 是y 的一个子集，如果g 中的任意一个顶点或者属于s 或者与s 中的至少一个顶点领接，则称s 是g 的一个支 配集若g 中没有另外的支配集s 7 ，使得l s i i s l ，则称s 是g 的个最小支配集 若支配集s 的任意真子集均不是g 的支配集，则称s 是g 的一个极小支配集g 的支 配数是指g 中最小支配集的顶点数，记作d ( g ) 如图1 2 2 6 所示， 1 ，5 ) 、 2 ，3 ，曲、 2 ，5 ，6 ) 、 4 ) 均为极小支配集，且d ( g ) = 1 图的支配集和独立集有着密切的联系在任意的图中，一个独立集是极大的当且仅 当它是一个支配集由此可知。图的独立数o ( g ) 支配数d ( g ) ， 4 2 1 注t 极大独立集必定是支配集，但是极小支配集却不一定是独立集如图1 2 2 7 有极 小支配集 3 ，4 ) ，但其不是独立的 6 12 54 f i g 1 2 2 6f i g 1 2 2 7 6 点的着色( c o l o r i n g )一个标定图g = ( ke ) 的个扎一着色是由g 的点集 v ( g ) 到色集最。= 1 ，2 ，n ) 上的一个映射n ，使对任意u ，u v ( g ) ，uo 匆u ， 均有o ( u ) n ( ”) ，这里又的元素通常称为颜色若图g 存在一个n 一着色，则称g 为n 一可着色的，使g 存在一个n 一着色的最小的n 称为g 的色数，记作x ( g ) 若 x ( g ) = n ，g 祢为n 一色的 例如：图1 2 2 ，8 中的色数分别为4 ，3 。 9 大连理工大学硬士学位论文 ygr b y f i g 1 2 2 8 对图的点进行着色，就是将图的顶点划分为若干独立集，使独立集的数目最少，因 为在一个独立集内的顶点是彼此不相邻的，所以独立集内的所有顶点可以着同一颜色 注：对于图的着色的研究来源于著名的四色问题。 本小节所提到的与独立集相关的匹配、团、支配集等的算法，读者可参见文献【1 0 】 1 0 第一章基本概念 1 3单峰型性质 对于非负序列a o ，o l ，( 本文不考虑无限序列) ，如果存在非负数m 使得蛳s sa l a m2a m + 1 a 。，则称此序列是单峰的( u n i m o d a l ) 。其中m 称为 这个序列的指标；如果对于所有的1s is 扎一1 ，均有不等式o a i - i 啦+ 。成立，则 称此序列是对数凹的( 1 0 9 - c o n c a v e ) ；如果不存在实数0 冬f j 0 ，因此，对于n 2 ，一1 是厶( z ) 的最大零点，所以，由式( 2 2 2 ) 可知矗一( 。) 交错厶( 。) 证毕 l e v i t 和m a n d r e s c u 【2 4 1 不仅利用蜈蚣树的性质证明了j ( ；z ) 是单峰的，而且还 利用递归关系，( ；z ) = ( 1 + 茹) 【j ( 巩一- ；z ) + 。，( i 一2 ；茁) 】，n 2 ，这里，( w i ；z ) = 1 ， 1 7 盔篓堡三查兰堡主堂垡堡塞 ，( i n ；。) = 1 + 2 x ，推出了如下的一些式子 x ( w 2 ；z ) ，( w j ；o ) ，( m ；z ) ( 睨；z ) ( - ；z ) ( ；z ) ，( w ；z ) j r ( i ；z ) j ( n o ；z ) ( i h l ；x ) 1 + 4 + 3 0 2 1 + 6 。+ l _ _ o z 2 + 5 x 3 1 + 8 x + 2 1 x 2 + 2 2 x 3 + 8 2 4 1 + l o x + 3 6 x 2 + 跏3 + 4 5 x 4 + 1 3 x 5 + 。6 1 十1 2 x + 5 5 x 2 + 1 2 4 x 3 + 1 4 _ _ 7 x 4 + 8 8 x 5 + 2 1 x 6 1 + 1 4 x + 7 8 x 2 + 2 2 5 x 3 + 3 6 _ 6 6 x 4 + 3 3 9 x 5 + 1 6 7 x 6 + 3 4 。7 1 + 1 6 x + 1 0 5 x 2 + 3 7 0 x 3 + 7 7 0 x 4 + 9 7 _ _ f i x 5 + 7 4 1 x 6 + 3 1 0 茹7 + 5 5 茁8 1 + 1 8 x + 1 3 6 x 2 + 5 6 7 x 3 + 1 4 4 3 x 4 + 2 3 3 7 x 5 2 4 2 2 x 6 + 1 5 5 7 x 7 + 5 6 6 x 8j 8 9 x 9 1 + 2 0 x + 1 7 1 x 2 + 8 3 4 x 3 + 2 4 8 5 x 4 + 4 9 2 0 x 5 + 6 5 0 5 x 6 + 5 6 9 6 。7 + 3 1 7 4 x 8 + 1 0 2 0 x 9 + 1 4 4 x 1 0 1 + 2 2 x + 2 1 0 x 2 + 1 1 4 9 x 3 + 4 0 1 2 x 4 + 9 4 1 5 x 5 + 1 5 2 0 5 2 6 + 1 6 9 6 0 x v + 1 2 8 4 9 x 8 + 6 3 1 7 x 9 + 1 8 1 9 x l o + 2 3 3 。1 1 他们通过对这些式子的观察提出了如下的猜想 猜想2 2 1 1 2 4 】多项式j ( i ；z ) 的指标是 坳胁一塑掣j + 2 l 字j 咄 对于此猜想，我们可以利用如下简单的m a p l e 程序进行检验 j ：= p r o c ( n ：n o n n e g i n t ) l o c a lx ，j ： j ( o ) ：= 1 ： j ( 1 ) ：= 1 十2 术x ： f o r j f r o m2 t ond o j 0 ) ：= ( 1 + x ) + ( j 0 1 ) + x 木j 0 2 ) ) ： o d ： e n d ： e x p i r e d ( j ( 1 3 ) ) ： s o r t ( ) ； 第二章对l e v i t 和m a n d r e s c u 猜想的证明 6 1 0 x 1 3 + 5 6 4 5 x 1 2 + 2 3 6 8 2 x l l + 5 9 5 3 2 x l o + 9 9 8 5 5 x 9 + 1 1 7 7 6 5 2 8 十1 0 0 2 3 5 。7 + 6 2 1 8 8 x 6 + 2 8 0 5 3 x 5 + 9 0 6 5 x 4 + 2 0 3 5 x 3 + 3 0 0 2 2 + 2 6 z + 1 尽管这个问题仍然是公开的，但可以由定理2 1 3 和牛顿不等式知蜈蚣树的独立多 项式最多只有两个指标 另外，设g 是由蜈蚣树组成的森林，则g 的独立多项式，( g ；岔) 是这些螟蚣树的独 立多项式的乘积，由定理2 1 3 可知，( g ；z ) 也只有实零点，因此，( g ；。) 是单峰的 值得注意的是，这个结论不能由l e v i t m a n d r e s c u 的关于蜈蚣树的独立多项式是单峰 的这个结论而得到 1 9 大连理工大学硕士学位论文 第三章道路与毛毛虫树的独立多项式的单峰型性质 3 1 道路与毛毛虫树的独立多项式的单峰型性质 道路r ( 如图3 1 1 ) 的概念我们已在第一章中介绍过了，现在我们给出毛毛虫树 ( c a t e r p i l l a r s ) 的定义 定义3 1 1 毛毛虫树日n = ( v 日) ，其中顶点集v = a u ( u 名1 ) b i ，这里a = n 1 ，a n ) ，b i = 6 f ，6 9 ) o = 1 ，2 ，n ) ，边集e = 啦n 件1 ：1 i n 一1 u 仉蜉：1s is n ，j = 1 ，2 ) ，如图3 1 2 - - - - o l 0 2 a 30 n - 1 n n f i g 3 1 1r a l 啦 口n 一1 口n 照。翮 掣6 砰妒毋。彦- 1 垮 f i g 3 1 2 风 从图3 1 2 我们可以推导出如下的定理： 定理3 1 1 毛毛虫树的独立多项式珥。( z ) 满足如下的递归关系： 。芒k ( z ) = ( 1 + 盘) 2 【芒k l ( z ) + 茁日一2 ( 。) 】，( 3 1 1 ) 其中( z ) = 1 ，h 1 ( 。) = z + ( 1 + 。) 2 证明t 由图的独立多项式的定义易知编( z ) = 1 ，日1 ( z ) = z + ( 1 + z ) 2 下面令n 2 ，显然，巩一) = 玩一面和风一n a 。】风一2 匿，这里 一k 2 是顶点数为2 的空图，且j ( j 石，。) = ( 1 + z ) 2 因此，由式( 1 2 1 ) 及定理1 2 1 ( i ) 可 得： 第三章道路与毛毛虫树的独立多项式的单峰型性质 j ( h n ，z ) = j ( k 一 n 。) ，嚣) + 。j ( 妇j n i a 。】，茹) = j ( 玩一，h 面，z ) 4 - z j ( 玩一2 面，z ) = ( 1 + 茹) 2 ( e k 一1 ，z ) + 譬( 1 - i - 。) 2 j ( e k 一2 ，$ ) = ( 1 + z ) 2 【j _ ( 。e k 一1 ，z ) + 丑j ( 日二一2 ，z ) 即； n ( x ) = ( 1 + 。) 2 【 k l ( z ) + 矗一z ( 。) 】， 证毕 注： 由式( 3 1 1 ) 及归纳法可得d e g 珥。( o ) = 2 n 事实上，从图3 1 2 观察可得口( 王k ) = 2 竹，因此，我们也可由定义直接得到d e g 日。( z ) = 2 n 显然。道路、毛毛虫树与蜈蚣树在结构上很相似，既然蜈蚣树的独立多项式不仅是单 峰的而且所有的零点都是实的，那么对于道路和毛毛虫树是否又有同样的性质呢? 结论 是肯定的我们已经知道道路的独立多项式是单峰的，参看文献1 1 8 ，p r o p o s i t i o n2 5 j ， 因此，我们只需考虑毛毛虫树的情况 定理3 1 2 毛毛虫树的独立多项式是对称单峰的 为了证明定理3 1 2 ，我们需要如下的引理： 引理3 1 1 1 2 p ( x ) 和g ( z ) 是两个多项式，它们的系数是非负的、对称的、单峰的，则 p ( x ) g ( z ) 的系数也是j # 负的、对称的、单峰的 定理3 1 2 的证明：利用归纳法证明由定理3 1 1 可知上k ( z ) 满足t 日k ( z ) = = ( 1 + 茁) 2 f 。e k l ( 。) + 。日k 一2 ( z ) 其中丑j ( z ) = 1 ，h 1 妇) = z + ( 1 + 茹) 2 ， 当n = 0 ，1 时，王b ( 茁) = 1 ，h 1 ( z ) = z + ( 1 + z ) 2 = 1 + 3 x + 2 ，显然结论是正确 的 假设对于nsk 一1 时，结论也是正确的下面我们考虑n = 七的情况 2 k - 22 - - 4 令h l ( x ) = n ，t l k 一2 ( 。) = b i x 则由归纳假设可知，巩一l ( x ) 和 上k 一2 ( z ) 均是对称的、单峰的t a o2a 2 k 一2sa l 。a 2 k 一3s s ( 2 k 一2 2 a k a k 一1 以及 b o = 6 2 一4 b l = b 2 k 一5s 冬b k 一3 = b k 一1s6 一2 2 1 大连理工大学硕士学位论文 则多项式 丑k 1 ( 。) + z 丑k 一2 ( z ) = a o + 扛2 k - 13 ( 口+ b i 一1 ) + n 2 k 一2 护七一2 是对称单峰的众所周知。多项式( 1 + z ) 2 是对称单峰的，因此，由引理3 1 1 可知， 吼( z ) = ( 1 + $ ) 2 h k t ( z ) + 。风一2 ( 。) 是对称的、单峰的证毕 定理3 1 3 道路的独立多项式只有实零点 证明z与定理3 1 1 的证明方法类似，我们也可以得到r ( z ) 满足如下的关系式； r ( 。) = p 竹一t ( x ) + 正r 一2 ( 省) ，( 3 1 2 ) 这里蜀( 。) = 1 ，p 1 ( z ) = z 十1 ，且由归纳法可知d e g r ( 。) = 訇 令厶( z ) = 。嘲r ( ) 是r ( $ ) 的反序多项式，由式( 3 1 2 ) 可知序列 厶( z ) ) 满足 如下的关系： 当n 是偶数时厶( z ) = 厶一l ( x ) + 厶一2 ( 茹)( 3 1 3 ) 当n 是奇数时。厶( 卫) = z 厶一1 ( z ) + l 一2 ( z )( 3 1 4 ) 其中而( z ) = 1 ，1 1 ( x ) = z + 1 显然，厶( 。) 是次数为f 1 的首1 多项式，因此， r ( 茁) 只有实零点当且仅当厶( 舅) 只有实零点下面对n 用归纳法证明厶( o ) 只有实零 点当ls 佗s1 0 时，由m a p l e 程序可得厶仁) 只有实零点( 见表3 1 1 ) 。而且我们可 以观察到厶一t ( 茹) 交错厶( z ) 表3 1 1 n = 1 2 1 0 时，厶( z ) 的所有实零点 假设当sn 一1 时结论也成立，然后考虑n 的情况下面分两种情况进行讨论： 第三章道路与毛毛虫树的独立多项式的单峰型性质 情况1 ，当n 是偶数时，即n = 2 k ，k = 1 ，2 ，则由式( 3 1 3 ) 可得 1 2 k ( x ) = 岛k 一1 ( x ) + 如女一2 ( z ) ( 3 1 5 ) 其中矗( 。) = 1 ，i ( x ) = z + 1 由归纳假设可得，厶一2 ( z ) 与1 2 k l ( 茹) 都只有实零 点，且一z ( 。) 交错一。( 。) ，那么由引理2 2 1 可得如一，( 。) + 如女一2 ( 面) 只有实零点， 因此，由式( 3 1 5 ) 知，1 2 ( x ) 也只有实零点再由引理2 2 1 知，1 2 k z ( z ) 的实零点 8 ls 口2s o k 与岛女一l ( 妫+ 1 2 f , 一2 ( 。) 的实零点岛岛s s 铱满足； _ ；8 lsa l s 岛s8 2 s 卢k 曼q k( 3 1 6 ) 所以由式( 3 1 6 ) 可知k 一( z ) 交错1 2 k ( z ) 情况2 ，当n 是奇数时，即n = 2 k + 1 ，k = 1 ，2 ，贝由式( 3 1 4 ) 可得 1 2 k + l ( z ) = z 1 2 k ( x ) + 如k i ( x ) ( 3 1 7 ) 其中岛( 。) = l ，i i ( x ) = z + 1 由归纳假设可得，1 2 女( x ) 与1 2 k 一1 ( 。) 都只有实零 点，那么z ( z ) 也只有实零点，且1 2 k l ( z ) 交错。1 2 k ( x ) 因此，由引理2 2 1 可 得。( z ) + 1 2 k 一1 ( 。) 只有实零点，即由式( 3 1 7 ) 有厶女+ l ( z ) 也只有实零点荐由引理 2 2 1 知，z 厶女( z ) 的实零点0 1 0 2 s ( 2 k 0 与z - 厶女0 ) + 如女一l ( x ) 的实零点 反曼艮s 。s 凤筘+ 1 满足t 卢lso l 芦2 锄s 凤茎凤+ 1 0( 3 1 8 ) 所以由式( 3 1 8 ) 可知z - ( z ) 交错1 2 k + l ( z ) 由上述两种情况可知结论是成立的 定理3 1 4 毛毛虫树的独立多项式只有实零点 证明t利用式( 3 1 1 ) 以及归纳法，易证明三k ( 。) 是首1 多项式， e k ( z ) = ( 1 + $ ) 2 l 等f h ( z ) ， 这里，当n 是偶数时，k ( 。) = h 。一1 ( z ) + x h 。一2 ( 。) ， 当n 是奇数时，k ( $ ) = ( 1 + z ) 2 h 。1 扛) + z k 一2 ( 茹) ， 以及 o ( z ) = 1 ， 1 ( ) = 1 + 3 x + z 2 证毕 而且，对于n 2 ( 3 1 9 ) ( 3 1 1 0 ) 显然， n ( 。) 是度为2 n 一2 【2 j 的首1 多项式，且点k ( z ) 只有实零点当且仅当k ( z ) 只有实零点因此。为了证明此定理，我们只需对n 利用归纳法证明k ( z ) 只有实零点 大连理工大学硕士学位论文 当1 n 7 ，结论是成立的，因为， h ( z ) 2 ( 譬) h 3 ( x ) h 4 ( x ) h s ( x ) h 6 ( x ) 岛协) 1 + 3 x + z 2 1 + 4 x + z 2 1 + 7 ：r + 1 3 x 2 + 7 x 3 + 士4 1 + 8 x + 1 7 x 2 + 8 x 3 + 。4 1 + l l x + 4 1 x 2 + 6 3 x 3 + 4 1 x 4 + 1 1 x 5 + z 6 1 + 1 2 x + 4 9 2 2 + 8 0 x 3 + 4 9 x 4 + 1 2 x 5 + 嚣6 1 + 1 5 x + 8 5 x 2 + 2 3 1 + 3 2 1 x 4 + 2 3 1 x 5 + 8 5 x 6 + 1 5 x 7 + z 8 这些多项式都只有实零点，见表3 1 ，2 r e a lz e r o s h l ( x - - 2 6 2 0 3