（运筹学与控制论专业论文）关于树的四阶路谱的一个充要条件.pdf

摘要 图的路谱是结构图论的重要研究内容之一设p 是图g 中的一条路，如果 p 不是g 中任何路的真子路，则称p 为g 中的极大路，并称g 中所有极大路的 长度所成之集为g 的路谱，记为p s ( g ) 设s 为一个正整数集合，如果存在一个 连通图岔使p s = s ，则称s 为一个路谱文献【l 】中给出了一棵树有阶为2 的 路谱和阶为3 的路谱的充要条件，本文对树的路谱作了进一步的研究，给出了 一棵树有阶为4 的路谱的充要条件本文的主要结论是 定理4 ：设q 6 ，c d 为4 个正整数，n 为偶数，6 ，c d 为奇数且6 c 吐那么存 在一棵树r ，使得芦( r ) = ( 以6 ，c 川当且仅当下述条件之一成立， 1 ) 口 2 6 或c 口 6 + c ，2 口= 6 + d 2 ) 口 6 + c ，2 d = c + d 3 ) 口 c 口+ 6 ，2 c = 6 + d 定理5 ：设口 6 ，c ，d 为4 个正整数，矾6 为偶数且a 执c ，d 为奇数且c 吐那么 存在一棵树r ，使得p s ( 乃= h 6 ，c 研当且仅当下述条件之一成立t 1 ) i6 一d f ，d ，口+ d = 6 + c 关键词t 路；极大路；路谱 a b s t r a c t t h ep a t hs p e c 虮m 1o f ag r a p hi so n eo f m o s “m p 埘a n ts u b s t 卸c eo ng r a p hs 协l c t i l r e 也e o r y a p a 也p o f ag r a p h g i s m a x i m a l i f p i sn o tap r o p e rs u b p a 血o f a n yo m c rp a 血o fm e 印【p h g a n d 恤p a ms p e c 口嘲o f g d e n o t e b y p j ( g ) ，i s t h es e to f l 如g t h o fa l l m a 】【i m a l p a 血s i m c 掣a p h as e tso f p o s i t i v ei n t e g e 船i sc a l l e dap a t hs p e c 咖i f t h e r ei sac o n n e c t e d 鲫hg s u c h t h a tp 邸) = s t h e 矾c l e 【l 】g a v et h ep a ：i h 印e c 缸强o f at r e e ，c h 黜l c t e r i z eu 1 ep a _ c hs p c c 讯瑚 o f o r ；d e rt 、o 姐dt h ep a t hs p e c t n 衄o f o r d e rt h r e e t h i sp a p e rs t l l d yi h ep a t hs p e c t 咖o f a 订e e 伽幢c r ，g i v ean e c e s s a r y 觚ds u 疖c i e tc o n d i t i o nf o r 也ep 抽s p e 蛐o f o r d e rf b u l t h em a i n r e s u na r ea sf b l l o w ： t h c o f c m 4 ：l e t 仉6 ，c ，d b e f o l l r p o s i t i v e i n t e g e r s ，口i s 州e n ，6 ，c ，d a r e o d d s a n d 6 c 吐也c n t h e r ee x i s t sa t r e e ，s u c h 山a t p j ( 砷= h 6 ，c ，刃i f 姐do n l y i f o o f t h e f 0 1 l o w i n gc o n d i t i o 璐 h o l d s ： 1 ) 口 2 6 0 f c 口 6 + c ，2 口= 6 + d 2 ) 口 6 + c ，2 4 = c + d 3 ) 口 c 口+ 6 ，2 c = 6 + d t h e o r e m5 ：l e t 口，6 ，c db ef b u rp o s i t i v ei n t e g e r s ，口，6a r ee v e n sa n d 口 6 ，c ，da r eo d d s 眦d c 吐l h e nt h e 嘲s t sa 订e e ，s u c h 山a t p “d = 口，6 ，c 研i f 柏do n l yi f o n eo f t h ef o l l o w i l l g c o n d 埘0 n sh o l d s ： 1 ) l6 一d l ，d ! ，d + d = 6 + c k q w o r d s ：p a m ；m a x i 工n a lp a 也；p a t h 印e c 1 1 1 n i i 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：王缸月j 日期：埘f 年i 月胎日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留井向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：王缸月芏 日期：删年i 月归日 导师签名硼骺 b 颧：聊6 年冠f 移日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益a 园童篮童握童卮溢厦! 旦圭生i 旦二生；旦三生筮查! 作者签名：王钮j 桎 日期：冽年，月，p 日 导师签名枷：缆 日舞l ：；柙6 年irf 口日 硕士学住论文 m a s t e r s t h e s i s 第一节路谱的概念和已知的结果 对于简单有限图，一条路p 的长度指的是该路中边的条数，记为f c p ) 设p 是图g 中的一条路，如果尸不是g 中任何路的真子路，则称p 为g 中的极大路， 并称g 中所有极大路的长度所成之集为g 的路谱，记为p s ( 回即p s ( g ) = f 科g 中 存在一条长度为k 的极大路) ，并称g 实现路谱p s ( g ) 设s 为一个正整数集合， 如果存在一个连通图g 实现j ，则称s 为个路谱在该定义中，连通的条件非 常重要，否则的话，每一个正整数集都将是一个路谱对于一个阶为n 的图g ， 如果存在个正整数j ( g ) ，使得p s ( g ) = s ( g ) ，j ( g ) + 1 ，月一1 ) ，则称g 为一个s 册一 图( s 舳苫p 枷印睇打g r 印鼽对于一条路，如果它的长度为奇数，那么我们称它 为奇路，如果长度为偶数，那么称它为偶路路谱的研究源于妇6 s 一以口f ， n o m 甜船”在文献【5 】中也提出了类似的问题j 彻6 s 帆吐a 们】证明了所有至多 包含两个正整数的集合都是路谱c ，凡砌w 鲫d j 拍把m o w 6 】证明了对任何 正整数屯有无数多个女元集合不是路谱c ”，协硎d 工7 】证明了三类特殊的图 是s 彤一图马建清在文献 1 】中证明了一类含有禁用子图的哈密顿图是s 朋一 图或者是一类特殊的图有关这方面研究的详细情况可参考文献【1 8 】 关于树的路谱的研究，马建清在文献 1 】中给出了一棵树有阶为2 的路谱和 阶为3 的路谱的充要条件，并且给出了下述一般性的结果t 定理l ：设f 。 f 2 “是任意女个不同的正整数，则存在一棵树r 使得 p “丁) = 2 l 2 f 2 ，2 “1 定理2 ：设七2 ，并且f 1 ，r 2 ，“是k 个不同的正奇数，则不存在一棵树r 使得 p 5 ( ，) = ( ，l f 2 ，珞】 定理3 ：设也，冉是偶数且旷是奇数，如果旬 也 吼，那么存在一棵 树r 使得p s ( r ) = 旧，旬，靠，口) 当且仅当“ 2 口 对于本文没有定义的概念和术语见文献 1 ，9 ，1 0 】 第二节树的4 阶路谱 不妨假设阶为4 的路谱为s = n ，6 ，c ，研，其中仉6 一d 为任意正整数 2 1 奇偶性相同的路谱 由定理1 ，有 推论l ：设a ，6 ，蔓，d 是4 个不同的正偶数，贝4 存在一棵树r ，使得p s ( d = a ，6 ，c ，讲 一 一h 由定理2 ，有 推论2 ：设a ，6 ，c ，d 是4 个不同的正奇数，则不存在一棵树r ，使得p s ( d = ( 口，6 ，c 研 2 1 奇偶性不相同的路谱 在本节中，假设s 中的整数有不相同的奇偶性，在此前提下来研究s 是否 能被一棵树实现记三( 即= ( 叫卉( v ) = l l ，易见下述引理成立 引理i ：设p = 尸【“，v 】是树r 中的一条极大路，则v l 工( r ) 在文献【l 】中给出了一个重要的引理； 引理i i ：如果，是树r 的路谱中最大的一个奇数，那么幽聊( r ) 茎2 驴一1 ) 由定理3 ，有 推论3 ：设a ，6 ，c ，d 是4 个正整数，n ，b ，c 为偶数且a 6 c ，d 为奇数，那么存 在一棵树r ，使得脚( 印= n ，6 ，g 铘当且仅当c 2 d 2 3 主要结论及其证明 定理4 ：设以6 ，c ，j 为4 个正整数，n 为偶数，6 ，c ，d 为奇数且6 c 吐那么存 在一棵树r ，使得p s ( 丁) = f a ，6 ，c ，研当且仅当下述条件之一成立t 1 ) 口 2 6 茸c 口 6 + c ，2 口= 6 + d 2 ) 口 6 + c ，2 口= c + d 3 ) 口 c 口+ 西，2 c = 6 + d 为了证明定理4 ，我们先证明下述两个引理： 2 引理1 ：设s = h 6 ，c ，田为树丁的路谱，其中a 为偶数，6 ，c ，d 为奇数且6 c c + 吐于 是有觚) = 鹏) = 4 此时令d ：= 蜀，则只q ，满足引理l 的要求，但i 工 n 三( q ，) i - l i 工( p ) n 三( q ) 睁o ，与假设矛盾当x 为奇数时，令：蜀：= j p i 瑚i 冯：= 忍瑚l ，则 置，恐均为r 中的极大奇路，且峨) + 蝇) = c + d + 2 x c + 正于是有墨) = 蛹) = 4 此时令q ，：= 蜀，则只q ，满足引理l 的要求，但l 三c p ) n 三( d ) | - 1 i 三n 工( q ) | - o ， 与假设矛盾故有以p ) nh q ) o ( 2 ) 若以p ) n h q ) o ，但只q 没有公共端点此时有三c p ) n 工( q ) = o ，如图2 所 示： 耋里苎艺三 图2 不妨记p 和q 的公共子路为凰，即：p n q = 凰，其中凰可以为一个顶点，p 的剩余子路为尸1 ，尸2 ，q 的剩余子路为q l ，q 2 ，设“尸1 ) = x ，# c p 2 ) = 弘炳) = z ，故q 1 ) = m ，故q 2 ) = ”，由假设：2 o 且f = z + z + y = c ，“q ) = m + z + ”= d 为奇数 情形l ：z ，m 奇偶性相同 可令蜀：= q i 蜀p 2 ，羁：= p 1 搦q 2 ，则蜀，噩均为r 中的极大路，o 隅) = m + z + j 蛹) ：= x + z + ，是f 瞒) + 魑) = 十故q ) = c + 吐故炳) 蛹) 中必定是一 个为c ，一个为矾如果# ) = c ，则令一：= 蜀，则，q 满足引理l 的要求，但 1 工) n 工( q ) l _ l l p ) n 工【9 1 o ，与假设矛盾如果隅) = d ，则令q ，：= 置，则 只满足引理1 的要求，但l 工( p ) n 工( q ，) 峥1 l 三 n 工( q ) i _ o ，与假设矛盾 情形2 ：蕾m 奇偶性不同 则z + m 为奇数，令马：= p 。q 。，则r l 为树r 中的极大奇路且f 职，) = x + m ，如果 舣。) = x + 聊= c 或吐则可取一：= 尸，q l 或q ，：= q ，此时则，q 或只g 满足引理l 的要求，但i 三) n “q ) l = l i 三n 三( 圆i _ o 或i 三( p ) n 工( q ，) 悻l i 工( p ) n 工( q ) l - o ， 与假设矛盾于是f c r 。) = 工十m = 6 ，同理令r ：= n q 2 ，则r ：为树r 中的极大奇路 且船2 ) = n + n 由对称性可知：f 僻2 ) = y + = 6 可令噩：= q l 蜀p 2 ，弼：= 户l 蕊q 2 ，则蜀，噩均为r 中的极大路且炳) = m + 2 + 弘f 0 乏) = x + z + 一士肇为偶数，于是f 碣) = 珊+ z + _ ) ，= 口= 工+ z 十竹= f q 五) 此时易见下述恒等式成立： ( 坍+ z + 一) + 缸+ y + 力= ( x + 2 + ，0 + ( 肼+ z + 力 0 + z + 功+ 沏+ 孑+ 力= 0 + m ) + 伽+ 力+ 乜 ( 1 ) ( 2 ) 于是由( 1 ) 知t2 口= c 十d ，由( 2 ) 知：2 d = 红+ 2 6 ，即a 6 ，显然由2 0 = c + d 知： d 口 c 6 ，知其成立由于6 + c = ( x + m ) + ( x + z + ) = ( ，押+ = + 力+ 2 工= + 2 z 口 故口 6 + c ，2 口= c + d 成立 由上述证明可知t 口 f 隅) 于是有t 娟) = m + z + y = 6 ，f ( 噩) = 小+ 2 + 玎= c ，故舯一_ ) ，= c 一6 = d c ， 即2 c = 6 + 吐由于弛) = + y 为偶数，故h + ) ，= 口，4 + 6 = 0 + + 似+ = + = 伽+ z + h ) + 砂= c + 矽 c ，由( 2 ) 知t2 c = 2 z + 2 口，故c n ，于是 口， 结论2 成立 情形3 ：q l 妇) 不妨设将q 1 分成两条子路z l 和历，犯) = 五f 慨) = 弘f ( p 1 ) = n ，并且有 她) = 州，妫) = 如图6 所示： 妙1 苎么二! 图6 令s 1 ：= q l p l ，s 2 ：= p iz l 胄，s 3 ：= 兄z j ，s 4 ：= 蜀z 1 r ，贝4 贝0s l ，s 2 ，s 3 ，s 4 均为t 中的 扭吏大路，贝4 “s 1 ) = n + z + ) ，“s 2 ) = 月+ 2 + ，“s 3 ) = 卅+ y ，“s 4 ) = f + z + m ，且有 f ( p ) = f + 玎= c ，“q ) = f + z + y = d 由引理2 可假设m y 7 情形3 1 ：m ，y 的奇偶性相同 因为f + 2 + y = 吐j + n = c 均为奇数，故郴1 ) = ”+ z + ) ，为偶数，郴2 ) = 月+ z + 聊也 为偶数，且郴3 ) = m + ) ，为偶数，于是斛= + y = ”+ z + m = ，f + _ ) ，= 口，故m = y = + z = ， 与假设矛盾 情形3 2 ：巩y 的奇偶性不同 由于f + z + y = d 为奇数，则郴4 ) = m + = + f 为偶数，于是”+ z + y = m + z + j - a ， 并且邪2 ) = h + z + 册为奇数，由( 3 ) 可知：h + ：+ 州= 2 口一吐显然 + z + m 4 否 则n = 吐矛盾于是有t 1 ) + z + m = 6 ，此时有2 口= 6 + 吐由( 4 ) 可知：2 口= 6 + d = c + 仰+ 力+ 玩于 是肼+ ) ，= 6 + j c 一拓 c 如+ 6 = 咖+ 力+ o + z + m ) = 0 + 2 + 力+ 2 m = 口+ 2 m d ，结论1 成立当m + y = 6 时有l 6 + 6 = 如+ 力+ 0 + z + 埘) = 0 + 2 + 力+ 2 掰= 口+ 抽 q 结论1 ) 成立。 2 ) ，l + z + m = c ，此时有2 口= c + 吐为了证明结论2 ) 成立，下面证明n o ， 假设z 把x 分成两条长度分别为m i 、m ：的子路蜀，噩，把】，分成两条长度分别 为n - 、”：的子路五，如其中： 蜀 脚i + 2 = 6 ，n 1 十m = c 如图7 所示 局 z 】， 图7 由对称性，不妨设m m 。均为偶数，则m ：，”：均为奇数，不妨设z 为奇数， 令： 月1 ：= 置z h 皿2 ：= 局z r 2 ，焉：= 置z 圪皿4 ：= 恐z k ，则且l ，r 2 均为r 中的极大奇 路，飓，函均为r 中的极大偶路，于是邢，) = 觚) = 吼且2 口= f 僻。) + 舣：) = ( m l + z + n i ) + ( m 2 + z + h 2 ) = 6 + c + 2 z ，显然6 + 2 z = 吐否则口= c ，矛盾于是 2 口= f 僻t ) + f 职：) = c + 吐故f 僻1 ) ，f 啤2 ) 中至少有一个小于等于c ，否则a = 吐矛盾 不妨设f ( r 1 ) c ，即z + ”l ，”l + 2 + i c ，贝0 口= 珊2 + z + 竹1 6 + c 8 硕士学住论文 m a s t e r st h e s i s ( f d 上( 的n 三( 功0 不妨设x 与y 的公共子路为，即：x ny = j 剩余的子路为墨，l ，剩余的 子路为y 1 ，如图8 所示 图8 则f ( ) + 觚) = 6 ，“) + f ( y 1 ) = c 此时f 隅) + “r 1 ) = 6 + c 一2 “) 为偶数，于是 f ) + “h ) = 口，故有口= 6 + c 一2 故y 0 ) 6 + c ( j f l ) 工( 的n 三( y ) = 0 ，n h 功0 不妨记x 和y 的公共子路为z ，即t n l r = z ，其中z 可以为一个顶点，x 的 剩余子路为蜀，恐，y 的剩余子路为y l ，e ，如图9 所示： 图9 设炳) = z l ，f ( 砭) = 砘，f = z ，f ( h ) = y l ，“兄) = 此，由假设：z o 且= 勘+ z + 恐= 6 ，故 = y 1 + z + 咒= c 为奇数，下面分两种情形讨论： 1 ) z - ，n 的奇偶性相同 令一：= 蜀h ，：= 噩珏，则，均为树r 的极大路，且有f ) = z 。叫。为偶数， 于是 哆1 = 口，f ( ，) = 强毗= 6 + c 一2 z 一为偶数，于是施十y 2 = 珥4 矾必要性得证 9 硕士学位论丈 m a s t e r st i i e s i s 充分性t 假设存在四个正整数a ，6 ，c ，以其中a 为偶数，6 ，c ，d 为奇数且6 c c 6 ，于是可以构造一棵树r 如下； 令尸：= 研“0 是一条长度为c 的路，作两条长度分别为d 一；，垃尹的路分别 交尸于“g ，“学，如图1 2 示： 1 0 图1 2 则易验证p j ( r ) = s = q 6 ，c ，田 3 ) 如果口 c 口+ 6 ，2 c = 6 + 吐则有口+ 拈c ，于是可以构造一棵树，如下： 令p ：= 尸，砌是一条长度为d 的路，作两条长度均为牟的路分别交p 于 “乎，“中，如图 图1 3 则易验证p s ( r ) = s = 口，6 c 研充分性得证 定理5 ：设口，6 c d 为4 个正整数，口，6 为偶数且n 6 ，c ，d 为奇数且c 吐那么 存在一棵树r ，使得p s ( r ) = ( 嘎6 ，c 讲当且仅当下述条件之一成立： i ) l6 一d i ，d ，d + d = 占+ c 为了证明定理5 ，我们先证明下述引理： 引理3 ：设口，6 ，c ，d 为4 个正整数，口，6 为偶数且a c + 吐于 是有觚) = 魍) = 吐此时令d ：= ，则只q ，满足引理3 的要求，但i 三n 三( ) i = 1 i 三n 工( q ) 仁o ，与假设矛盾当z 为奇数时，令t 蜀：= p l 翘l 疋：= p 2 地，则 置魁均为r 中的极大奇路，且诵) + o 隅) = c + “2 j c + 吐于是有f ) = 蛹) = 吐 此时令q 7 ：= 蜀，则只满足引理3 的要求，但i 上( p ) n 上( q ，) j = 1 il ( p ) n ( q ) | - o ， 与假设矛盾故有n 以q ) o ( 2 ) 若n 以q ) o ，但只q 没有公共端点此时有三( p ) n 工( q ) = o 如图1 5 所 示； 二r 二么 图1 5 不妨记p 和q 的公共子路为，即：p n q = 搦，其中蜀可以为一个顶点， 的剩余子路为p - ，p 2 ，q 的剩余子路为q - ，q 2 ，设舻1 ) = x ，“p 2 ) = 弘f ) = z ，“q 。) = ，烈q 2 ) = h ，由假设：z o 且= x + z + y = g “q ) = + z + n = d 为奇数， 情形l ：五m 奇偶性相同 可令墨：= q t 岛岛，局：= p 1 硒q 2 ，则置，为均为r 中的极大路，f c 蜀) = m + z + _ ) ，f ) ：= z + z + ，是f 啦) + f 隅) = # + f ( q ) = c + 吐故炳) ，舭j ) 中必定是一 个为c ，一个为吐如果# ) = c ，则令p ，：= 五，则，q 满足引理3 的要求，但 i 三) n 三( q ) 降1 l 工( p ) n 三( q ) bo ，与假设矛盾如果f ) = 吐则令：= 蜀，则 只q ，满足引理3 的要求，但i 工c 尸) n 工( q ，) j _ l i 三n 三( 9 卜o ，与假设矛盾 情形2 ：x ，m 奇偶性不同 则x + m 为奇数，不妨记蜀：= p l q 。，则五为r 中的极大路且f ) = z + m ，于 是f ) 的值必为c 或西如果酗) = c ，则令一：= 蜀，则p ，q 满足引理3 的要求， 但l ( 一) n 烈q ) l - l l “p ) n 以q ) 净o ，与假设矛盾如果f ) = d ，则令d ：= 蜀，贝l j 只q ，满足引理3 的要求，但f 三( p ) n 三( ) 净1 l 上( d n 三( q ) l = o ，与假设矛盾，故引 理3 成立 由引理3 可知( 一n 工( q ) o ，因为j p q ，所以i ( 尸) n 上( q ) i _ 1 记r 为路 p 和q 所组成的图，不妨设尸与q 的公共子路为蜀，即：p nq = 蜀，p 剩余的 子路为p 1 ，q 剩余的子路为q l ，可记函：= 札一“p l ：= “，札- q = “一“1 白，显然 l ( r ) l - 3 ，而j p s ( r ) l = 4 ，故由引理i 可知：至少存在一个顶点v o 三( d 似o ，蹦， 则v og h ，) ，令r ：= r 【v 0 ，h 】是树r 中一条从咖到树r 的路并且交，于点，显 然“q 1 ) 一# ( p 1 ) = f 岛) + “q 1 ) 】一 f c 碥) + “p 1 ) 】_ “q ) 一“p ) = d c o ，于是f ( q 1 ) f ( 尸1 ) ， 且“q 1 ) + 优p 。) = c + d 一2 蛹) 为偶数，于是有下述两个引理成立： 引理4 ：如果“q 1 ) + 妒1 ) = n ，且对任意v 0 ( r ) 蜘，幻) 及其关联的路五 研v 0 ，】，下述情形之一成立： o 凰，“f 】，且# 】) = = ；， f j ) v 卅q 1 ( “f ，啪，且“q l 【v 卅，翻) = m = g ， 贝0 有p s ( r ) = p j ( r ) = f 吼c ，棚 证明：先证明对任何两个满足条件d 的悬挂点及峋，其对应关联的路r ：= q v 0 ，】，胄：= r 怕，】，满足附) nm7 ) = k ) _ f w ) - f “ 显然由于r 和，所构 成的树为r ，则p s ( r ) = h c ，奶= 芦( r ) 于是y ) n h d = l ，否则弛 “o ，一】) g ， 矛盾如果硝与r 仅有唯一的交点则由上推导可知结论成立，于是不妨记 矗与r 的公共子路为风，r 与r 的剩余子路分别为r 。皿：，不妨设础，) = h “r 2 ) = 也，f ) = ，则圪+ r = ，l + ，= ；，且m 矗2 为树? 中的极大路，于是# 僻1 ) + f 职2 ) = r - + 仡= n 一2 r a 为偶数，于是，= o ，故上述结论成立同理可证对任何两个 满足条件功的悬挂点吒及其对应关联的路月：= 月吒，吒】，砭= 砭k ，】，满足 矿瞄) n 矿隔) = 吒 = ) = f 轧! 】于是有p s ( r ) = c ，研= ( r 7 ) ，故引理4 成立 因此引理4 所构成的树具有如下结构( 如图1 6 所示) ： 图1 6 由引理4 可知t 如果p s ( ，) = a ，c ，研，而p s ( d = s ，则可以假设弛【叫) ， 或“q l 【v 卅，幻】) ，不全为； 引理5 ：如果“q 1 ) + f ( p 1 ) = 6 ，则有i6 一d i o ，舻1 ) = 学 o ，“q i ) = 学 o ， 故有c + d 6 ，6 + c 吐即i6 一d l o 令蜀：= 赐q l ，恐：= z 1 月，玛：= 赐尸l ，五：= p l q l ，则蜀，置，墨，五 均是，中的极大路，且有题设有t = x + y + z = c 为偶数，f ( q ) = z + z + ：d 为奇 数，则有t 地) = ”啊为偶数，并且有：觚) = m + 抖一，妫) = x + m ，# 隅) ：。+ ：+ 且 情形1 1 ：五m 的奇偶性相同 此时觚) = m + z + ”，锅) = m + z + y ，均为奇数并且在( c ，奶中取值，蛹) ：，+ 。 1 4 为偶数，由上面定理中恒等式( 1 ) 知。d + ( m + z 十y ) = c + 阳+ ：+ n ) ，即有m + z 叫 吐显然6 + c 以c + d 口+ 6 6 ， 故结论1 ) 成立 情形1 2 ：z ，m 的奇偶性不同 此时稍) = m + z + n ，f 隅) = m + z + _ ) ，均为偶数并且在f d ，6 l 中取值，蝇) = h m 为奇数，由( 1 ) 知：d + + z + 力= c + 沏+ z + h ) ，即有m + z + y 所+ z + h ，于是 州+ z + y = 口，所+ z + = 6 ，此时口+ c ，= 6 + c 于是当x + 聊= d 时，由( 2 ) 知 h + y = 口一乜 ，口+ d = 6 + c 而c ；等价于c + d 6 ，故结论1 ) 成立 情形2 ：= 蜥如图1 8 所示： 图1 8 设巩p 1 ) = 弘“q 1 ) = ”，并且有弛) = # = 州，令蜀：= rq l 局：= 础，蜀：= r 一，局：= 户1 q - ，则置，局，局，蜀均是树r 中的极大路，且# ( p ) = f + ，= c 为偶数， f ( q ) = f + = d 为奇数，则f ) = ”+ y 为偶数下面分两种情形讨论t 情形2 1 ：f ，m 奇偶性相同 则撕) = f + m 为偶数，魍) = m + ”，f 隅) = m + y 均为奇数，易见下述恒等式 成立z o + 玎) + ( 州+ 力= ( f + 肌) + ( 一+ 力竺o + + ( m + ，力( 5 ) 由( 5 ) 可知tm + y 争! ，c ! ，于是c + d 6 ，6 + c 正故结论1 ) 成立 情形2 2 ：f ，奇偶性不同 1 5 硕士学住论文 m a s t e r st h e s i s 则弛) = f + ，l 为奇数，炳) = m + h ，魍) = 小+ y 均为偶数，由( 5 ) 可知： 小十y ，d ，口+ d = 6 + c ，于是结论3 ) 成立 情形3 ：e 1 p l ( 卿，均如图1 9 所示z 图1 9 设f ( z 1 ) = = ，“z 2 ) = 弘“q 1 ) = ”，并且有f ( 岛) = f ，f = 鸭则由假设有z o 令：= 兄z 1 q i ，噩：= r z l 岛，坞：= a q l ，蜀：= 冗z 2 ，则蜀，恐，揭，凰均是r 中的极 大路，且有题设有；f ( p ) = f + y + z = c 为偶数，“9 = f + n = d 为奇数，则有t 编) = ，l + y + z 为偶数，并且有：觚) = n + z + ，f ) = f + z + m ，# ) = + 弘 情形3 1 ：m ，j ，奇偶性相同 则地) = m + y 为偶数，慨) = f + 2 + m 为奇数，觚) = + 2 + 为偶数，下 面可以分两种情形讨论： 1 ) f 0 毛) = f + z + 刀= c ，由( 3 ) 知栉+ z + 埘= h + 2 + _ ) ，若刀+ z + 埘= 朋+ ：+ y = q 贝由 ( 4 ) 知：一十_ ) ，= 口+ c d 一拓 以矛盾故m + z + 栉= m + z + y = 6 ，此时由( 4 ) 知 珊+ y = 6 + c d 一幻 ”+ z + y ，于是行+ 三+ m = 6 ，一+ = + y = d ， 有6 十c = 口+ d ，由( 4 ) 知tm + y = 口一2 z 口，矛盾 情形3 2 ：，2 ，奇偶性不同 则弛) = m + y 为奇数，f 隅) = f + z + m 为偶数，觚) = ”+ z + m 为奇数，当 日+ z + = c ，则由( 4 ) 知：掰+ y = 2 c d 一2 z d ，只 需证明c + d = 2 口 6 选取树r 中长度分别为6 ，c 的极大路五y 使得i ( 的n 上( y ) i 尽可能大，于是 ( 0 矿( 柳n h y ) = o 由于r 是一棵树，则路x 和路y 之间存在一条路，记为z ，并设# ( 刁= z o 假设z 把x 分成两条长度分别为m 。、耽的子路五，局，把y 分成两条长度分别 为n 1 、n 2 的子路玎，琏其中；m l + m 2 = 6 ，m + h 2 = c 如图2 l 所示t 蜀局 z 图2 l 不失一般性，假设m 。、地均为奇数，n 。为偶数、均为奇数，由对称 性，不妨设z 为奇数时，令r 。：= h z 蜀，尺：= y i z 为均为丁中的极大偶路，于 是卯t 。) = o 僻2 ) = 口，否则，若其中至少一个值为6 ，不妨设f 眯t ) = 6 ，则此时可取 z = r i ，y 满足条件，但i 三) n y ) l - l i 工( j j c ) n 联n 降o ，这与五y 的选取 矛盾此时2 口= 巩r 1 ) + f ( r 2 ) = 帆+ z + 1 ) + + z + m 2 ) = 6 + 2 ( m + z ) 6 ，于是 c + d = 2 口 6 ，结论1 ) 成立 ( 国工( 砷n 三( 功0 不妨设x 与y 的公共子路为y o ，即：x ny = y 。z 剩余的子路为蜀，y 剩余的 子路为y l 。如图2 2 所示： 图2 2 则故) + # 隅) = 6 ，“) + “r 1 ) = c ，此时f 隅) + “h ) = 6 + c 一2 “) 为奇数，于是 当# ) + “耳) = d 时，满足引理5 的条件，于是结论1 ) 成立当f ) + “五) = c 时，“y o ) = f 隅) = ，f ( h ) = c 一多o ，于是有c ；，故c + d 2 c 6 ，结论1 ) 成立 ( 打0 工( n 三( n = 0 ，y ( 田n 啊”0 不妨记工和y 的公共子路为z ，即：工n y = z ，其中z 可以为一个顶点，z 的 剩余予路为蜀，丑，y 的剩余子路为y i ，琏如图2 3 所示t 上 遮l1 | 图2 3 设# ( 蜀) = 均，巩砭) = 耽，# ( z ) = z ，“y 1 ) = 儿，“如) = m ，由假设z o 且f = x 。+ z + 耽= 6 ，故y ) = y l + ：+ 雎= c 为奇数，由对称性可以考虑“) ，l 的奇偶性相 同的情形，此时有托+ n 为偶数，于是尬+ 此= 5 + c 一2 z 一( x 1 + y ) 为奇数，显 然z i + 儿= 岛勋+ 此= 吐否则如+ m = 6 或恐+ y 2 = c ，则可选取：= 五r l 或 】，= 恐b ，但f 三f ) n 工( y ) i = 1 i 上( 田n 三( 即j _ o 或i 三( 的n ( ，) i = 1 j ( 柳n 上( dpo ， 与x ，y 的选取矛盾此时令五l ：= h z 疋，飓：= 蜀z 玛，则r i 为树r 中的极大偶 路，恐为树丁中的极大奇路，由上可知：彻一) = 皿淝) = 吐此时由恒等式t 0 1 + z + 砘)