（运筹学与控制论专业论文）限制条件下图的极大独立集问题.pdf

- 限制条件下图的极大独立集问题 摘要 1 9 6 0 年，e r d 6 s 和m o s e r 提出在一般n 阶无向图g 中求极大独立集个数的最 大值，以及何时达到晟大值的问题e r d 6 s 解决了这个问题，随后，m o o n 汞l m o s e r 也 独立的给出了这个问题的相关结果数十年来，关于各种特殊图类的极大独立集 问题得到了广泛的研究研究限制条件下图的极大独立集的计数问题是关于图的 独立集研究的主要方向 本文在前人的工作基础上，运用数学归纳法和构造反例等方法，继续研究限 制条件下图的极大独立集问题，主要结果如下： ( 1 ) 在对树的极大独立集的计数研究中，其对应的极图( 树) 的结构一般只含 有一个最大度点本文我们研究了含有两个最大度点的树的极大独立集个数的最 大值，同时刻画取得最大值时的树的结构； ( 2 ) 同样的，关于树的极大独立集个数，不管是第一、第二、还是第三最 值，大部分极图( 树) 的直径都比较小本文给出了直径较大时树的极大独立集个 数的最大值，同时刻画取得最大值时的树的结构； ( 3 ) 最后本文对单圈图的线图中的极大独立集的计数问题开展研究，刻画 了单圈图线图中含有最大极大独立集个数的极图结构特征 关键词：树；单圈图；最大度；直径；极大独立集 t h en u m b e ro fm a x i m a li n d e p e n d e n ts e t si ng r a p h sw i t h c o n s t r a i n t s a b s t r a c t i n19 6 0 ，e r d 6 sa n dm o s c rr a i s e dt h ep r o b l e mo fd e t e r m i n i n gt h em a x i m u mh u m - b e ro ft h em a x i m a li n d e p e n d e n ts e t sf o rag e n e r a lg r a p hgo fo r d e r 礼a n dt h et i m eo f t h o s eg r a p h sa c h i e v i n gt h i sm a x i m u mv a l u e t h i sp r o b l e mw a ss o l v e db ye r d 6 s ，a n d l a t e rb ym o o na n dm o s e r i nt h ep a s td e c a d e s ，t h ep r o b l e mh a sb e e ne x t e n s i v e l ys t u d - i e df o rv a r i o u ss p e c i a lc l a s s e so fg r a p h s t o d a yt h em a i nd i r e c t i o ni st od e t e r m i n et h e n u m b e ro fm a x i m a li n d e p e n d e n ts e t so fg r a p h su n d e rs o m er e s t r i c t i v ec o n d i t i o n s o nt h eb a s i so fp r e v i o u sw o r k s ，t h i st h e s i ss t u d i e st h ep r o b l e mo ft h em a x i m a l i n d e p e n d e n ts e t s i ng r a p h su n d e rs o m er e s t r i c t i v ec o n d i t i o n s t h em a i nr e s u l t so ft h i s d i s s e r t a t i o nm a yb es u m m a r i z e da sf o l l o w s ： ( 1 ) i nt h es t u d yo fc o u n t i n gt h en u m b e ro ft h em a x i m a li n d e p e n d e n ts e t si n t r e e s ，i th a sb e e np r o v e dt h a tt h ec o r r e s p o n d i n ge x t r e m a lt r e e sa l w a y sh a v ej u s to n e v e r t e xw i t hm a x i m u md e g r e e i nt h i sp a p e rw ec o n s i d e rt h ep r o b l e mo fd e t e r m i n i n g t h el a r g e s tn u m b e ro fm a x i m a li n d e p e n d e n ts e t sf o rt r e e sw i t ht w om a x i m u md e g r e e v e r t i c e s e x t r e m a lt r e e sa c h i e v i n gt h e s ev a l u e sa r ea l s od e t e r m i n e d ； ( 2 ) i th a sb e e np r o v e dt h a tt h ee x t r e m a lt r e e sw i t ht h el a r g e s t ( s e c o n d ，t h i r d ) n u m b e ro fm a x i m a li n d e p e n d e n ts e t sa l w a y sh a v eas m a l ld i a m e t e r i nt h i sp a p e rw e s t u d yt h ep r o b l e m o ft h e l a r g e s tn u m b e ro ft h em a x i m a li n d e p e n d e n ts e t sf o rt r e e sw i t h al a r g ed i a m e t e r e x t r e m a lt r e e sa c h i e v i n gt h e s ev a l u e sa r ea l s od e t e r m i n e d ； ( 3 ) a tl a s t ，w es t u d yt h ep r o b l e mo fc o u n t i n gt h en u m b e ro ft h em a x i m a li n d e - p e n d e n ts e t si nt h el i n eg r a p ho fu n i c y c l i cg r a p h w ec h a r a c t e r i z et h es t r u c t u r eo ft h e i l l i n eg r a p ho fu n i c y c l i cg r a p hw i t ht h el a r g e s tn u m b e ro ft h em a x i m a li n d e p e n d e n ts e t s k e yw o r d s ：t r e e s ；u n i c y c l i cg r a p h s ；t h em a x i m u md e g r e e ；d i a m e t e r ；t h e m a x i m a li n d e p e n d e n ts e t s 目录 摘要 i a b s t r a c t 目录 1 绪论 1 1 1 基本概念 1 1 2 研究概况3 1 3 - 奉文的主要结果 9 2 含有两个最大度点的树的极大独立集个数1 0 2 1 引理1 0 2 2 主要结果- 1 3 3 限制直径为d 的树的极人独立集个数2 1 3 1 小直径的树的极人独立集个数2 l 3 2 人直径的树的极人独立集个数2 6 4 单圈图线 4 i 的含有最大极大独立集个数的极i c i 结构特征3 3 4 1 记号和术语3 3 4 2 引理3 3 4 3 主要结果3 5 参考文献3 9 在学期间的研究成果及发表的论文4 1 致谢4 2 浙江师范大学学位论文独创性声明4 3 学位论文使用授权声明4 3 浙江师范大学学位论文诚信承诺书4 4 i v ， i ， i-，i-。r， ，f i ll 1 1 基本概念 1绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 一个有序对g = ( ve ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素叫做图g 的项点，e 中的元素叫做图 的边通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合与边集合没有重边和环的 图叫做简单图除非特别指出，本文研究的图均指有限简单无向图 常用u ，u 表示g 中的点，e 表示g 中的边若边e = 删e ( g ) ，则说t ， 在 g 中相邻；这时又说t l 和u 是e 的端点，也说 ，t 与e 相关联设t ，是一个顶点，t ， 的全体邻点所形成的集合叫做u 的邻域，记作( ) g ( v ) u u 叫做 的闭邻域， 记作m 与t ，相关联的边的条数叫做u 的度数，记作d ( ) g 中的点的最大的 度数记作( g ) 若d ( u ) = k ( d ( u ) k ，d ( u ) 七) ，则称v 为一个k 点( k + 点，k 一 点) 如果对图g = ( ve ) 的任何两个顶点札与u ，g 中存在一条m 一 ) 骼，则称 g 是连通图g 中长度为k 的圈称为k 圈边数等于顶点数的简单连通图称为单 圈图不含圈的连通图称为树 对于图g 中两个顶点u 和 ，若g 中存在( 牡一u ) 路，则必定存在一条最 短的( t i u ) 路r ，称r 为一条( u 一 ) 最短路，r 的长度称为顶点仳与u 的距离，记为d g ( 牡，u ) ( 或d ( u ，u ) ) 定义图g 的直径d i a m ( g ) ( 简写为d ( g ) ) 为 d ( c ) = m a x d ( u ，u ) i u ，u y ( g ) ，u ) 如果一个项点的度至多为i ，那么就称这个点为悬挂点或叶子点一个度至 少为3 的点叫做支点如果一条非平凡的路p 在g 中除了端点的度不为2 ，其余 点的度都为2 ，则称路p 为串长度为l 的串称为平凡的含有g 中一个悬挂点 l 1 绪论 的串称为悬挂串如果串尸的一个端点z 是一个支点，那么就称串p 附在z 上 g 中的子图艇七称为悬挂星，如果其中有k 一1 或k 个点在g 为叶子点，且中心 点在g 与星中的度均为k 由一条i 个顶点的路p 的两个端点下一共悬挂j 条长为2 的路所得到的树 记为b ( i ，歹) n 阶树死( 礼) 定义如下：( 1 ) 若扎三0 ( m o d2 ) 且n 4 ，则乃( 佗) 为一颗星 k l 3 其中两片叶子下挂有孚条长为2 的路( 2 ) 若礼三1 ( m o d2 ) 且佗7 ，则 疋( n ) 为路r ，其两个端点下挂有学条长为2 的路 n 阶树死( n ) 定义如下：( 1 ) 若n 三0 ( m o d2 ) 且n 1 0 ，则死( n ) 为路p l o ， 其中一个端点下挂有学条长为2 的路( 2 ) 若n - - - 1 ( m o d2 ) 且n 5 ，则死( n ) 由路r 和树乃( 礼一4 ) ，用一条边连接树的中心点与r 的一个内点得到 b ( f ；i 1 ，歹1 ；i 2 ，如) ( 如图1 1 所示) 表示一棵树：给定一条f 个项点的路p ，一个 端点u l 下挂有i 1 条长为2 的路和j 1 条长为l 的路；另一个端点u 2 下挂有i 2 条 长为2 的路和j 2 条长为1 的路当j 1 = 0 且如= 0 时，我们把b ( z ；i l ，歹l ；i 2 ，如) 简 记为b ( f ；i 1 ；i 2 ) 图1 1 树b ( z ；i l ，j 1 ； 2 ，j 2 ) 给定图g ，v ( g ) 的一个子集s 称为独立集，若s 中的任何两个顶点在g 中 都不相邻如果一个独立集不真包含于其他任一独立集，就称该独立集为极大独 立集用m i ( g ) 表示g 中极大独立集的个数取得m i ( g ) 的最大值时的图称为极 图 给定图g ，e ( g ) 的一个子集m 称为匹配，若m 中的任何两条边互不相 邻如果一个匹配不真包含于其他任何一个匹配，就称这个匹配为极大匹 配a 是无边图或的唯一的匹配令朋( g ) 为g 中的极大匹配族，并且令 m ( g ) = i m ( c ) i 2 t i ， 膏 ，-i一 ”一 一 一 i r j 1 绪论 t ，c 礼，= r t n n 一- - 2 。，+ 1 萋：三三 m m 。o d d2 2 ，) ； 圳2 ir n _ 2 。+ 1 ，茬若：n n - - 三0 l ( ( m r o 。o d 2 ) d 2 ) ； 如c n ，= - ；矗r r n n 一。+ ，2 萋n n 兰= 0 1 ( 。m r o o 。d d2 2 ，) ； m ) = ，若吲n - - o ( ( m m o d 2 0 d2 ) - ) ； “d ) = r ( r n n - 一d d + m i 。( p d - 1 1 ) m i ) , ( 日一2 ) + i i l i ( r 一。) ， 若n n 一- d d 三= o l ( ( m m 。o d d2 2 ) ) ； t ，( n ，d ) ： 。( 他，d ) 若d = 5 ，d = 6 或d = 4 ，d = 7 且n d 三l ( r o o d2 ) ； it ( n ，d ) + 1 ，若d = 7 且n d 兰0 ( m o d2 ) 1 2 研究概况 图的极大独立集问题源自网络的进程间分配共享资源的问题，是图论中著名 的n p c 问题，即不可能存在一个多项式时间算法求解这个问题它虽与匹配概念 一样有着悠久的历史，却没有类似于匹配的理论图的极大独立集的计数问题对 于解决图论中的许多困难问题的算法设计有重要的意义，例如，极大独立集个数 上界的估计对于图的染色问题的算法改进非常关键 1 9 6 0 年，e r d 6 s $ 口m o s e r 提出在一般几阶无向图g 中求极大独立集个数的最大 值以及何时达到最大值的问题e r d 6 s 解决了这个问题，随后，m o o n 和m o s e r t i i 也 独立的给出了这个问题的相关结果 3 1 绪论 函= 4 么 ； ； n 三0 ( r o o d3 )n 三1 ( m o d3 ) 图1 2 一般图的极图o ( n ) 定理1 1i i i 若简单图g 的阶为礼，则 m i ( g ) 9 ( n ) = 等号成立当且仅当图 若扎= 3 s ； ，若礼= 3 s + 1 ； 若咒= 3 s + 2 g 竺g c n ，= 圣兰曼三1 ，蚝或2 心u c s 一， ； n 三2 ( m o d3 ) 若n = 3 s ； 若佗= 3 s + 1 ： 若n = 3 s + 2 当n 4 时，一般图的所有的极图都是不连通的w i l 雇文献 2 1 q b 给出了树 的极大独立集个数的最大值并提出了这样一个问题：n 阶连通图的极大独立集个 数的最值是多少? s a g a n 在文献【3 】中给出了关于树的结果的另一种简短证明，并找出了树的所 有极图 定理1 21 3 1 如果t 是一棵n 阶的树，那么m i ( t ) t l ( n ) ，等号成立当且仅当 丁竺乃c n ，= b ( 2 , - 2 王或b ( 4 孚) ，若n n 三- - 0 1 。( m m 。o d d2 2 ，) ； 而f u r e d i 4 1 ) 3 乏g d g g s 和g r i n s t e r e a d 等人【5 i 独立的给出了n 阶连通图的极大独 立集个数的最大值及极图 以 ， 知 一 ， 3 3 s ， 3 4 2 ，-j、_【 1 绪论 7 , 兰0 ( m o d3 )佗三1 ( r o o d3 ) n 暑2 ( r o o d3 ) 图1 3 连通图的极图g o ( n ) 定理1 3 【5 】若图g 为n 阶连通图，若n 5 的情 况 假设j i l 2 ，令z 为日( z ；i a + 1 ，歹l 一1 ；i 2 ，j 2 ) 中路只端点l 1 下的一个叶子 点，由引理2 1 有 m i ( b ( 1 ；i l + 1 ，j i l 1 ；i 2 ，j i 2 ) ) = m i ( b ( t ；i 1 + l ，歹1 1 ；i 2 ，j 2 ) 一【z 】) + m i ( b ( t ；i l + 1 ，歹l 一1 ；i 2 ，j 2 ) 一【乱l 】) = 2 l + 1 i i l i ( b ( 2 一l ；0 ，o ；i 2 ，j 2 ) ) + i i l i ( b ( z 一2 ；0 ，o ；i 2 ，如) ) = 2 i - ( i i l i ( b ( f 一1 ；0 ，o ；i 2 ，j 2 ) ) + i i l i ( b ( 2 3 ；0 ，o ；i 2 ，j 2 ) ) + r n i ( b ( f 一4 ；0 ，o ；i 2 ，歹2 ) ) ) + m i ( b ( z 一2 ；0 ，o ；i 2 ，j i 2 ) ) = 2 i m i ( b ( t 一1 ；0 ，o ；i 2 ，j 2 ) ) + 2 i l m i ( b ( t 一3 ；0 ，o ；i 2 ，如) ) + m i ( b ( t 一2 ；0 ，o ；i 2 ，j 2 ) ) + 2 i l m i ( b ( t 一4 ；0 ，o ；i 2 ，歹2 ) ) 现在考虑树b ( t + 1 ；i l ，j l ；i 2 ，j 2 ) 同样地，令z 为b ( z + 1 ；i t , j l ；i 2 ，j 2 ) 中路只 1 1 2 含有髓个最大度点的树的极大独立集个数 端点仳1 下的一个叶子点，由引理2 1 有 m i ( b ( t + 1 ；i a ，j l ；i 2 ，j 2 ) ) = m i ( b ( 1 + 1 ；i l ，j l ；i 2 ，j 2 ) 一u x 1 ) + m i ( b ( c + l ；i l ，j l ；i 2 ，j 2 ) 一u u 1 ) = 2 i l m i ( b ( f ；0 ，o ；i 2 ，j 2 ) ) + 血( j e 7 ( f 一1 ；0 ，o ；i 2 ，j 2 ) ) = 2 i l m i ( b ( t 一2 ；0 ，o ；i 2 ，歹2 ) ) + 2 i l m i ( b ( t 一3 ；0 ，o ；i 2 ，力) ) + m i ( r ( z 一3 ；0 ，o ；i 2 ，j 2 ) ) + m i ( b ( t 一4 ；0 ，o ；i 2 ，歹2 ) ) 由引理2 8 ，结论成立 当歹l = 1 时，反复应用引理2 1 有 m i ( b ( 1 ；i 1 + 1 ，o ；i 2 ，j 2 ) ) = 2 h + 1 1 1 1 i ( b ( z 一1 ；0 ，o ；i 2 ，j 2 ) ) + m i ( b ( t ；0 ，o ；i 2 ，j 2 ) ) m i ( r ( 1 + 1 ；i l ，1 ；i 2 ，歹2 ) ) = 2 i l m i ( b ( 1 ；0 ，o ；i 2 ，歹2 ) ) + m i ( r ( t 一1 ；0 ，o ；i 2 ，j 2 ) ) = 2 i m i ( b ( t 一2 ；0 ，o ；i 2 ，歹2 ) ) + 2 m i ( b ( t 一3 ；0 ，o ；i 2 ，歹2 ) ) + i t l i ( b ( z 一1 ；0 ，o ；i 2 ，歹2 ) ) 由引理2 8 ，结论成立 引理2 1 0 若l 1 ，d 1 ，则m i ( r ( 4 t + 1 ；d + 1 ；d + 1 ) ) m i ( r ( 4 t + 5 ；d ；d ) ) ， m i ( b ( 4 t 一1 ；d + 1 ；d + 1 ) ) m i ( b ( 4 t + 3 ；d ；d ) ) 证明：对d 进行归纳证明当d = 1 时，由引理2 1 有 m i ( b ( 4 2 + l ；2 ；2 ) = n l i ( p 4 , + 5 ) + 2 m i ( b ( 4 t ；2 ；o ) ) + 2 i i l i ( b ( 4 c ；l ；o ) ) = m i ( p 4 , + 5 ) + 4 l i ( p 4 h 2 ) + 4 l i ( p 4 , 一1 ) ， m i ( r ( 4 t + 5 ；1 ；1 ) ) = n l i ( p 4 i + 9 ) = m i ( r l + 5 ) + 2 m i ( p 4 1 + 2 ) + m i ( p 4 z + 3 ) 显然，, m ( b ( 4 t + 1 ；2 ；2 ) i ( b ( 4 1 + 5 ；1 ；1 ) ) 假设当d r n j ( b ( 4 l + 5 ；d 一1 ；d 一1 ) ) 且 2 m i ( b ( 4 1 ；d + l ；0 ) = 2 ( m i ( b ( 4 1 ；d ；o ) ) + m i ( 凡一1 ) m i ( d k 2 ) ) = 2 m i ( b ( 4 l ；d ；o ) ) + 2 d + 1 m i ( p 4 l 1 ) m i ( b ( 4 + 4 ；d ；0 ) = m i ( b ( 4 l + 2 ；d ；0 ) + m i ( b ( 4 t + 1 ；d ；o ) ) = r m ( b ( 4 t ；d ；o ) ) + 2 “( b ( 4 z l ；d ；o ) ) + m i ( b ( 4 z 一2 ；西o ) ) 容易证明2 d m i ( p 4 i 1 ) n 1 i ( b ( 4 t 一1 ；d ；o ) ) ，等号成立当且仅当z = 1 因此 2 i i l i ( b ( 4 z ；d + 1 ；0 ) m i ( b ( 4 l + 4 ；d ；o ) 由以上证明，我们有m i ( s ( 4 2 + 1 ；d + 1 ；d + 1 ) ) i t l i ( b ( 4 z + 5 ；d ；d ) ) 同理可 证不等式m i ( b ( 4 t 一1 ；d + 1 ；d + 1 ) ) m i ( s ( 4 t + 3 ；d ；d ) ) 2 2 主要结果 定理2 1 若丁是一棵含有两个最大度点的树，则 若n = 4 k + 1 ； 若n = 4 k + 2 ； 若礼= 4 k + 3 ： 若n = 4 k + 4 3 1 l l 一 一卜 ，毛卜 ， r 1 r l + + + + 3 2 3 2 一 一 一 一 n n n n r r r r ，iiilil，、【 = n 一 丁m 2 含有两个最大度点的树的极大独立集个数 等号成立当且仅当t 竺丁( 几) ，其中 ib ( 5 ；k 一1 ；k 一1 ) 或b ( 2 ；k ，o ；k 一1 ，1 ) ，若n = 4 k + 1 ； t ( 礼) ： b ( 2 ；毛尼l苎佗= 4 七+ 2 ； l b ( 3 ；七；七) ， 若亿= 4 k + 3 ； ib ( 4 ；七；七) ， 若n = 4 k + 4 证明：当n = 4 k + 2 和n = 4 凫+ 4 时，由引理2 4 ，定理显然成立所以只需 证n = 4 k + 1 和n = 4 k 十3 的情况对扎进行归纳证明由于n = 4 k + 3 与 佗= 4 k + 1 的证明思路完全类似，这里我们只证明佗= 4 k + 1 的情况 当n 1 2 时，定理显然成立令n 1 3 ，假设当n 7 n 时结论成立令丁为 一棵阶为n ，含有两个最大度点的树为方便起见，令丁为平面中的有根树且至少 含有两层，w 为只有两层子孙的顶点，y 为w 的一个儿子，z 为y 的儿子显然，x 是t 中的一个叶子点令n = 4 k + 1 若d ( y ) 3 ，则 m i ( t ) = m i ( t n i x ) + m i ( t 一【可】) t l ( n 一3 ) + ，( n 一4 1 ) 7 n 一5 + 1 + 7 n 一5 r l 一3 + r 孚 冈此令d ( y ) = 2 由于丁包含两个最大度点，所以d ( y ) 情形1 d ( w ) 如果w 有一个叶子儿子，由归纳假设可得 n f i ( t ) = m i ( t 一【z 】) + m i ( t 一【y 】) t ( n 一2 ) + ，( 佗一4 ) = 7 - n 一5 + 7 孚一1 + r n 一5 = r n 一3 + r 丁n - - 1 1 r n 一3 + r t n - - 1 因此假设w 的所有子孙形成一个匹配用r 表示7 中删除了w 及其所有子 孙的树显然r 的阶为n 一2 d ( w ) + 1 假设r 竺正( n 一2 d ( w ) + 1 ) ，那么r 为图2 1 中的一棵树不失一般性，假 设a ，b ，c ，d ，e ，g 中的一个是w 的父亲显然有 l i ( 丁一【夕】) = r 2 ( d ( t | ，) 一2 ( r n 一2 d ( 埘) + 1 2 + 1 ) = 7 _ “一5 + r 2 ( d ( ”) 一 1 4 囊 ， ， 簟 。i i 。 l ， 2 含有两个最大度点的树的极大独立集个数 c e d 图2 1 树r 的可能情形 由于d ( w ) ，所以有2 d ( w ) 孚令a w e ( 丁) ，反复应用引理2 1 有 m i ( t 一h ) = ( 1 + 2 + + 2 d ( - ) 一3 ) ( r n 一2 d ( ) + 1 2 + 1 ) + r n - 2 d ( - ) 一1 + r 生曼炉+ 1 = ( 7 2 ( d m ) 一2 ) 一1 ) ( r n 一2 d 佃) 一1 + 1 ) + r n 一2 d ) 一1 + r 旦二垒笋+ 1 ：，n - 5 + r 型! 警灶+ r 2 ( d ( 埘) 一2 1 由引理2 1 可得 n l i ( t ) = m i ( t 一【z 】) + m i ( t 一【引) = r n 一3 + r 旦二学+ r 2 ( d ( ) 一1 ) r n 一3 + 7 t n - - i 令b w e ( 丁) ，反复应用引理2 1 有 m i ( t 一【z 】) = ( 1 + 2 + + 2 d ( 埘) 一3 ) ( 7 - 2 d ( 删) + 1 2 + 1 ) + r n - 2 d ( 埘) 一1 + 1 = ( r 2 ( d m ) 一2 ) 一1 ) ( r - 2 d ( 伽) 一1 + 1 ) + r n - 2 d ( ”) 一1 + 1 = r n 一5 + r 2 ( d 佃) 一 由引理2 1 可得 m k t )= m i ( t 一【z 】) + m i ( t 一【可】) = ，- n 一3 + r 2 ( d ( ) 一1 r n 一3 + 7 下n - i 令c 伽e ( 丁) ，反复应用引理2 1 有 i i l i ( t 一) = ( 1 + 2 + + 2 d ( w ) 一3 ) ( r n 一2 d ( 伽) + l 一2 + 1 ) + r n - 2 d ( w ) 一1 + r 2 曼掣 = ( r 2 ( d ) 一2 ) 一1 ) ( 7 n 一2 d ( 埘) 一1 + 1 ) + r n - 2 d ( w ) 一1 + r 2 鱼擎灶 ：r n - 5 + r 竺垒擎业+ 7 2 ( d ( 仰) 一2 ) 一1 由引理2 1 可得 n l i ( t )= m i ( 丁一n n ) + i i l i ( t 一【引) = 7 n 一3 + 7 生曼掣+ r 2 ( d ) 一1 ) 一1 r n 一3 + r 孚 1 5 2 含有两个最大度点的树的极大独立集个数 令d w e ( t ) ，反复应用引理2 1 有 m i ( t n i x ) ( 1 + 2 + + 2 d ( w ) 一3 ) ( r n 一2 d ( w ) + l 一2 + 1 ) + r n - 2 d ( w ) 一1 + r 生鱼擎业 ：( r 2 ( d m ) 一2 ) 一1 ) ( r n - 2 d ( w ) 一1 + 1 ) + 7 n 一2 d ) 一1 + r 竺兰掣 = r n 一5 + 7 竺兰掣+ r 2 ( d ( 叫) 一2 ) 一1 由引理2 1 可得 m i ( t ) = l n i ( t n i x ) + n l i ( t 一 y 】) r n 一3 + r n - 2 d 2 ( w ) + l + 7 2 ( d ( t l ，) 一1 ) 一1 7 n 一3 + r t n - 1 令c w e ( 丁) ，反复应用引理2 1 有 m i ( t n i x ) = ( 1 + 2 + + 2 d ( ”) 一3 ) ( r n 一2 d ) + 1 2 + 1 ) + r n - 2 d ( 删) 一1 + 1 = ( r 2 ( d ( ) 一2 ) 一1 ) ( r n 一2 d 沁) 一1 + 1 ) + r n - 2 d ( 埘) 一1 + 1 = 7 n 一5 + r 2 ( d ( 伽) 一2 1 由引理2 1 可得 m i ( t ) = 1 1 1 i ( 丁一n i x ) + m i ( t 一【引) = 7 i n 一3 + r 2 ( d ) 一1 7 n 一3 + 7 孚 令，叫e ( 丁) ，反复应用引理2 1 有 m i ( t n i x ) ( 1 + 2 + + 2 d ( 埘) 一3 ) ( r n 一2 d ( w ) + 1 2 + 1 ) + r n - 2 d ( w ) 一1 + r 竺垄擎业一1 ：( r 2 ( d m ) 一2 ) 一1 ) ( r n - 2 d ( w ) 一1 + 1 ) + r n - 2 d ( w ) 一1 + 7 竺型笋出一l = r n 一5 + r 生兰学+ 7 2 ( d ( 叫) 一2 ) 一2 由引理2 1 可得 m i ( t )= m i ( t 一【z 】) + m i ( t 一【】) 7 n 一3 + r 竺垒擎业+ r 2 ( d ( ) 一1 ) 一2 r “一3 + r 孚 令g w e ( 丁) ，反复应用引理2 1 有 越( t n i x ) ( 1 + 2 + + 2 d ( w ) 一3 ) ( r n 一2 d ( w ) - - i - i 一2 + 1 ) + r n - 2 d ( w ) 一1 + r 竺垒擎业 ：( 7 2 ( d m ) 一2 ) 一1 ) ( 7 n 一2 d ( 加) 一1 + 1 ) + r n - 2 d ( w ) 一1 + r 竺型笋出 = r n 一5 + 7 - 旦二兰掣+ 7 2 ( d ( ) 一2 ) 一1 1 6 j ， ， 窖 i ，鼍， 2 含有两个最大发点的树的极大独立集个数 由引理2 1 可得 1 1 1 i ( t ) = m i ( t n n ) + m i ( t 一【可】) 7 - n 一3 + r 2 鱼警吐三+ r 2 ( d 细) 一1 ) 一1 7 n 一3 + 7 下n - - 1 若r 箬t ( n 一2 d ( w ) + 1 ) ，由归纳假设及引理2 6 有 m i ( t )= m i ( t n x 1 ) + m i ( t 一【纠) t ( n 一2 ) + r 2 d ( 叫) 一4 t 2 ( n 一2 d ( w ) + 1 ) = r n 一5 + t 2 专工一1 + ，2 d ( 伽) 一4 r n 一2 d ( w ) + l 一2 ：r n 一3 + 7 曼尹一1 ，n 一3 + ，孚 情形2 d ( w ) = 不失一般性，假设只含有两层子孙的顶点是丁中的最大度点 令另外一个最大度点为，我们可以假设的不包含叫的子孙分支恰好有 两层令尸为丁中唯一的w 一路 情形2 1 p 中有一个内点的度至少为3 pi 叫2叫 图2 2 以z 为根的树t 令z 为尸中一个度至少为3 的内点由于t 中包含两个最大度点，因此有 d ( z ) a 令t 以z 为根，如图2 2 所示用a 表示丁一名中不包含伽和的分 支的点集由情形l ，a 中的任何一个点至多含有一层子孙因此，z 与a 中的任 何一个点的距离至多为2 分别用t ( w ) 和t ( w 7 ) 来表示丁一z 中包含w 和的 分支令i 丁( 伽) i = n l ，i t ( w ，) i = n 2 假设z 中没有叶子儿子那么n 1 + n 2 = 几一2 d ( z ) + 3 令a 为a 中的一个叶 1 7 2 含有两个最大度点的树的极大独立集个数 子点由归纳假设及引理2 1 有 m i ( t ) = m i ( 丁一【o 】) + m i ( t n a uz ) t ( n 一2 ) + r 2 ( d ( 。) 一3 ) t l ( n 1 ) l ( n 2 ) r n 一5 + 7 孚一1 + 7 2 ( d ( ：) 一3 ) r n l + n 2 2 ：r n 一5 + 7 n i - - 一i 一1 + r 2 ( d ( ：) 一3 ) r n 一2 d ( ：) + 1 r n 一3 + r n r - - i 假设z 含有叶- 了儿子不失一般性，假设z 只有一个叶子儿子否则由引理 2 3 ，有m i ( t ) t ( n 一1 ) z ( 礼) 令z 为z 的仅有的叶子儿子 若d ( z ) 4 ，即z 的除了z 的子孙形成一个匹配令a 为a z 中的一个叶 子点由归纳假设及引理2 1 有 i t l i ( 丁) = r m ( t 一 n 】) + m i ( 丁一g a 】uz ) t ( n 一2 ) + r 2 ( d ( 。) 一4 ) ，( n 一2 d ( z ) + 4 ) r n - 5 + r t n - - 1 1 + r 2 ( d ( z ) 一4 ) r n 一2 d ( ：) + 4 1 = r ”一5 + r 丁n - 1 1 + r n 一5 r “一3 + r l n - - 广1 因此令d ( z ) = 3 ，即z 是z 在a 中的唯一的子孙由于死= 4 k + 1 ，我们有 丁一n i x i 兰1 ( r o o d2 ) 不失一般性，令n 1 三1 ( m o d2 ) ，n 2 兰0 ( m o d2 ) 情形2 1 1 z wge ( 丁) 由引理2 1 及引理2 4 可得 m i ( t ) = m i ( t n i x ) + m i ( t 一【z 】) t l ( n 1 ) t l ( n 2 ) + t x ( n l 一1 ) f ( n 2 1 ) r n l - ir ”2 2 + i ) + ( 7 i “l 一1 2 + 1 ) r ( n 2 - 1 - 1 ) = 7 n 一5 + r n 一7 + 7 n l 一1 + 7 - n 2 2 7 n 一3 + 7 ! 与 情形2 1 2 z w e ( 丁) 凶为n 1 3 ，d ( w ) = d ( ) ，所以礼1 n 一6 若w 有一个叶子儿子，则由 t ( 叫) i = n l 三1 ( r o o d2 ) 可得w 至少含有两个叶子儿子由引理2 1 及引理2 4 1 8 ， ， 2 含有两个最大度点的树的极大独立集个数 得 m i ( t ) = m i ( t n i x ) + m i ( t 一【z 】) t l ( n x ) t l ( n 2 ) + f ( n l 一2 ) f ( n 2 1 ) 7 _ n l 一1 ( 7 n 2 2 + 1 ) + ( r n l 一1 2 + 1 ) r ( n 2 1 1 ) = r n 一5 + r n l 一1 + r n 一5 2 r n 一3 + r t n - 1 因此假设西不含叶子儿子当n l 孚时， m i ( t ) = m i ( t n i x ) + m i ( t 一【z 】) r n l - 1 ( 7 n 2 2 + 1 ) + f ( n 一4 ) = r n - 5 + r n t - i + r n 一5 n + 2 l 时，至少含有4 个叶子儿子，因此有 m i ( t ) = m i ( t n i x ) + m i ( 丁一【z 】) r n l 一l r n 2 3 1 + ，- n l l r n 2 1 3 = r n 一7 + r n 一7 = r n 一5 r n 一3 + r t n - - 1 情形2 2 p 的每个内点都是2 度点 此时t 竺b ( 2 ；i l ，歹1 ；i 2 ，j 2 ) ，其中l + 2 i l + 2 i 2 + j l + j 2 = 4 k + 1 ，i l + i i = i 2 + j 2 情形2 2 1 1 2 歹1 + j 2 由引理2 9 ，m i ( t ) m i ( b ( 2 ；i l + 歹1 ，o ；i 2 + ( z 一2 一歹1 ) ，j i l + j 2 一( f 一2 ) ) ) 若歹l + j ；2 一( 2 2 ) 2 ，由于n = 4 k + 1 ，我1 门有歹l + j f 2 一( z 一2 ) 3 由引 理2 3 可得m i ( t ) h ( n 一1 ) ( 几) 因此令歹l + j 2 一( f 一2 ) = 1 ，那么m i ( t ) r n - 3 + ，孚，等号成立当且仅当 t 皇b ( 2 ；k ，o ；k 一1 ，1 ) 情形2 2 2 2 2 歹1 + j 2 由引理2 9 ，m i ( t ) m i ( b ( 一( j 1 + j 2 ) ；i l + j l ；i 2 + 如) ) 由于f + 2 ix + 2 i 2q - j lq - j 2 = 4 k + 1 ，i l + j l = i 2 - b j 2 ，我f 门有( i - 2 ) 一( j l + j 2 ) = 4 七一1 4 ( i l + j i l ) = 4 k 一( i l + 歹1 ) 】一1 0 令k 一( i l + j 1 ) = t ，t 1 ，则 f 一( j i l + j 2 ) = 4 t + 1 ，t 1 1 9 2 含有两个最大度点的树的极大独立集个数 由引理2 1 0 可得 m i ( t )m i ( b ( 5 ；i 1 + 歹1 + 1 - f f l + 4 # 2 ) - s ，1 2 + j 2 + 生立学) ) = m