（应用数学专业论文）树的极大独立集的计数问题.pdf

， k 一 树的极大独立集的计数问题 摘要 图的极大独立集的计数问题的研究率先由e r d 6 s 等人提出m o o n 与m o s e r 解决了确定一般图的极大独立集的最大值，并完全刻画了达 到最大值的图的结构图的极大独立集的计数问题具有重要的理论意 义，对于许多图论问题( 如图的染色) 的算法设计或者算法改进具有十 分重要作用数十年来，研究者对于该问题进行了深入的研究当前对 于该问题的研究重点是研究若干限制条件下图的极大独立集的计数 问题 本文主要研究带有限制条件下树的极大独立集问题，主要研究结 果如下： ( 1 ) 第三章主要是对树的最大度的范围加以限制，研究了最大度 比较大的那些树中极大独立集的计数问题，确定了它的极值，并完全 刻画了对应的极图 ( 2 ) 第四章主要是对不含叶子的树的极大独立集进行了研究，研 究了不含叶子的极大独立集个数的小值和大值的情况，并完全确定了 各种情况的极图 ( 3 ) 第五章主要是研究了树的极大独立集个数的次大值的情况， 给出了第四，第五大值并刻画了对应的极图结构 关键词：独立集；极大独立集；最大度；树；叶子 & 掣 心 ， ： ，i 7 0 ， - 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 nt r e e s a b s t r a c t e r d 6 sa n dm o o nr a i s e dt h e q u e s t i o no fd e t e r m i n i n gt h em a x i m a li n d e p e n d e n t s e t s i ng r a p h s t h i sp r o b l e mh a sb e e ns o l v e db ym o o na n da l lt h ee x t r e m a lg r a p h sa c h i e v - i n gt h em a x i m u mv a l u ew e r ed e t e r m i n e d 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 s i ng r a p h si so ft r e m e n d o u s l yt h e o r e t i c a ls i g n i f i c a n c e ，a n dp l a y si m p o r t a n tr o l e si ni m p r o v i n ga n dd e s i g n i n ga l g o r i t h m sf o rp r o b l e m si ng r a p ht h e o r y i nt h el a s td e c a d e s ， m a n yr e s e a r c h e r sh a v em a d ei n t e n s i v es t u d yo nt h i sp r o b l e m r e c e n t l y , r e s e a r c h e r sf o - c u so nt 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 ha d d i t i o n a lc o n s t r a i n e d c o n d i t i o n s i nt h i st h e s i s ，w ef o c u so nt 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 nt r e e s o u r w o r km a i n l yi n c l u d e st h r e ep a r t s ： ( 1 ) i nt h et h i r ds e c t i o n ，w es t u d yt 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 nt r e e s w i t hl a r g em a x i m u md e g r e e w ed e t e r m i n et h em a x i m u mv a l u e sa n dc h a r a c t e r i z et h e e x t r e m a lg r a p h so ft h ec o r r e s p o n d i n gt r e e s ( 2 ) i nt h ef o u r t hs e c t i o n ，w es t u d yt h em a x i m a li n d e p e n d e n ts e t si nt r e e sw i t h o u t i n c l u d i n ga n yl e a v e s i np a r t i c u l a r , w ed e t e r m i n es o m es m a l la n dt h el a r g e s tn u m b e ro f t h e s es e t 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 ； ( 3 ) i nt h ef i f t hs e c t i o n ，w ed e t e r m i n et h ef o u r t ha n df i f t hl 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 si nt r e 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 k e yw o r d s ： i n d e p e n d e n ts e t s ；m a x i m a li n d e p e n d e n ts e t s ；m a x i m u md e g r e e ； t r e e s ； l e a v e s 尊 善 尊 参 上勖矗参 e 目录 摘要 i a b s t r a c t ，i i 目录 1 绪论 1 1 1 研究背景及研究意义 1 1 2 独立集问题的国内外研究现状 3 1 3 本文主要解决的问题1 0 2 预备知识1 l 2 1 基本概念与基本记号1 1 2 2 基本引理与定理1 3 3 最大度限制条件下树的极大独立集1 6 3 1 情形( 丁) 吲1 6 3 2 情形嘲丁) 3 7 ，对应的极图是以恐，凰为块；k o h ，g o h ，d o n g 在文献【9 1 研究 了单圈连通图中的极大独立集问题 对于一些问题，有时不一定要利用他的最大值，有时相应类型的图类的第 二，第三大值均有很大的用处文献( 3 0 1 中，研究了一般图的第二大极大独立集的 个数问题；文献【1 8 】中，分别研究了树的第二和第三大极大独立集的个数问题；文 献【1 6 】中研究了至多含r 个圈的佗阶图第二大极大独立集的个数问题，并给出了 对应的极图 在文献【2 1 】1 2 2 中定义了q u a s i 树图，并分别对q u a s i 树的图谱和r a n d i e 指标 进行了研究q u a s i 树即图g 存在点u o 使得g - u o 为树，显然当铷为叶子时，g 就是树，当让。的度大于1 时，q u a s i 树的结构就比较复杂了，他包含的圈的个数也 随着u o 的度发生了变化，g 可能是单圈图，也可能是含三个圈的双圈图，故q u a s i 树既包含了我们常见的树，单圈图等，也包含了许多结构较复杂的图，它是一类很 大的图类 计算一个图的独立集个数是一个n p h a r d 问题对于要确定一个为n p - h a r d 问题的图参数来说，我们转而确定它的界则是非常有意义的，通常也是可行的而 对于图的极大独立集个数上界的研究。其中一个最有意义的研究方向仍是考虑某 些基本性质的图类，比如，避免某些限制子图，限制直径，限制最大度等等 2 一 j 秽 tvl，重 l 绪论 ，i l i j ， n = 0 ( m o d 3 ) 、 、1 _ 一_ 删m 邮，tt 走 _ 1 或 冈入八、 _ 0 1 只 n = 2 ( md 3 ) l ，- 一，_ 二二 图1 1 ：一般图类的极图结构 1 2 独立集问题的国内外研究现状 e r d 6 s 和m o s e r 第一次提出了计算图的极大独立集的个数的问题，并刻画达 到最大值的图的结构 定理1 1 若简单图g 是阶为扎2 ，则m i ( g ) 9 ( n ) ，当且仅当g 筌c ( n ) 等号成 立其中， m i c g ，9 c n ，= 3 s ：_ 1 ，n ：= 三3 三s ：；： g = s 笔k 3 ：, 忘，甄或2 驯s + 叫风n = 3 鬻s ； 一般图的极大独立集个数达到极值时的图，如图1 1 所示 3 1 绪论 从图上我们看出当n 4 时，一般图的极大独立集个数达到极值时，极图都 是不连通的那自然地想到，在连通图类中，它的极图又是怎么样呢? 树是连通图 类中性质最好研究的图类，因此学者们最早在树中得到了比较好的研究结果，且 刻画出它达到极值时的极图 设i ，歹0 ，定义b ( i ，歹) 如下：把j 个托连到路只的两个端点( 如图1 2 所 示) ，显然t 3 ( i ，j ) 为i4 - 歹阶的树，且不唯一我们用r 表示、互 a a 三 j 1以 j = j l + j 2 图1 2 - 图b ( i ，j ) 定理1 2 【l l 】如果丁是一棵n 阶的树，那么m i ( g ) t ) ，当且仅当t 皇丑( n ) 等 号成立其中 酬= r n _ 2 ，+ 1 - 礼n 三- - 0 1 ( ( m o m o d 2 ) d 2 ) ； t 垒乃c n ，= 尝置摹；，或以4 ，孚) ，n n 兰- 0 l ( 。姗r o o d2 ) ； 由此，自然想到与树的性质类似的不连通的图即森林的极图结构 定理1 3 若f 是阶为n 的森林，则 m i ( f ( 礼) ) ，( n ) = r r ”n - 。，n 扎三= - - - 0 l ( ( m m 。o d d2 2 ) ) ； 当且仅当f 竺f ( n ) 等号成立，其中 跏，= 7 定理2 3 设t 是阶为n 的树若t 喾正( n ) ，i = 1 ，2 ，则m i ( t ) t 3 ( 礼) ，等号成立 1 4 勘1 1 1 擎一一 是卜 卜 卜芒 2 预备知识 当且仅当t 垒死( n ) 或t 竺p 9 ，其中 丽77 “+ 2 ， 3 r n 一1 4 。 n = 8 ： 几= 1 0 ； n 三0 ( m o d2 ) 且n 8 ，1 0 ； n 三l ( m o d2 ) 定理2 4 若t 是阶n 3 的树，则包含叶子的极大独立集的极图是路r 1 5 l 坫 3 最大度限制条件下树的极大独立集 在这一章中，将对树的最大度分别为f 号 a ( t ) 号1 ，a ( t ) f 詈1 的情形 进行研究，进而确定最大度在这个范围的树的极大独立集达到最大值时的图的 结构设兀( n ，) 是阶为佗4 的树，开始于一点，这点连接着佗一一1 条长为 2 的路，如图3 1 所示通过引理2 1 得到m i ( 死( n ) ，) = t l ( n ，) = 2 舻以+ 1 ， 礼5 3 1 情形a ( t ) 豳 定理3 1 设t 是阶为佗2 的树若a ( t ) f 蛩1 ，则m i ( t ) q ( n ，( t ) ) ，等号 成立当且仅当t 笺死( n ，( 丁) ) 下面对这个定理进行证明 证明：我们对阶为n 的树进行数学归纳显然，结论对阶2 n 5 的树均成 立下面设死6 假设结论对阶小于他的树均成立为方便研究，假设丁不是星， 且至少有3 层的根树设z 是在根树丁的最底层的点，z ，y 分别是z 的祖父与父 亲，t 的最大度a ( t ) 记为若d ( y ) 3 且d ( y ) ，则y 至少有两片叶子。利 用引理2 6 ，我们得到m i ( t ) = m i ( t z ) t l ( n l ，) h ( n ，) 若d ( y ) 3 且d ( y ) = ，则y 有一1 片叶子，记为x ，x l ，x 2 ，x a 一2 因 为n 6 ，利用引理2 1 ，2 6 和定理2 1 ， m i ( t ) = m i ( t 一 z l ，x 2 ，j ，x a 一2 ) ) t l ( n 一( 一2 ) ) h ( n ，) 等号成立当且仅当礼= a - i - 2 ，即t 笺矸( n ，) 下面令d ( y ) = 2 我们假设z 有歹( j 0 ) 片叶子和z ( z 1 ) 的子孙有i 个 虬情形j ，d ( z ) 1 6 一 r t 3 最大度限制条件卜树的极大独立集 2 a - n - i 上上 n 一一l 图3 1 ：树t - ( n ，) 工工 n 一- 3 图3 2 - 树t - ( n 一2 ，) l 或i 选二望 |l 图3 3 ：树t 2 ( n ，) 注意到一l a ( t n m ) 下面利用引理2 1 ，2 6 ，定理2 ，1 ， m i ( t ) = m i ( t n i x ) + m i ( t 一【引) t l ( 佗一2 ，) + 2 i - 1 t l ( n 一( 2 i + j + 1 ) ，a ( t n i y ) ) ：2 n 一一3 + 1 + 2 i - t ( 2 n 一( 一1 ) - 2 i - - j 一2 + 1 ) ： 2 i 一一3 + 2 ”一a 一 一j 一2 + 2 i 一1 + 1 2 ”一a 一3 + 2 “一一i 一2 + 2 i 一1 + i 2 n 一一3 + 2 n a 一3 + 2 “一a 一3 + 1 2 ”一一1 + 1 情形2 d ( z ) = 因此仃2 a 一歹若n 一2 i j 一1 三i ( m o d2 ) ，则利用数学归纳法和定 理2 1 ， 1 7 1 l t i - - 岔 t 1 3 最人度限制条件卜树的极大独立集 m i ( t )m i ( t n i x ) + m i ( t 一【y ) h ( n 一2 ，一1 ) + r 2 1 - 2 t l ( n 一2 i 一歹一1 ) 2 n a 一2 + 1 + r 2 i 一2 r n 一2 i j 一2 2 n a 2 + 1 + r n j 一4 2 n - a - 2 + 1 + 2 ”一a 一2 2 n 一一1 上1 等号成立当且仅当n = 2 a j ，即t 型t l ( n ，) 若n 一2 i j 一1 兰0 ( m o d2 ) ，即i 礼一a 一2 和j 2 a 一几+ 1 ，则利用数 学归纳法和定理2 1 。 m i ( t ) = m i ( t n i x ) + m i ( t 一 鲥) t l ( n 一2 ，一1 ) + r 2 i - 2 t l ( n 一2 i j 一1 ) 2 n 一一2 + 1 + r 2 i - 2r ”一2 一j 一1 2 + 1 ) 2 ”一a 一2 + 1 + r n j 一5 + r 2 i 一2 2 n 一一2 + 1 + 2 ”一一2 2 ”一a 一1 + 1 等号成立当且仅当i = n 一一2 且歹= 2 a 一扎+ 1 ，即t 竺乃( n ，) 证明完毕 3 2 情形闭( 丁) 闭 定理3 2 设t 是阶为n 5 若薏1 ( 丁) 5 6 ； 正( 佗，( 丁) ) 见图3 3 证明：我们对阶为n 的树进行数学归纳设t 是阶为n 且等1 a ( t ) ， # _ i | 一 | | | | 一 | | 3 最大度限制条件卜树的极大独立集 詈1 显然，结论对阶为5 礼6 的树成立下面令n 7 假设结论对阶小于n 的树均成立 设丁是高至少有3 层的根树假设z 是丁最底层的叶子，即y ，z 和s 分别是 z 的父亲，祖父，曾祖父为方便起见，我们记是树丁的最大度 对n 8 且为偶数，利用定理2 1 ，结论显然成立 下面假设他足奇数且扎之7 假设丁有一点至少有两片叶子，则利用引理2 6 得到m i ( t ) st l ( n 一1 ) = 2 ( n l ，) t 2 ( n ，) 因此我们假设丁至多有一片叶子 因此令d ( u ) = 2 我们假设z 有j ( 0 歹1 ) 片叶子且z 的子孙有i 个恐 组成下面我们分类讨论 情形_ a ( t n i x ) = 令j = 1 若 f t n - 2 1 ，则利用数学归纳法和定理2 1 ，得到 m i ( t ) = m i ( t n i x ) + m i ( t 一旧】) t 2 ( n 一2 ，a ) + 2 扣1 h ( n 一( 2 i + 2 ) ) = r n 一5 + r n 一2 a 一3 + f 2 a 一2 1 + + r “一5 t 2 ( n ，) 若= f 警1 ，则利用数学归纳法和定理2 1 ，得到 m i ( t ) = m i ( t n i x ) + m i ( t 一b 1 ) h ( n 一2 ) + 2 h h ( n 一( 2 i + 2 ) ) =r n 一3 + r “一5 = i p 1 r n 一1 = t 2 ( n ，) 现在我们假设j = 0 注意到t 的每个点至多有一片叶子若d ( s ) a ，我们 1 9 l 3 最大度限制条件卜树的极大独立集 得到i n - - t 2 a 一- - 1 若d ( s ) = a ，我们得到i n - - 2 2 a + 1 若i n - - 下2 a 一- 1 若a 孚1 ，则利用数学归纳法和定理2 1 ，得到 m i ( t ) = m i ( t 一b 】) + m i ( t 一 】) t 2 ( n 一2 ，) + 2 i - 1 t l ( 佗一( 2 i + 1 ) ) = r n 一5 + n 一2 a 一3 + r 2 a 一2 1 + + r “一5 + r 2 i 一2 t 2 ( n ，) 等号成立当且仅当丁一m 笺t 2 ( n - 2 ，) ，t 一m 皇( i 一1 ) k zu t ( n 一( 2 i + 1 ) ) 和i = 下n - - 2 - i ，即t 星死( 佗，) 若a = 警1 ，则利用数学归纳法和定理2 1 ，得到 m i ( t ) = m i ( t n i x ) + m i ( t 一囟】) t l ( n 一2 ) + 2 i - l t l ( n 一( 2 i + 1 ) ) = r n 一3 + r “一5 + r 2 i 一2 i r n _ 1 + r 吨 r n 一1 t 2 ( n ，) 下面考虑情况i = n - 2 2 z x + l 且d ( s ) = 设，是t 去掉z 以及z 的子孙得到 的图则，鲁t ( 2 a 一2 ) 和( ，) = a 一1 ，即t 见图3 4 因为i = 竺坠2 越，我们 得到t n + 3 我们从n 7 和引理2 1 ，2 6 得到 m i ( t ) = m i ( t 一【伽】) + m i ( t 一 s 】) = r 2 ( a 一2 ) r n 一2 a + l _ lr n 一2 + 1 = r n 一3 上r n 一2 + 1 t 2 ( 他，) 情形2 a ( t n i x ) = 一1 2 0 l 鲁 一 l l 、 3 最大度限制条件卜树的极大独立集 z s叫 i = n - - 2 广a + l a 一2 图3 4 树丁 若j = l ，则利用数学归纳法和定理2 1 ，得到 m i ( t )= m i ( t 一 z 】) + m i ( t 一b 】) t 2 ( n 一2 ，一1 ) + 2 i - 1 h ( n 一2 i 一2 ) = r n 一3 + r n 一2 a 一1 + r 2 a 一4 1 t 2 ( n ，l x ) 若j = o ，则i = 一1 则利用数学归纳法和定理2 1 ，得到 m i ( t ) = m i ( t 一【z 】) + m i ( t 一【耖】) t 2 ( n 一2 ，a 一1 ) + 2 i - x t l ( n 一2 i 一1 ) 7 ”一5 + r n 一2 a 一1 + r 2 a 一4 1 + r n 一5 + r 2 i 一2 t 2 ( n ，) 等号成立当且仅当t n i x 兰7 2 ( 佗一2 ，一1 ) ，且丁一n y 竺( 一2 ) u t ( n 一2 a + 1 ) ，即t 垒( 几，) 证明完毕 2 1 4 树中不包含叶子的极大独立集 文献【1 4 】研究了树中包含叶子的极大独立集的情形，同时w l o c h 给出了树中 包含叶子的极大独立集的最小值与最大值的情况那自然想到树中不包含叶子的 极大独立集的极值及其相应的极图结构 设t 是树对z y ( 丁) ，记l ( x ) 为z 的叶子的集合 定义4 1 点z v ( t ) 且l ( x ) 0 ，则称z 为支持点若| l ( z ) l 2 ，则称z 为强 支持点若i l ( z ) i = 1 ，则称z 为弱支持点 若己是丁的叶子集合，一l 是r 的支持点的集合记m i l ( g ) 是丁包含支持 点集合的极大独立集的个数显然，m i l ( g ) 是t 不包含叶子的极大独立集的个 数 定义4 2 若路p m ( m 2 ) 的两个端点分别连接i ，jo ，j 1 ) 片叶子，称这样的树 为m 一星，记为叼当m = 2 ，我们称之为双星 定义4 3 若路p 3 上的三个点，分别连接i ，j ，s ( i ，歹，s 1 ) 片叶子得到的图，记为 b ( 3 ；i ，j ，s ) 定义4 4 若路只的两端点连接i ，j ( i ，j 1 ) 片叶子，而路的任一内点连接8 ( s 1 ) 片叶子，记为q ( 4 ；i ，j ，s ) 定义4 5 若树丁上的点z 连接d ( x ) 一1 片叶子，则称z 是树丁的插点注意到x 连接d ( x ) 片叶子，当且仅当t 是星且z 是中心 引理4 1 若丁是阶n 3 的树，则包含叶子的极大独立集的极图是路r 下面的引理很清楚，故省略证明 引理4 2 设t 是树，s 是t 的极大独立集若x 一l 且snl ( x ) 0 ，则 l ( x ) s 2 2 4 树中不包含叶子的极大独立集 引理4 3 设丁是树，z 是丁的强支持点对任何l ( z ) cl ( z ) ，m i l ( t ) = m i l ( t l ( z ) ) 引理4 4 设丁是树，s 是丁的极大独立集若snl ( t ) = d ，则一l s 引理4 5 设丁是树若丁有不包含叶子的极大独立集，则任意两个支持点不相邻 引理4 6 设t 是树若丁有不包含叶子的极大独立集，且m i l ( 丁) = p ( p 是素 数) ，则t n - l 】有一个非平凡连通图 4 1 树中不包含叶子的极大独立集的最小值 定理4 1 设t 是阶为n 3 的树则m i l ( t ) = 1 当且仅当丁【- 纠是空图或 t 竺n - l 定理4 2 设t 是阶为n 3 的树则m i l ( t ) = 2 当且仅当丁a r 【一剀包含一个 非平凡的连通图彤1 勘t 1 证明：对t 的任意一个不包含叶子极大独立集s ，应用引理4 4 ，我们有 一己s 注意到，对任意的scv ( t ) 且一l 冬s ，s 是t 中不包含叶子的极大独 立集，当且仅当s 一l 足t 【一纠的极大独立集 若丁【一剀只包含一个非平凡的连通图，k 1 ，t t 1 ，很显然，我们得到 m i l ( t ) = m i ( t n - l ) = 2 相反地，假设m i l ( t ) = 2 ，则m i ( t n 一引) = 2 设于是，的子图，使得 ，y ( 于) 包含孤立点则m i ( t ) = m i ( t ) = m i l ( t ) = 2 从引理4 5 得到，于是 树我们证明了t = k 1 勘t 1 假设于箬k 。山t 1 则于包含路r 从m i ( p 4 ) = 3 ，我们得到m i ( 2 f ) 3 由此得到矛盾 证明完毕 若彳= t ：t 是树且m i ( t ) = 7 ， 定理4 3 设t 是阶为n 3 的树则m i l ( t ) = p ( p 是素数) 当且仅当t 卜驯 足一个非平凡连通图名 2 3 4 树中不包含叶子的极人独立集 当p 是素数，我们可以列举可能出现的各种可能：以= k 1 ，t ，玩= 吃， 以= t 。4 ，b ( 3 ；i ，j ，s ) ) ，蜴= 吃) 但是对合数r ，情况就变得很复杂了对小的 合数，我们得到下面的结果 定理4 4 设丁是阶为几3 的树，则m i l ( t ) = 4 当且仅当丁【一纠仅包含一 个非平凡连通图t l 或两个星图组成 定理4 5 设丁是阶为钆3 的树，则m i l ( t ) = 6 当且仅当t f _ 纠仅包含一 个非平凡图q ( 4 江j ，s ) 或两个k 1 ，t 和吃 4 1 2 树中不包含叶子的极大独立集的最大值 首先我们利用定理逐步得到同阶的不包含叶子的极大独立集的最大值是路， 使得不包含叶子的极大独立集不是逐步下降 定理4 6 设z 是t 的弱支持点且l ( x ) = z 若x 不是插点，则m i l ( t ) m i l ( t 名 ) i y _ u ) j ：记，= t 石) 设庐la n d 彰工分别是t ，不包含叶子的极大独 立集的集族显然，我们得到m i l ( t ) = i 矿l i 和m i l ( r ) = l 矿l l - 对任何 s 乒l ，s 是t 和，不包含叶子的极大独立集，即矿l 冬矿l 定理4 7 设丁阶为n 3 的树若z 是强支持点，z 的叶子点为l ( x ) = z 1 ，z a ，z p ， p 2 设u 是t 插点且v ( 仳) l ( u ) 则m i l ( t ) m i l ( s u b 。，。l ( t 五) ) ) ， 1 i p 证明：利用定理4 6 ，我们得到m i l ( t ) = m i l ( 八 磊) ) 令，= s u b 。，。l ( 丁【乞) ) 令矿l 和矿l 分别是t 和，不包含叶子的极大独立集 显然，我们容易得到m i l ( t ) = i 乒l i 和m i - l ( r ) = i 彰l | 对任意的 s 宄l ，t j 簪s 再则，s 和su u ) 是，中不包含叶子的极大独立集显然，我 们得到了满足条件的结果 定理4 8 设丁是阶为n 5 的树假设t 包含两个子树r 和岛，t ，m 3 ，使得 ( i ) z 是只和p m 的公共端点； ，4 4 树中小包含叶子的极大独立集 ( i i ) ) r 和f i m 的另一个端点在t 中是叶子； ( i i i ) r 和的内部的点的度数在丁中的度为2 则m i l ( t ) m i l ( t 一肌，+ u ) ，其中u 是尸m 的端点，且v = n ( x ) ny ( b ) 证明记，= t 一删+ 删设莎l 和彰l 分别足丁和，的不包含叶子的 极大独立集的集族设s 矿工和( 札) = w 则u 譬s 和w s 显然，s 是， 的独立集下面，我们将s 扩展成，的不包含叶子的极大独立集，根据下面的法 则 规贝u 1 u s 贝0x 硭s ( 1 1 ) 若( z ) 】ns = 国，贝0su z ) 乡t l ( 1 2 ) 若( z ) ) ns 仍，贝us 乡t l 规贝2 v 譬s 令a = ( u ) z ( 2 1 ) 若a s ，贝us 乡t l ( 2 2 ) 若a 隹s ，则su ) 多二l 根据上面的法则，对任意不同的& ，岛乒l 将，扩展成不同的不包含叶 子的极大独立集因此我们得到m i l ( t ) m i l ( t x v + u u ) 证明完毕 从定理4 6 ，4 7 ，4 8 ，我们得到下面的结果 定理4 9 设丁是阶为n 3 树，则m i l ( t ) m i l ( r ) 我们通过上面的定理得到，不包含叶子的极大独立集的极图是路 定理4 1 0 对任何佗4 ，m i l ( r ) = m i l ( r 一2 ) + m i l ( r 一3 ) 4 3 扩展后的树的情形 我们通过扩展，可以得到在丁的不包含叶子的极大独立集 令于一仟意树，t - a d d i t i o n 表示从t 扩展得到的树，通过丁_ n d 于( 础) ( t ) ：有 z y ( 丁) ，使得点x 黏贴到点y y ( 于) ，于是图若于是星，则我们通过这个方法 2 5 4 树中不包含叶子的极大独立集 得到增加星 定理4 1l 设丁是阶为佗3 的树，且于是有且只有一个不包含叶子的极大独立 集的树，则m i l ( n 略( 础) ( 丁) ) = m i l ( t ) 其中z 是t 的任一个支持点，y 是于的 任一支持点 2 6 5 带有较多极大独立集的树 在文献【1 8 】中，j i n 和y a n 等人给出了树的极大独立集个数的第二，三大值为 加深对树的认识，很自然地想到对树的第四，第五大值进行了研究在第二章的预 备知识中，我们分别用t l ( 仃) ，t 2 ( n ) ，t a ( n ) 表示树的第一，第二，第三大值分别用 乃( 礼) ，正( n ) ，乃( n ) 表示树达到第一，第二，第三大值时的图结构 五( n ) = b ( 1 , n - 1 ) , 或b ( 4 ，n 一4 ) ，佗n 兰- - 0 1 ( ( m m 。o d d2 2 ) ) ； a 聆 n 兰0 ( m o d 2 ) 且n 4 n = 8礼= 8 图5 1 ：树死( n ) r = 8 ) i n 7 拿r 声凰龃 弋= n = 1 0n = l o 图5 2 ：树乃( 佗) 川= r n _ 2 ；+ 1 扎n - - 三0 1 ( ( m m o d 2 ) o d 2 ) ； 5 带有较多极大独立集的树 t ：c 礼，= it n _ 2 。+ 1 ，礼n 兰- - - - o 。( m m 。o d d2 2 ，) ： 以垆7 n f2 n - - - - 0 。( 删m o d2 ) ； 定理5 1 设t 是阶为n 的树若t 箬互( 礼) ，i = 1 ，2 ，3 ，则m i ( t ) 4 ( n ) ，其中 纵垆 篆鼍n - - 0 ( 删m o d 2 ) ； 等号成立当且仅当t 垡乃( 几) ，乃( n ) 见图5 3 一一于 图5 3 ：树乃( n ) 证明：我们对树的阶佗进行数学归纳对于佗1 1 容易验证结论成立令 几1 2 ，假设结论对阶小于n 的树均成立假设t 是至少有2 层的根树设x 是 在根树t 的最低层的点，z ，y 分别是z 的祖父与父亲下面对n 进行分类讨论 假设在丁中有点q 至少有两片叶子，记为u ， 假设t u 竺五( n 一1 ) ，则根据 五( n 一1 ) 的结构，得到t 兰已( n ) 因此我们假设t u 喾正( n 一1 ) ，由此得到 m i ( t ) = m i ( t u ) t 2 ( n 一1 ) = 1 , n - - 2 + 1 r n + 1 由此假设丁中的点至多有一片叶子，从而d ( y ) = 2 下面对树的阶分两种情形讨论 情形1 n 三0 ( m o d2 ) 5 带有较多极大独立集的树 b a uv 他兰l ( m o d 2 1 e d 死兰0 ( r o o d 2 1 图5 4 ：树正( n 一2 ) 若丁一n i x 】鲁乃( n 一2 ) ，见图5 4 我们得到z a ，b ，c ，d ，e 若z = a 。由于 丁( n ) 箬冗( n ) ，贝0d