（运筹学与控制论专业论文）关于路谱的一些探讨.pdf

硕士学位论文 m a s t e r lst h e s i s 摘要 设p 是图g 中的一条路，如果p 不是g 中任何路的真子路，则称p 为g 中的极大路。并称g 中所有极大路的长度所成之集为g 的路谱，记为 p s ( g ) 。设s 为一个正整数集合，如果存在一个连通图g 使得p s ( g ) = s ， 贝9 称s 为一个路谱对= 5 - - 个阶为n 的图g ，如果存在一个正整数s ( g ) 使 得p s ( a ) = s ( g ) ，s ( e ) + 1 ，n 1 ) ，则称g 为一个s p s 一图 本文共分三节，第一节简单介绍了路谱的概念和相关的研究成果。第二节 证明了一类含有禁用子图的哈密顿图是s p s 一图或者是一类特殊的图。第三节 对树的路谱进行了研究，给出了一棵树有阶为2 的路谱和阶为3 的路谱的充 要条件。本文主要结果如下； 定理2 2设g 为2 一连通图，如果g 中任何导出子图都不与既3 或 屁同构，则g 是一个s p s 图或者g 满足下面的条件： ( i ) v ( g ) = a t 3 x u b 是v ( g ) 的一个捌分； ( i i ) g 刎，g b 是完全图； ( i i i ) x 中每个点都与启中所有点相邻； ( i v ) g j 是完全图或者f x f = 2 且 ，a ( z ) ) 。x 形成a 的一个划分； ( v ) a 中的每个点在x 中至多有一个邻点 定理，设a ，b 是两个正整数，则s = a ，b ) 是树的路谱当且仅当下述 条件之一成立： ( i ) n ，b 均为偶数； ( i i ) a ，b 中恰有一个为偶数且! 口 c 且l 。一b j m 。 口，6 关键词：路；极大路；路谱；s p s 一图 i i 硕士学位论文 m a s t e r st h e s i s a b s t r a c t a p a t h p o f a g r a p h g i s m a x i m a l i f p i s n o ta p r o p e r s u b p a t h o f a n y o t h e r p a t h o ft h eg r a p hg a n dt h e p a t hs p e c t r u mo fg ，d e n o t eb yp s ( g ) ，i st h e8 e t0 f l e n g t ho f a l lm a x i m a l p a t h si nt h eg r a p h as e ts o fp o s i t i v ei n t e g e r si sc a l l e da p a t hs p e c t r u m i ft h e r ei sac o n n e c t e d g a p hg s u c ht h a t p s ( g 1 = s f o r a g r a p h go fo r d e r 礼，i ft h e r ee x i s t sa ni n t e g e r8 ( a ) s u c ht h a tp s ( g ) = 8 ( g ) ，s ( a ) + 1 ，札一1 ，t h e ng i sc m l e das t r i n gp a t hs p e c t r u mg r a p h ( s p s g r a p hf o r s h o r t ) t h i sp a p e ri sc o m p o s e do ft h r e ep a r t s ：i nt h ef i r s tp a r tw ei n t r o d u c es o m e c o n c e p t sa n dr e s u l t sa b o u tp a t hs p e c t r u m ；i nt h es e c o n dp a r tw es h o v et h a t e v e r y2 - c o n n e c t e d ， 甄3 ，p 5 一f r e eg r a p h i se i t h e ra s p s g r a p ho ras p e c i a lk i n d o fg r a p h ；i nt h et h i r dp a r tw es t u d yt h ep a t hs p e c t r u mo fat r e e ，c h a r a c t e r i z e t h ep a t h s p e c t r u m o fo r d e rt w oo rt h ep a t hs p e c t r u mo fo r d e rt h r e e t h em a i n r o s a 】t sa r ea sf o 】l o w s ： t h e o r e m2 2 ：l e tgb ea 2 - c o n n e c t e d ， 硒，3 ，忍) 一f r e eg r a p h ，t h e ng i s e i t h e ras p s g r a p ho rs a t i s f i e st h ef o l l o w i n gc o n d i t i o n s ： ( i ) v ( a ) = a u x ubi sa p a r t i t i o no fv ( a ) ； ( i i ) b o t hg 陋 a n da b a r ec o m p l e t e ； f i i i ) e v e r yv e r t e xo fx i sa d j a c e n tt oa l lv e r t i c e so f _ b ： ( i v ) e i t h e rg 瞵j i sc o m p l e t eo rl x = 2 a n d 批) x f o r m sap a r t i t i o n o f4 ： f v ) e v e r yv e r t e xo fa h a sa tm o s t0 t 1 0n e i g h b o ri n t h e o r e m ，：l e ta ，bb et w op o s i t i v ei n t e g e r s ，t h e ns = 口，6 ) i sap a t h s p e c t r u mo fat r e ei fa n do n l l yi fo n eo ft h ef o l l o w i n gt w oc o n d i t i o n sh o l d s ： i i i 硕士学位论文 m a s t e r st h e s i s ( i ) a ，ba r ee v e n s ； ( i i ) o n l yo n eo fo ，bi se v e na n d ； 。 c a n di n b j m a x a ，” k e yw o r d s ：p a t h ；m a x i m a lp a t h ；p a t hs p e c t r u m ； s t r i n gp a t hs p e c t r u mg r a p h i v 硕士学位沧文 m a s e r sl h i ：s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：b 建； 日期：五妒i s 年# 月f 三日 学位论文版权使用授权书 本学位沦文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 作者签名：马建 日期：加p r 年6 月i 二日 导师签名 枷锨 日瓤前z 月肛e l 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本 人的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章 程”中的规定享受相关权益。回童逾童握銮后进后；旦主生；旦二生；目三生 筮查! 作者签名：岛建7 i 日期：咕年月j l 日 导师签名铘玩 日期和好月p - 日 硕士学位论文 m a s t e r lst h e s i s 第一节引言 1 1 路谱的概念和已知的结果 本文考虑的图都是简单有限图图g 的一条路指的是一个点序列，其中 各个点都不相同并且相继的点是相邻的。一条路j p 的长度指的是该路中边的 条数，记为f ( p ) 如果g 中有一条路p 经过g 中所有的点，则称p 为g 的哈密顿路。如果g 中包含一条哈密顿路则称g 是可迹的如果对g 中任 何非哈密顿路p ，都存在一条路q 使得v ( p ) cv ( q ) ，则称该图是路可延 展的。显然，一个图如果是路可延展的则这个图一定是可迹的。h e n d r y 最早 提出了路可延展和圈可延展的概念。并且证明了一个图是哈密顿图或是可迹 图的一些著名的充分条件也隐含该图是路可延展的和圈可延展的。 如果图g 中的一条路p 的长度是所有路中最大的，则称路p 为g 的一 条最大路。传统的，对一条路p ，如果不存在路q 使得v ( p ) 为v ( q ) 的一 个真子集，则称路p 为一条极大路根据这个定义，任何路可延展的图的最 大路和极大路都是该图的哈密顿路。在本文中，我们将研究极大路的另一种定 义，根据这种定义将不会出现上面的平凡情形。如果对图g 中的一条路p ， 不存在一条路q 包含路p 作为真子路，则称路尸为一条极大路等价地， 一条路p 为极大路当且仅当路p 不能从它的两个端点延展，用极大路的这种 定义，我们定义图g 的极大路谱为g 中所有极大路的长度构成的集合，记为 p s ( g ) 。即 即( g ) ； 七fg 中存在一条长度为k 的极大路) ， 并称g 实现路谱p s ( c ；) 。设s 为一个正整数集，如果存在一个连通图g 实现s ，则称5 t 为一个路谱。在该定义中连通的条件非常重要，否则的话，每 一个正整数集都将是一个路谱。对于一个阶为n 的图g ，如果存在一个正整 数s ( g ) 使得p s ( g ) = s ( g ) ，s ( g ) + 1 ，n 1 ) ，则称g 为个s p s 一图。 路谱的研究源于j a c o b s o ne t a 1 ，t h o m a s s e n 在文献 4 】中亦提出类似的 硕士学位论文 m a s t e r st h e s i s 问题。j a c o b s o ne t a 1 1 证明了所有至多包含两个正整数的集合都是路谱 c h e n ，f a u d r e ea n ds c h i e r m e y e r 5 证明了对任何正整数k ，有无数多个k 元 集合不是路谱。c h e n ，h ua n dl i 7 证明了三类特殊的图是s p s 一图。关于该 方面研究的详细情况可参见文献 1 ，2 ，3 ，4 ，5 ，7 ，8 。 对任意的路p 阻，d ，我们假定它有一个从“到可的定向并且p 一表示相 反的定向对y ( p 口】) 中点z ，如果x v ，用矿表示z 的后继点，z 埘 表示( z 十( 卜1 ) + 。类似地，用z 一表示。的前继点，x 一表示( x - - ( i - 1 ) ) 一对于 一条路，如果它的长度为奇数，那么我们称它为奇路；如果长度为偶数，那么 我们称它为偶路。对于本文没有定义的概念和术语见文献 6 , 9 ，1 0 j 。 1 2 主要结论 本文所做的工作可以分为两部分：第一部分：证明了一类涉及到禁用子图 的哈密顿图是s p s 一图或者是某类具有特殊路谱的图；第二部分：研究一类特 殊的图，树的路谱。并且给出了一棵树有阶为2 的路谱的条件和阶为3 的路 谱的条件 定理2 2设g 为2 一连通图，如果g 中任何导出子图都不与k - 3 或 尸5 同构，则g 是一个s p s 一图或者g 满足下面的条件： ( i ) v ( g ) = a u x u b 是v ( c ) 的一个划分； ( i i ) g a ，c b 】是完全图； ( i i i ) x 中每个点都与b 中所有点相邻； ( i v ) g f x 是完全图或者l x l = 2 且 a ( z ) ) 。x 形成a 的一个划分； ( v ) a 中的每个点在x 中至多有一个邻点 关于树的路谱，我们有下述结论： 定理3 1设t 1 t 2 t 且i r s 1 t 定理3 5设r ，s 和t 是三个正整数如果r 是奇数；s 和t 是偶数且 s ； 定理3 6设e 1 ，e 2 ，是偶数且o - 是奇数，如果e 1 e 2 e ， 那么存在一棵树丁使得p s ( t ) = e 1 ，e 2 ，e k ，口) 当且仅当e k 2 口 根据定理3 1 和定理3 2 可知： 推论3 1设r ，s 和t 是三个不同的正偶数，则存在一棵树r 使得 p s ( t ) = r ，s ) 或者 r ，s ，t 推论3 2设ns 和t 是三个不同的正奇数，则不存在一棵丁使得 p s ( t ) = r 1s ) 或者ns ，t ) 3 硕士学位论文 m a s t e r st h e s 【s 第二节关于s p s 一图的一个充分条件 很明显，所有的s p s 一图都是可迹图，因此可迹图是s p s 一图的必要条件。 另一方面，不难说明并非所有的可迹图都是s p s 一图。然而，我们期望涉及到 禁用子图的哈密顿图也是s p s 一图，或者除了某些例外图是s p s 一图涉及到 禁用子图的哈密顿图在前二十几年得到了深入的研究。下面是其中一个有趣 的结果。 定理2 1设g 为2 一连通图，如果g 中任何导出子图都不与k 1 ，3 或 b 同构，则g 是一个哈密顿图。 本文将证明下面的结论 定理2 2设g 为2 一连通图，如果g 中任何导出子图都不与k 1 3 或 尸5 同构，则g 是一个s p s 一图或者g 满足下面的条件； ( i ) v ( o ) = a u x u b 是v ( c ) 的一个划分； ( i i ) a a ，g b 是完全图； ( i i i ) x 中每个点都与b 中所有点相邻； ( i v ) o x 是完全图或者i x j = 2 且 j 7 v a ( z ) 。x 形成a 的一个划分； ( v ) a 中的每个点在x 中至多有一个邻点 证明：假设定理2 2 的结论不成立设p = p u ， 】是g 中一条长为p 的极大路，并且g 中不含长为p + l 的极大路，其中p n 一3 设h 为 g v ( p ) 的一个连通分支。 因为p u ，”】是一条极大路，所以 ( u ) c o _ v ( p ) 且( ) y ( 尸) 引理2 1对每个z v ( h ) ，d p ( z ) 1 。 4 硕士学位论文 m a s t e r st h e s i s 证明：用反证法。假定存在一个点2 v ( h ) 使得d p ( z ) 三2 。设x 。，z 2 为z 在p 上的前两个邻点，且g + = a i v ( p z 1 ，z 2 ) ) 】。为了证明引理2 1 ， 我们需要证明下面的一些断言。 断言1 对任意的w v ( g + ) ，有d i s t c + ( x l ，训) s2 证明：假设结论不成立，则存在点w v ( a 4 ) 使得d i s t a - ( z l ，w ) 23 ， 则g + 有一条阶至少为4 的导出( 。，”) 一路，记为q 1 。易见a i r ( ) u z ) 是g 中阶至少为5 的导出路这与定理2 2 的假设矛盾因此断言1 成立 断言2 z z f e ( g ) ，i = l ，2 证明：因为z e ( g ) 并且x i z ，孔z r e ( g ) ，如果z 产z _ 岳e ( g ) ，那 么 甄z 产，z f ，z ) 诱导出一个甄，。，产生矛盾因此断言2 成立 断言3 z f z 2 ，z f z i ，。1 。i ，z z 2 隹e ( g ) 证明：假定z i z 2 e ( g ) ，贝4p 【“，z i z i 茁2 。z l 尸陋1 ，z i z i z 亨p z v 是 一条长为p + 1 的极大路，与定理2 2 的假设矛盾。 假定z i z i m a ) ，贝4p f “，z f z i z i p 一睁i ，z i z 1 2 。2 p 瞄2 ，叫也是条长 p + 1 的极大路，产生矛盾 假定。1 。i e ( g ) 则f l u ，z f 。i 对p 陆 ，z i z i 茁1 z 。2 p 【。2 ，v 也是一条长 为p + 1 的极大路，产生矛盾 假定x + x 2 e ( g ) ，则p hz 1 x l z x 2 x t p x i _ ，。i z i 对p p 亨，u 也是一条 长为p + 1 的极大路，产生矛盾 综上所述，x f x 2 ，x i2 c 2 一，勋z i ，x + z 2 仨e ( g ) 根据断言1 和断言3 ，d i s t 伊( z 1 ，。i ) = 2 ，因此存在一个点y v ( a + ) 使得z 1 y ，z i e ( g ) 因为g 。l ，。i ，y ，z 与k l ，3 不同构并且z i z ，y z 芒e ( g ) ，故z i 掣e ( g ) 由断言3 可知z r z 2 ，z i z i 隹e ( g ) 又因为g z ，勋，z i ，y ，z i ) 与p 5 不同构 5 硕士学位论文 m a s t e r st h e s i s 并且z i 。，y z ，z ；z 隹e ( g ) ，所以x 2 y e ( g ) 既然。 z 2 隹e ( g ) ，故y 对 考虑图g 【 可，z i - ，y 一，z i 如果z i 可一e ( g ) ，那么p 阻，x 1 x i y p i v 一，x 1 x l z x 2 y p y ，z i z i 。亨_ p 陋手，” 是一条长为p + l 的极大路； 如果。i 可一e ( g ) ，l g z , p b ，z i z i z p k ，y - y z i p f z i ，y y x l z x 2 p k 2 ，v 是一条长为p + 1 的极大路因此。f g 一，z i 可一隹e ( g ) 由断言3 可知，茁i 。i 仁e ( g ) 因此，g ，x l ，y 一，。i 是一个诱导的 k 1 3 ，产生矛盾因此引理2 1 的假设错误，原命题的结论成立。 引理2 2 设f y ( p ) i = 则g ( p ) j 掣甄或者e l y ( p ) 皇一 z l z 2 ) ，其中x l ，x 2 v ( p ) ，并且当g i v ( p ) 型k t 一 z l z 2 ) 时，有n p ( h ) = x l ，。2 ) 证明：因为g 是2 一连通的，所以l n p ( h ) i 2 。设日在p 上的第一 个邻点为。1 ，并且a l n h ( x 1 ) ，由引理1 ，我们得到n p ( a 1 ) = 。1 情形l ：图g 存在一点b 日( 铂) 使得且瞄( 6 ) = 0 由断言2 可知，z i 对e ( g ) 如果x l z i 2 岳e ( g ) ，因为a ( b ) = 0 并且p ( 0 1 ) = x 1 ) ，那么 b ，a 1 ，z l ，。i ，。i 2 诱导出一个p 5 ，产生矛盾因此z ，。i 2 e ( g ) 类似地，2 2 1 z f 3 ，z i z f 4 ，g l z f 4 = z l n e ( g ) ，z l z ，z l z 2 ，。l 。 = = z 】秽 e ( g ) 即v ( p ) n i x l 对任意的v i ，v ( p ) z 1 ) ，如果优隹e ( g ) ，那么 x l ，a i ，v i ，) 诱 导出一个k i ，3 ，所以t | e ( g ) 因此，a i r ( p ) 】是一个完全图既然f y ( 尸) j = t ，故a i r ( p ) 】竺k 情形2 ：对任意的点b n h ( n 1 ) ，p ( b ) 0 6 硕士学位论文 m a s t e r st h e s i s 既然g 是2 一连通的，不失一般性，假设存在一点b 1 n h ( a 。) 使得 m p ( b z ) 矗t ) 由引理l ，不妨设p ( b 1 ) = 2 2 ) 由断言2 可知，z i 对e ( g ) ，设p + = p u ，z i 】z i 。丰p 【z 手，” ，则p + 是 一条长为p 一1 的极大路并且p - ( b 1 ) = o ，a l b l e ( g ) 类似情形l 的证明可得，g v ( p + ) 】= g ) 一 z z h 是一个完全图 类似地，g v ( p ) 一 。z ) ) 是一个完全图 如果x l x 2 e ( g ) ，那么g 【y ( p ) 垒k 如果z ，x 2 茌e ( g ) ，那么g y ( p ) 型k 一 z - z 2 ) 当a i r ( p ) 】型k t 一 z l z 。) 时，假设n p ( h ) 。，x 2 ，则存在一个点 a v ( h ) 使得 ( n ) = 。) 并且x x l ，z z 类似地，a v ( p ) 一 z ) j 是一 个完全图，则z l z 2 e ( g ) ，这与事实2 ；1 6 2 e ( a ) 矛盾因此当e l y ( p ) 】兰 t 一 z l z 2 ) 时，n p ( h ) = z 1 ，x 2 引理2 3h = g y ( p ) ，即g v ( p ) 是连通的 证明：假设结论不成立皿是g v ( p ) 的一个连通分支并且凰日 我们有下面的断言。 断言4 n p ( h ) n n p ( h 1 ) = d 证明：假设断言不成立，存在一点z | t v p ( 日) na ( 日1 ) 使得a l 1 ，( 阿) ，n 2 v ( h 1 ) 并且n l z ，a 2 x e ( g ) 由引理2 1 可知，a l x 一，a 2 x 一e ( g ) ，既然c l x ，z 一，a l ，a e 与k 1 ，3 不 同构，则a l a 2 e ( g ) ，这与h 和日1 是g v ( p ) 的不同的连通分支矛盾 因此断言4 成立。 不失一般性，假定a l y ( 日) ，a 2 v ( h 1 ) 并且p ( 8 1 ) = m ，n p ( 8 2 ) = y 2 ) 因为g 是2 一连通的，所以存在一点6 l 以口) 并且铂6 1 e ( a ) 使得 b l y l 芒e ( g ) ， 7 硕士学位论文 m a s t e r st h e s i s 由断言4 可知，b l y 2 ，口2 可1 车e ( g ) 如果y l y 2 e ( g ) ，那么 b a ，l ，y 1 ，y 2 ，。2 ) 诱导出一个p 5 ；如果y a y 2 隹e ( g ) ，根据引理2 2 ，u y l ，u y 2 e ( g ) 又因为 ( ) c c _ v ( p ) ，所以 6 l ，0 1 ，y 1 ，u ，y 2 ，a 2 ) 诱导出一个r ，产生矛盾 因此，h = g y ( p ) 引理2 4日是一个完全图 证明； 不失一般性，假定a l ，a 2 v ( h ) 并且y p ( a 1 ) = 1 ) n p ( a 2 ) = 。2 ， 为了证明引理2 3 ，我们需要用到下面的几个事实。 事实1 g ( 戤) ，( i = 1 ，2 ) 是完全图 对任意的v i ，n u ( z 1 ) ，则v i x ，v j x l e ( g ) 由引理2 2 可知， u x e ( g ) 又因为( ) y ( p ) ，所以钍地，u v j 仁e ( g ) 既然g 札，x 1 v i ：码与k 1 ，3 不同构，故忱码e ( g ) 因此g h ( z ) 是完全图 类似地，g i n h ( x 2 ) 】是完全图因此事实1 成立。 令h + = a v ( n ) u z 1 ) 】 事实2 对任意的y v ( h + ) ，d i s q t ( x l ，y ) 兰2 假设结论不成立，存在y v ( h + ) 使得d i s t f t 一( 5 9 ，y ) 3 ，则图日+ 中存 在一条阶至少为4 的诱导的( 茁，) 一路，记为q 3 。 因为( “) y ( p ) ，n ( u ) nv ( q 3 ) = 。t ) ，所以g u ) uy ( q 。) 包含一 个诱导的b ，产生矛盾，因此事实2 成立。 由事实2 可知，对任意的y v ( h + ) 日( z 1 ) ，有d i s t 日- ( x l ，9 ) = 2 ，因此 存在一点a l 0 ( z 1 ) 使得a l y e ( g ) 事实3 g 口( 。，) u 矗( 。) j 是完全图 8 硕士学位论文 m a s t e r st h e s i s 假设结论不成立，因为g j h ( 墨) ，( i = 1 ，2 ) 是完全图，故存在0 1 n h ( x 1 ) ，a 2 n n ( z 2 ) 使得a l a 2 隹e ( g ) 由事实2 可知，存在一个b l n n ( x 1 ) 使得a 2 b l e ( g ) 由事实1 可知，a i b f ( g ) 根据引理2 1 ，a l z 2 ，b l x 2 聋 e ( g ) 根据引理2 2 ，z 2 u e ( g ) ，既然n ( u ) y ( p ) ，有u a l ，u b l ，u a 2 隹e ( g ) 因此 o ，6 ，a 2 ，x 2 ，铭 诱导出一个姥，产生矛盾因此事实3 成立 事实4 对任意的秒v ( h ) n h ( x 1 ) un h ( x 2 ) ，有n h ( x 1 ) l j h ( z 2 ) 量 ( ) 假设结论不成立，存在y v ( h ) n h ( x 1 ) un i t ( x 2 ) ，。l n h ( w 1 ) ，a 2 n h ( x 2 ) 使得y a l e ( c ) 且y a 2 岳e ( g ) 由事实3 可知，a l a 2 e ( g ) 故 可，a l ，a 2 ，印，) 诱导出一个p 5 ，产生矛盾所以a k ( z 2 ) ( 可) 类似地， n h 伽1 ) c ( g ) 因此，( 。) u ( x 2 ) ( y ) 事实5 对任意的y l ，y 2 v ( h ) n t i ( x 1 ) u 日( z 2 ) ，y l y 2 ：有y l y 2 e ( g ) 根据事实2 和事实4 不失一般性，假定a 1 n h ( z 1 ) 使得。1 1 ，0 1 2 e ( g ) 如果y l y 2 e ( g ) ，那么 。1 ，y l ，y 2 ，z 1 ) 诱导出一个k 1 ，3 ，产生矛盾因此 事实5 成立。 根据事实1 到事实5 ，我们可以得到h 是一个完全图，引理2 4 得证 设v ( h ) = a ，| v 尸( 日) = x 并且v ( p ) 一( h ) = b 由引理2 4 和引理 2 1 可知，在引理2 2 的第二种情形中，对任意的b y ( 日) ，有b n h ( a j ，因 此对任意的z v ( 日) ，有x 7 v h ( z 1 ) 或者嚣n h ( x 2 ) ，即 h ( z 1 ) ，n h ( x 2 ) 形成日的一个划分因此，g 满足定理2 2 中的条件( i ) 至条件( v ) ，定理9 2 得证 对于满足定理2 2 中的条件( i ) 至条件( v ) 的图g ，它的路谱也非常特 9 硕士学位论文 m a s t e r st h e s 【s 殊，但是g 不一定为s p s 一图我们不妨来看一个具体的例子，令定理2 2 中 的条件( i ) 至条件( v ) 中的l a i = 4 ，i b f = 3 ，x = ，d 2 ) 且a 中有3 个点与 v ，相邻，剩余的一点与v 2 相邻，则不难得到g 的路谱为p s ( g ) = 4 ，6 ，7 ，8 因此，g 不是一个s p s 一图 1 0 硕士学位论文 m a s t e r st h e s l s 第三节树的路谱 我们不妨假设阶为2 的路谱为s = ns ，阶为3 的路谱为s = ns ，f ) 其中ns ，t 是任意的正整数。 在3 t 节中，我们将考虑s 中的整数有相同的奇偶性的情形在3 2 节 中，我们将研究树的路谱在何情况下阶为2 在3 3 节中，我们将考虑1 s = 3 并且s 中的整数有不同的奇偶性的情形。 3 1 奇偶性相同的路谱 在本节我们假设s 中的整数有相同的奇偶性，并研究s 是否能被一棵树 实现记l ( t ) = ”矿( 丁) l d t ( w ) = 1 ，易见下述引理成立 引理3 1设p = p u ，v 是树t 中的一条极大路，则 u ，v c l ( t ) 定理3 1设t 1 t 2 “是任意k 个不同的正整数，则存在一 棵树t 使得p s ( t ) = 2 h ，2 t 2 ，2 ) 证明；设p = u o “l 壮“是条长为t k 的路对任意的i = 1 ，2 ，k 我们 可以作一条长为t t 的路q 心”“ 使得路q 与路p 仅在点t t t ；处相交易 见，我们得到的这个图是一棵树，记为t 路p u o ，u t 。 q d u , 。，”t 。】的长度正好 等于2 4 因此，树r 的路谱是 2 t 1 ，2 t 2 ，2 t k 结论得证 根据定理3 1 ，我们有下面的推论。 推论3 1设r ，s 和t 是三个不同的正偶数，则存在一棵树7 _ 使得 p s ( t ) = ns 或者 r ) s ，t ) 定理3 2设2 并且h , t 2r ：t k 是k 个不同的正奇数，则不存在 一棵树丁使得p s ( t ) = l ，t 2 ，“) 证明：假设结论不成立，存在一棵树丁使得p s ( t ) = t l ，t 2 ，t k ， 设p = u o “h 曲，是一条长为t 1 的极大路因为l v s ( t ) i 2 ，由引理3 1 可 硕士学位论文 m a s t e r s 豫e s i s 知， i ( d l 3 设v 9 是( t ) 如o ，钍t ，) 中任意一点，则口。y ( 纠又设 q = ? 2 0 v 1 是t 中从到v ( p ) 的一条路，使得= 毗v ( p ) 很明显， 0 r ，因此s ；充分性得证。 必要性：如果8 ；，我们可以用下面的方式构造一棵树t 令p = u o l ， 设q = q v o ，】是一条从v o 到v ( p ) 的长为s i 的路并且路口交路p 于 点札；= v x ，可以验证p s ( t ) = ns ) ，这说明我们构造的树满足条件，必要性 得证 综上所述，关于阶为2 的路谱，我们有下述结论： 定理，设a ，b 是两个正整数，则s = 峨b ) 是树的路谱当且仅当下述 条件之一成立： ( i ) a ，b 均为偶数； ( i i ) a ，b 中恰有一个为偶数且2 a 2 b 3 3 阶为3 的路谱 在这一小节中我们将讨论i s l = 3 并且s 中的整数有不同的奇偶性的情 形在陈述主要的定理之前，我们首先给出一个重要的引理。 引理3 2如果r 是树t 的路谱中最大的一个奇数，那么d i a m ( t ) 2 f r 一1 ) 。 证明：设p 是t 中一条长为r 的极大路且q 是t 中的最大路，则 l ( q 1 = d i a m ( t ) 如果q 是一条奇路，那么f ( q ) = z ( 尸) l ，所以p n q 是一条路设p n q 是一条长为茁的路，并且p 中剩余的两条子路的长度为m 和m 。；q 中剩余 的两条子路的长度为n ，和n 。，长为m 1 和2 , ，的两条路有一个公共点；长为 m 。和礼。的两条路有一个公共点如下图3 ： 1 5 硕士学位论文 m a s t e r st h e s i s p 吵 里!。 兰么里2 q 图。 不妨设礼1 礼2 ，注意到( m 1 + z + 7 l 2 ) + m l + z + m 2 ) = r + t ( q ) 是奇 数根据对称性，不妨假设m l + z + 扎2 是奇数又因为p 上长为m 1 的子 路、p nq 及q 上长为札2 的子路构成t 中的一条极大路，并且? 1 是v s ( t ) 中最大的奇数，所以 ? n 1 + z + 扎2 s r ( 1 ) 又因为 = 2 m 1 + ( n 1 + z + n 2 ) = 2 m 1 + z ( q ) 是偶数而”1 + z + “2 是奇数，所以y 2 1 + n l 也是奇数。又因为p 上长为 m ，的子路与qa z - k 为m 的子路构成t 中的一条极大路，r 是p s ( t ) 中最 大的奇数，所以 m 1 + n 1 r ( 2 ) 根据( 1 ) 和( 2 ) 可得，2 m 1 + ( 1 + z + n 2 ) 茎2 r 即2 m l + f ( q ) 2 r 因此 z ( q ) s2 ( r 1 ) 情形4 ：l v ( p ) nv ( q ) i 1 且p 和q 有一个端点为公共点 记p 和q 公共的子路为x ，p 中剩余的子路为x 2 ，q 中剩余的子路为 y 如下图4 ： 1 6 硕士学位论文 m a s t e r st h e s i s p q l ( x 1 ) + f ( y ) = l ( q )( 1 ) l ( x 1 ) + f ( x 2 ) = l ( f ) = r( 2 ) 既然l ( q ) 是偶数且r 是奇数，由( 1 ) 和( 2 ) 可知，l ( x 1 ) 和f ( y ) 有相同的奇 偶性，l ( x 2 ) 和l ( y ) 有不同的奇偶性因此恐y 是一条奇路，又因为x 2 y 是t 中的一条极大路，并且r 是p s ( t ) 中最大的奇数，所以 l ( x 2 ) + l ( r ) r( 3 ) 由( 2 ) 和( 3 ) 可知，l ( q ) + 2 i ( x 2 ) s2 r + 所以z ( q ) 2 ( r 一1 ) 定理3 4设r ，s 和t 是三个正整数如果r ：8 是奇数且t 是偶数，则 存在一棵树? 使得p s ( t ) = ( r ) s ，) 当且仅当r + 5 t 且f r s f t ， i r s i = f l ( x ) 一f ( y ) i t l r s ；l l ( q ，) 一2 ( q 。) i t ， l r s l = l f ( q ：) 一f ( q ：) i r s l l f ( x ) + f ( y ) l ( z a ) t 且1 r s t ，i r s l t ，则显然有r i t ；若r j t ， 充分性得证 必要性：假定存在三个整数r ，s 和t ，其中r 是奇数；s 和t 是偶数 如果r ，我们可以构造一棵树如下图9 ，设p = u o u l “，是一条长度为r 2 1 硕士学位论文 m a s t e r st h e s i s 的路， q l = q t u 。2 ，2 是一条交p 于点z t s 2 长度为5 2 的一条路，且 q 2 = q 2 i t t 2 ，巩2 】是一条交p 于点u t 2 长度为t 2 的路，记得到的这个图为 t ，很容易验证p s ( t ) = n8 ，味 p tt!lt,主 l q ， t q 2 ； 我们可以把定理3 5 中的结果推广到s 中有有限个偶数和一个奇数的情 形。 定理3 6设e 1 ，8 2 ：，是偶数且盯是奇数，如果e l e 2 ， 那么存在一棵树t 使得p s ( t ) = e 1 ，e 2 ，e k ，盯) 当且仅当e c 且l a b l m n 。 o ，6 ) 硕士学位论文 m a s t e r st h e