（应用数学专业论文）bc树性质的研究.pdf

中文摘要 摘要 本文主要研究了b c 树的性质给出了几类特殊b c 树的b c 子树的计数及其 性质；提出了w i e n e r - 1 ，w i e n e r - 2 指标和w i e n e r - 1 ，w i e n e r - 2 距离的概念并给出了其 在树上和b c 树上的性质 首先给出了星形b c 树和路径b c 树的b c 子树的计数，对于路径b c 树。分析 了经过任给顶点的b c 子树的计数问题；由星形b c 树和可接受子树残留构型的概 念进而提出了刀1 个分支的k 扩星形b c 树的概念和可接受b c 子树残留构型的概 念；同时也给出了k 扩星形b c 树的b c 子树数，可接受b c 子树残留构型数，与原 叶相关的b c 子树数以及与每一层上顶点相关的b c 子树数 结合毛虫树和b c 树的概念提出了毛虫b c 树的概念研究了毛虫b c 树的b c 子树数，与原叶相关的b c 子树数，与区域相关的b c 子树数；并且给出了毛虫b c 树的两个特性：与直径相关的一个性质以及包含直径端点的b c 子树数与对称区域 叶子数间的关系 对应于w i e n e r 指标的概念和性质，本文提出w i e n e r - 1 ，w i e n e r - 2 指标和 w i e n e r - 1 ，w i e n e r - 2 距离的概念，并且分别给出了树上的w i e n e r - 1 ，w i e n e r - 2 距离和 w i e n e r - 1 ，w i e n e r - 2 指标的特性；并且我们也给出了一般b c 树、星形b c 树、路径 b c 树、k 扩星形b c 树、毛虫b c 树的w i e n e r - 1 指标和w i e n e r - 2 指标的关系 关键词：b c 树；露扩星形树；毛虫树；树的分裂；w i e n e r - 指标；w i e n e r - 距离 英文摘要 a b s t r a c t i nt h i sp a p e r , w es t u d yt h ep r o p e r t i e so fb ct r e e ，g i v eo u tt h ee n u m e r a t i o no fs u b b ct r e ea n dp r o p e r t i e so fs o m ek i n d so fs p e c i a lb ct r e e ；w ep r o p o s et h ec o n c e p t so f w i e n e r - i ，w i e n e r - 2i n d e xa n dw i e n e r - 1 ，w i e n e r - 2d i s t a n c e ，a n dg i v eo u ti t sp r o p e r t i e s o nt h et r e ea n dt h eb ct r e er e s p e c t i v e l y f i r s t l y , w eg i v eo u tt h ee n u m e r a t i o no fs u bb ct r e e so fs t a rb ct r e ea n dp a t hb c t r e e ；w ea n a l y s i st h ee n u m e r a t i o no fs u bb ct r e e sp a s s i n gt h r o u g ha n yg i v e nv e r t e xo f p a t hb ct r e e ；c o n t r a s tt h ec o n c e p t so fs t a rb ct r e ea n da c c e p t a b l es u b t r e er e s i d u a l c o n f i g u r a t i o n , w ep r o p o s et h ec o n c e p t so fke x t e n d e ds t a rb ct r e e 、们n l 刀一1b r a n c h e s a n d a c c e p t a b l es u bb ct r e er e s i d u a lc o n f i g u r a t i o n , w eg i v eo u tt h en u m b e ro fs u bb c t r e e s ，a c c e p t a b l es u bb ct r e er e s i d u a lc o n f i g u r a t i o n , s u bb c t r e e sr e l a t i n gw i mo r i g i n a l l e a f , s u bb ct r e e sr e l a t i n gw i t he v e r yl a y e r 舔w e l l c o m b i n i n gt h ec o n c e p t so fc a t e r p i l l a rt r e ea n db ct r e e , w eg i v eo u tt h ec o n c e p to f c a t e r p i l l a rb ct r e e ，a n dw es t u d yt h en u m b e ro fs u bb ct r e e s ，s u bb ct r e e sr e l 撕n g 、撕t l l o r i g i n a ll e a f , s u bb ct r e e sr e l a t i n gw i 廿le v e r yz o n e , a n dg i v eo u tt w os p e c i a lp r o p e r t i e s o fc a t e r p i l l a rb ct r e e ：o n ep r o p e r t yi sr e l a t e dw i t ht h ed i a m e t e ra n dt h eo t h e ri st h e r e l a t i o n s h i pb e t w e e nt h en u m b e ro fs u bb ct r e e sc o n t a i n i n gt h ee n d so fd i a m e t e ra n d t h es y m m e t r i cz o n e c o r r e s p o n d i n gt ot h ec o n c e p to fw i e n e ri n d e x , i nt h el a s to ft h ep a p e r , w ep r o p o s e t h ec o n c e p t so fw i e n e r - 1 ，w i e n e r - 2i n d e xa n dw i e n e r - 1 ，w i e n e r - 2d i s t a n c e , a n dg i v e o u tn l e i rp r o p e r t i e so nt h et r e e ，n e x t ，w eg i v eo u tt h er e a l a t i o n s h i pb e t w e e nw i e n e r - i i n d e xa n dw i e n e r - 2i n d e xo fg e n e r a lb ct r e e ，s t a rb ct r e e ，p a t hb ct r e e ，ke x t e n d e ds t a r b ct r e e 、c a t e r p i l l a rb ct r e e k e y w o r d s ：b ct r e e ；ke x t e n d e ds t a rt r e e ；c a t e r p i l l a e rt r e e ；s p l i t t i n go ft r e e ； w i e n e r - i n d e x ；w i e n e r - d i s t a n c e 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文“旦挝性厦的班究”除论文中已经注明引用的内容外，对 论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明本论文中不 包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果 本声明的法律责任由本人承担 论文作者签名：杨【矽夕矿年夕月7 碉 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法 ，同意大连海事大学保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅本人授权大连海事大学可以将本学 位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描 等复制手段保存和汇编学位论文 保密口，在年解密后适用本授权书 本学位论文属于：保密口 不保密口( 请在以上方框内打“4 一) 论文作者签名：锄需导师签名：办十秒爿欠 日期：年3 月7 日 b c 树性质的研究 第一章绪论 1 1 引言 树的术语起源于植物学和家谱学早在18 5 7 年，英国数学家亚瑟凯莱( a r t h u r c a y l e r , 1 8 2 1 - 1 8 9 5 ) 就发现了树，当时他正在试图列举形为q 棚的化合物的同分 异构体树具有广泛的应用，特别是在计算机科学、管理科学和工程应用中，例如 用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算 机网络，用树模拟一系列决策完成的过程，独立的基尔霍夫方程式的数目，选择独 立方程式的方法以及网络函数的拓扑公式都是纯以树的概念来表示的 在各种各样的图中，树是一类简单而又十分重要的图类，不仅仅因为它在许 多不同领域有广泛的应用，而且还在于图论本身在图论中，许多悬而未解的问题 往往首先从树这一类图入手，许多问题对于一般图未能解决或没有简便的方法， 而对于树则能够完满解决且方法较为简便因此对树的研究意义非常重大，本文 将着重研究一类特殊的树b c 树的性质 1 2b c 树的研究现状 如果一棵树是2 可染色的，并且所有的叶子顶点都具有相同的颜色，那么它就 是一棵b c 树b c 树是由著名的图论学家h a r a r y 和p l u m m e t 于1 9 6 7 年在文献【l 】中 提出的，是h a r a r y 和p l u m m e r 毛h 研究图的肛核的过程中发现的b c 树有诸多特殊 性质：一棵树是b c 树当且仅当它的搏核等于它本身；b c 树的最小顶点覆盖是唯一 的，且不包含任何一片叶子顶点；b c 树的任两片叶子之间的距离都是偶数等等 h a r a r y 和p r i n s 研究了图的块割点树，证明了一棵树是b c 树当且仅当它是 某个连通图的块割点树，并且利用p 6 1 y a 计数定律给出了刀个顶点的所有不同构的 b c 树个数【2 】；m k r t c h y a n 5 1 证明了b c 树存在一个最大且适当的部分m 1 染色，使得 染色为0 的那些边刚好形成一个最大匹配等由于b c 树的特殊性质。对于特殊b c 树的研究，b c 树的b c 子树计数、p 顶点b c 树的存在性，b c 树上类似w i e n e r 指 标的研究，以及b c 树的性质对应其在化学等领域的应用等等都变得非常的有意 义 绪论 1 3 本文的研究内容与安排 本文主要研究了图论中一类简单而又十分重要的图b c 树，给出了几类特殊 b c 树的b c 子树的计数及其性质；提出了w i e n e r - 1 ，w i e n e r - 2 指标和w i e n e r - 1 ， w i e n e r - 2 距离的概念并给出了其在树上和b c 树上的性质： 第l 章，绪论介绍了b c 树的研究现状，并给出本文的主要内容安排 第2 章，给出了星形b c 树和路径b c 树的b c 子树的计数，对于路径b c 树，分 析了经过任给顶点的b c 子树的计数问题 第3 章提出刀1 个分支的k 扩星形b c 树的概念和可接受b c 子树残留构型 的概念，同时也给出了k 扩星形b c 树的b c 子树数，可接受b c 子树残留构型数， 与原叶相关的b c 子树数以及与每一层上顶点相关的b c 子树数 第4 章，研究了毛虫b c 树的b c 子树数，与原叶相关的b c 子树数，与区域相 关的b c 子树数；并且给出了毛虫b c 树的两个特性：与直径相关的一个性质以及 包含直径端点的b c 子树数与对称区域叶子数间的关系 第5 章，提出w i e n e r - 1 ，w i e n e r - 2 指标和w i e n e r - 1 ，w i e n e r - 2 距离的概念，并且 分别给出了树上的w i e n e r - 1 ，w i e n e r - 2 距离和w i e n e r - i ，w i e n e r - 2 指标的特性；并且 我们也给出了一般b c 树、星形b c 树、路径b c 树、k 扩星形b c 树、毛虫b c 树的w i e n e r - 1 指标和w i e n e r - 2 指标的关系 第6 章，结论对本文的内容进行了总结，指出了研究工作中需要进一步研究 的问题并对未来的工作进行了展望 b c 树性质的研究 第二章两类b c 树的b c 子树的计数 计数是组合数学中一个很重要的研究领域，也是图论学家非常喜欢的一个研 究课题关于图的计数有各种各样的方法，有的是从p 6 1 y a 计数定律出发，有的是 从生成函数出发y a n 和y e h 6 采用生成函数的方法研究了树的子树的计数问题，借 助于这种思想，本章也将用生成函数的方法来研究b c 树的b c 子树的计数，并给 出路径b c 树、星形b c 树的b c 子树的个数；对于一般b c 树给出了其所含b c 子树个数的一个上界 2 1 符号和相关引理 假定t = ( 矿( r ) ，e f t ) ；f ，g ) 为一棵加权树，顶点集矿( 乃= “，v 2 ，心) ，边集 e ( r ) = e i ，吃，气一。) ，顶点权函数厂：y ( r ) 一尺，在本文中尺也可以是颜色的集 合，即厂电可认为是顶点的染色函数，边权函数g ：e ( t ) 专r 记s ( r ) 为树r 的所有 子树的集合，对树r 的任意两个顶点k 和v ，记s ( 疋v f ) ( s ( r ；k ，v ，) ) 为包含顶点 ( k 和，) 的子树的集合对于树r 的子树五，定义石的权重h 石) 为石中的所有 顶点权和边的权重的乘积加权树丁的子树的生成函数记为f ( 疋，g ) 就是丁的所 有子树的权重的和，即f ( t ；f ，g ) = 五咧nw ( 五) ，同理记包含顶点k 的子树的生 成函数为v ( r ；f ，g _ ) = 石鲤r 辑) w ( 互) ；记包含顶点m 和_ 的子树的生成函数为 f ( r ；f ，g ，m ，v j ) 2 秘h ) 以石) 为便于描述，若r 为b c 树，记r 的b c 子树的生成函数为吒( r ；，g ) ，同时 记r ( t ) = 民( r ；1 ，1 ) 为b c 树r 的b c 子树的个数，r ( t ，m ) = 瓦( 丁；1 ，l ，m ) ( 疋( r ；f ，g ，m ) 为包含顶点m 的b c 子树的生成函数) 为r 的包含顶点u 的b c 子 树的个数，7 ( 丁，吩，巧) = 气( r ；l ，l ，_ ，) ( 民( r ；f ，g ，v f ，) 为包含顶点m 和的b c 子树的生成函数) 为包含顶点m 和的b c 子树的个数 定义2 1 设r = ( 矿( r ) ，e ( r ) ；f ，g ) 为n 1 个顶点的加权树，e = ( “，) e ( r ) ， 且露( “) = l 记巧= ( y ( 巧) 占( 巧) ；l - ，酊) ，y ( r 2 ) = y ( f ) 、如 ，e ( 巧) = e ( z ) e ) ， 其中 两类b c 树的b c 子树的计数 疗c k ，_ 关z ；f 材g p + d ，v 屹s - m v y ，c k 矿c 巧， 酝( p ) = g ( e ) ( e e ( 巧) ) 为了后面证明的需要引入以下引理： 引理2 1 qr 和巧的定义同上则丁的子树的生成函数等于巧的子树的生成 函数与顶点u 的权重的和，即 ，( 丁；f ，g ) = ，( 巧；f ，或) + ( 甜) 引理2 2 【6 jr 和巧的定义同上那么对任意顶点m “，树t 的含顶点k 的子 树的生成函数与巧的含顶点m 的子树的生成函数相等即 f q jl ，g j v a = f q ：j l ：，或j 。 引理2 3 【6 】r , n r 。- 的定义同上对任意两个不同的顶点m ，v ，且k “，v ，“， 则t 的含顶点k ，吩的子树的生成函数与巧的含顶点m ，巧的子树的生成函数相 等即 f ( 乃厂，g ；m ，) = f ( 巧；f ，甄；k ，匕) 引理2 4 刀路径树只有c “2 个子树，比任一个以顶点树所含的子树都少，星形 树墨，有2 ”+ n - 1 个子树，比任一个力顶点树所含的子树都多 同时我们再引入三个计算加权树t = ( 矿( r ) ，e ( d ；厂g ) 的子树的生成函数，含 任给一个顶点m 的子树的生成函数，含任给两个顶点，v srv , 吩的子树的生成 函数，即f ( t ；f ，g ) ，f ( t ；f ，g ；咔) ，f ( 丁； g ；v i ，0 ) 的图论的计算算法 算法2 1 1 6 令丁= ( y ( 丁) ，e ( 丁) ；f ，g ) 是一加权树 s t e p1 初始化定义：p ( 匕) = ( 屹) v 匕y ( d ，n = 0 s t e p 2 收缩 ( a ) 选择一个悬挂顶点“，并且记e = ( “，) 为悬挂边 秭用新的权值p ( v ) ( p 似) g ( 力+ 1 ) 作为，的权值，替代旧的权值p ( v ) ( c ) 用+ p ( u ) 替代m ( d ) 消除顶点“和边巴 s t e p3 如果，是剩下的唯一个顶点，转向s t e p4 否则转向s t e p2 b c 树性质的研究 s t e p 4 输出f ( r ；f ，g ) = p ( v ) + n 算法2 2 嗍令t = ( y ( 丁) ，e ( 丁) ；f ，g ) 是一颗加权树，m 为r 的一个固定顶点 s t e pl 初始化定义：p ( k ) = 厂( k ) ，v 屹矿( 刀 s t e p2 收缩 ( a ) 选择一个悬挂顶点u k ，并且记e = ( “，) 为悬挂边 ( b ) 用新的权值p ( v ) ( p ( “) g ( p ) + 1 ) 作为1 ，的权值，替代旧的权值p ( v ) ( c ) 消除顶点u 和边e s t e p3 如果 ，是剩下的唯的一个顶点m ，转向s t e p4 否则转向s t e p2 s t e p 4 辅i 出f ( r ；f ，g ；v f ) = p ( v ) 算法2 3 【6 】令r = ( y ( 丁) ，e ( 丁) ；，g ) 是一颗加权树，坼和v j 为t 的两个不同的 顶点 s t e pl 初始化定义：p ( l ) = ( v j ) ，v 屹y ( n s t e p2 如果丁是一条路径，并且k 和 ，是两个悬挂顶点，转向s t e p5 否则转 向s t e p3 s t e p3 收缩 ( a ) 选择一个悬挂顶点“并且“巧，“ ，并且记p = ( “，1 ，) 为悬挂边 ( b ) 用新的权值p ( ，) ( p ) g ( e ) + 1 ) 作为，的权值，替代旧的权值p ( v ) ( c ) 消除顶点“和边e s t e p4 如果不存在这样的顶点屿使得“满足s t e p3 中的条件( a ) ，转向s t e p 5 否则转向s t e p 3 s t e p5 输出f ( r ；厂，g ；v i ，o ) = 兀惺p ( 一p ( v ) 兀砌( 一g ( p ) ， _ 为r 的连接顶 点k 和，的唯一的那条路径 2 2 星形b c 树的b c 子树数 s z e k e l y 和w a n g 在文献 7 中研究了树的子树，并给出了一般树的子树个数的 大小关系，下面将给出b c 树的b c 子树个数的大小关系 定理2 1 n 顶点星形b c 树k 十。有2 ”一刀个b c 子树，比任何一个n 顶点b c 树所含的b c 子树都多 证明：对星形b c 树赋权值如图2 1 ，项点v i 赋权值薯，边赋权值都为l ， 两类b c 树的b c 子树的计数 由引理2 1 知 v l 卜川 图2 。1 星行b c 树k 加t f i g 2 1s t a rb c - t r e ek i t f c k i 扩i ；厂，1 ) = 吒( 1 + 而) ( 1 + 屯) ( 1 + 矗一i ) + 毛+ 而+ + 毛一l ( 2 1 ) 又因为b c 树可以2 染色，故可令毛o = l ，2 ，n - 1 ) 都为颜色为颜色m 上 式为 f ( k i , n - i ；f ，1 ) = j ，( 1 + 工) “+ ( ，l 1 ) x = c ：一l 矽+ c ：l 工2 y + + ，一y + ( n - 1 ) x + y ( 2 2 ) 由b c 树的性质可知，b c 树二染色后，两色顶点数不等，因此， 瓦( 墨州；厂，1 ) - - l x 2 y + i 办+ + 础y ( 2 3 ) 令x = l ，y = l 带入式( 2 3 ) ，即得刁( 墨j 一。) = 2 ”。一刀 设r 为任一刀顶点b c 树，贝l j r ( t ) e ( t ) - ( 2 n - 1 ) ，其中( 乃为z 的所有子树 个数( 因为r 的九个顶点和刀一l 条边是子树但不是b c 树) 由引理2 4 知 ( n 2 ”1 + 刀一l ，所以 r ( t ) 2 ”一1 + 力一l 一( 2 n 一1 ) = 2 ”一1 + 刀一1 2 n + 1 = 2 ”1 一刀 等号成立当且仅当r 为星形b c 树墨川，故定理得证 利用引理2 2 ，结合b c 树的性质，与定理2 1 的证明类似可得推论2 1 推论2 1 星形b c 树k 加中含顶点k “= l ，2 ，一一1 ) 的b c 子树的个数为 2 ”一1 结合求经过任意两个顶点的子树的生成函数的算法2 3 ，利用引理2 3 以及b c b c 树性质的研究 树的性质，同理可以获得推论2 2 推论2 2 星形b c 树五俨l 中含顶点v l , v s 的b c 子树的个数7 7 ( k 扩l ，哆，v j ) = 2 ”3 2 3 路径b c 树的b c 子树数 定理2 2 令= ( h ) ，目) ；厂，g ) 为加权路径b c 树，以e ) = “i i = i ，2 ，刀) 互( ) = 如= ( m ，。) li = l ，2 ，以- 1 ，只的边权赋值都为1 ，顶点权赋值为：i 为奇( 偶) 时，顶点h 赋值为玉( 咒) 则 眦；川，= 喜喜 生学c 一嘞，+ t l + ( - l yc 一) ， 证明：对拧进行归纳证明n = 3 和n = 5 显然成立假设式( 2 4 ) 对于刀2 是成立的 ( 因为是路径b c 树，故顶点个数必须为奇) ，而路径b c 树只一：与只相比，长度为 2 1 ( 1 = 1 ，2 ，( 力一3 ) 2 ) 的b c 子树都少了2 个，长度为疗一1 的b c 子树少了一个，结 合子树的生成函数的算法2 1 ，以及路径b c 树的特性得： 喜薯 生学c 砒而一t 1 + ( - 1 ) 1c 脚一r + n - 3 【( 1 2 j 稚2 ，只一2 “l x l l _ 2 1 + 2 - 一2 以一1 ) + ( 趔儿划+ 1 一拼2 只- 2 1 + 3 ) o l 毛) 卜 x i y 声3 y 4 j 铲2 y n - i x r = 喜蓍 生c 挑丙一生笋c 幽讹) = 民( 只；厂，1 ) 上式得证 2 3 1b c 树的分裂 定理2 3 路径b c 树只有o 1 ) 2 4 个b c 子树，比任何一个一项点b c 树所含 的b c 子树都少 证明：对路径b c 树只2 染色，令所有的玉u 为奇) 为颜色毛所有的j ，( ，为偶) 为颜色y ，得 堕一一 桃；圳= 喜i 半x t + i y + 半1 f = ll j 两类b c 树的b c 子树的计数 故 n - 1 2 7 7 ( 只) = ( n - 2 1 ) = ( n - 1 ) 2 4 ，= l 假设对于顶点数小于刀的b c 树定理2 3 的第二部分结论成立对于疗个顶点 的b c 树正若r 为星形b c 树则结论显然成立，否则，我们总可以找到一个分裂 顶点如图2 2 ) ，使得分裂之后的两个树为r 和r 都为b c 树kt 。为含p ( p 3 ) 个 顶点的星形b c 树，由归纳假设可知 r l ( t 7 ) ( 以一p + l 1 ) 2 4 = ( 行一p ) 2 4 ，刁( 丁”) ( p 一1 ) 2 4 b c 树7 b c 树硫顶点 了蕤r b c 树rb c 树r 图2 2b c 树2 的分裂 f i g 2 2s p l i t i n go fb c t r e et ( 1 ) 若p = 3 ，则b c 树t 中的除顶点y 之外有刀3 个顶点，每个顶点到顶点， 都有一条唯一的路径若路径长度为偶，则该偶路径再并上b c 树r 即为一个新的 b c 子树；若路径长度为奇，则这条路径再并上边( ，u ) 也是b c 树的一个b c 子树， 故r 和p 结合形成的b c 子树个数大于等于n 3 所以 r r t ) - ( n 一3 ) 2 4 + ( 3 一1 ) 2 4 + 刀一3 = ( 刀一1 ) 2 4 ( 2 ) 若p 3 ，因为b c 树r 中有n - p + 1 个顶点，其中至少有伽一p ) 2 个顶点到 顶点1 ，的距离长度为偶，b c 树r 中含边( ，“) 的b c 子树至少有p - 1 个而，中的 到顶点，的距离为偶的至少伽一p ) 2 条路径中的每条再并上r 中的p l 中的每个 b c 子树都会产生一个新的b c 子树，故r 和p 结合生成的b c 子树个数大于等于 ( 刀一p ) ( p 一1 ) 2 ，所以 ，7 ( 丁) ( n - p ) 2 4 + ( p 1 ) 2 4 + ( 一一p ) ( p 一1 ) 2 = ( 万一1 ) 2 4 定理2 3 第二部分结论成立 结合定理2 3 及b c 树的性质很容易得到 b c 树性质的研究 推论2 3 奇长路径树只伽为偶) 含有0 2 2 n ) 4 个b c 子树 2 3 2 路径b c 树中经过给定顶点的b c 子树数 对于路径b c 树o 为奇) ，对于任给顶点k v ( 只x i = l ，2 ，疗) ，可以求出过顶 点屹的b c 子树的个数刁( 乞，h ) ，以及过任意两个顶点l 和y ，的b c 子树的个数 玎( 只，u ，v j ) ，其方法是类似的在此给出7 7 ( 只，u ) o = l ，2 ，1 ) ，并且给出经过顶点k 的长度为2 l ( 1 = l ，2 ，( 刀一1 ) 2 ) 的b c 子树的个数由路径b c 树的特点可知： ( 月一n ) 2 7 7 ( 只，坼) = 口( 只，畸，2 0 = l 其中口( 只，v j ，2 1 ) 为经过顶点_ 的长度为2 ，的b c 子树的个数首先求经过顶点睢的 子树的生成函数，对顶点和边分别赋权值为1 和x 利用算法2 2 求出f ( 只；，g ，v ) ， 并将顶点和边权代入生成函数，得到式( 2 5 ) ! 焚一 。 ! = | 姿 ，( ；f ，g ，k ) = 【( ( x + 1 ) x + 1 ) x + 1 】工+ 1 】工+ l 】【( ( z + 1 ) j + 1 ) z + l 】工+ l p + 1 】 = ( 一。+ ，2 + ，3 + + x + 1 ) ( 工州+ x 卜卜1 + + z + 1 ) ( 2 5 ) = 石”一1 + x ”2 + 工”一3 + + 一+ ，一+ x ”一2 + ，一3 + + 一一1 + 一一2 + 妒q + 。一+ 0 _ + 0 2 + 0 3 + + 妒一i + 矿一一l + ，工+ l 通过计算可知经过顶点k 和屹+ h 的长度为2 l ( 1 - - - 1 ，2 ，锄一1 ) 2 ) 的b c 子树数目 是相同的对于顶点叶，可以很容易得知口( 只，v i ，2 0 = l ( ，= 1 ，2 ，b 一1 ) 2 ) ，故 7 7 ( 只，m ) = ( n - - 1 ) 2 利用式( 2 5 ) 或求( 2 6 ) 不等式组整数解的个数都可以求出口( 只，b ，2 1 ) ( ，= l ，2 ，伽- 1 ) 2 ) f n x + 1 f 1 l 工f ( 2 6 ) ( 1 ) f 为奇且3 f ( n + 1 ) 2 时， 口( 只，m ，2 0 = 2 1 + 1 ( 1 = l ，2 ，( i - 3 ) 2 ) ， 口( 只，m ，2 0 = “，= ( 】 - 1 ) 2 ，1 ( i - 1 ) + 2 ) 2 ，( 刀一，) 2 ) ， 口( 只，m ，2 1 ) = 刀一2 1 ( 1 = ( 万一i + 2 ) 2 ，( n - i + 4 ) 2 ，( n - 1 ) 2 ) ， ，7 ( 只，v f ) = ( i ( n + l f ) 一1 ) 2 ， ( 2 ) f 为偶且2 f ( n - 1 ) 2 时， 两类b c 树的b c 子树的计数 口( 只，m ，2 1 ) = 2 1 + 1 ( 1 = 1 ，2 ，o 一2 ) 2 ) 口( ，v i ，2 1 ) = i ( 1 = i 2 ，( i + 2 ) 2 ，( n - i - 1 ) 2 ) 口( 只，u ，2 1 ) = n - 2 1 ( 1 = ( n - i + 1 ) 2 ，( n - i + 3 ) 2 ，( n - 1 ) 2 ) 7 7 ( 只，m ) = ( i ( n + 1 - 0 - 2 ) 2 并且通过对表2 1 表2 2 的观察可得： 。 ( 1 ) 刁( 只，) 随下标i 的增大而增大，在卢( n + 1 ) 2 时达到最大，其值为 ( 以2 + 2 n 一3 ) 8 ( n = 4 k + 1 ) 或( 刀2 + 2 n 一7 ) 8 ( n = 4 k + 3 ) ，然后又对称的逐渐减小 ( 2 ) 过顶点uo = l ，2 ，j 1 ) 的偶长度抛树数目个数关于长度为( 刀一1 ) 2 ( 甩= 4 k + 1 ) ，( n - - 3 ) 2 和o + 1 ) 2 ( 刀= 4 尼+ 3 ) 所在的列对称 给出经过顶点m 的长度为2 l ( 1 = 1 ，2 ，妇一1 ) 2 ) 的b c 子树的个数的具体取值情 况见表2 1 和表2 2 ，因为行为奇数，为了便于描述将其分为力= 4 k + l 和行= 4 k + 3 两种情况进行讨论 对一般b c 树的b c 子树个数计算时，先对其进行2 染色，由b c 树的性质可 知其2 染色后，它的树权的两种颜色的幂次一定不相等，故去掉f ( t ；f ，g ) 中那些 单独幂次的和幂次相等的项之后，再令x = l ，y = l ，得到的那个数值即为b c 树的b c 子树个数的上界，但这个上界并不是精确的上界，因为颜色幂次不相等的树不一 定是b c 树，故如何从生成函数这个角度实现一般b c 树的b c 子树个数的精确计 算仍是一个需要深入研究的方向 2 4 小结 本章用生成函数的方法来研究了b c 树的b c 子树的计数问题，得出万顶点星 形( 路径) b c 树的b c 子树比任一个刀顶点b c 树所含的b c 子树都多( 少) ，以及路 径b c 树和星形b c 树所含的b c 子树数的精确值；对于路径b c 树，分析了经过任 给顶点的b c 子树的计数问题，也给出了相应的b c 子树数的精确值；对于一般b c 树给出了其所含b c 子树个数的一个上界 对一般b c 树的生成函数的研究意义非常重大，如果能求出一般b c 树的含某 个顶点且满足某种性质的子树的个数，则一般b c 树的b c 子树的计数就能够精确 求出，目前正在作这方面的研究此外对特殊b c 树的研究以及b c 树上的距离， b c 树性质的研究 b c 树与选址问题以及树的b c 子树的计数都将是一个深入研究的方向 n一 气 、 一 小 n 三卜 卜。-一 _ _ c 一 茸 一 一 + 、_ ， t+ + n t 1 套 一一 t _ n nnn 譬 n 一 n + n - n i - 譬 一 + 墨 拉 i 最 譬二 n 最 。一 v 一 - 二墨 i f 震 甘 譬 霉二 n寸 n 斗 n、叶 譬 一 +一 小 n寸 叠 n 小 n、 甘 n n寸 曩 扫寸 采 棠n 一 、一 一 h 覃 _ 二穴 n叶n n - - 一 n 口n、 寸 h 寸n 寸 - n n n ，- 、，、 墨避一 一 橱墨 芝 农最 + -v 少 肾 l ， 一志寸i譬口qii参一n一+v；n一雌一一f时一f它_田一n一一+鼍一；n一o一一。譬一；n一讨，) 一，zi时一q-oo等季一n口一 一n_+譬一；nh o一一，时一夸隧一n一一+譬v；n一on一一譬一：n一o，)文j时一苦_志寸。譬hn秣 籁砖g 霹m u窨霉u粼陵 。n一 ，- 、 一 了 | 一 争 一 f * h- 小 c譬 鼍 一 、一一 一 + 鼍 套 一 一 n 一 nnf _ 1nn n、 nn + n、 -_ n n t _- 置 ：孽 i 震n 柠 n 譬 ：r 一 n v i 墨 i l 最 寸 譬 n n 寸 夺 nn叶 小 ! 卜 n、 寸 小 n、寸 - 盛 妇寸 r n 采 一 n v 一 n 摹 n 二最 n寸nn 一 、 q_- n 、 口nn寸 hh卜 n、 寸 ni v 、 nn nn nn f 、 ，、，- 、 耄形 一一 一 靛匿 一 状状+ ，- v y 爵 一 一 鲁 n土寸i壑_。_事一n一一+譬一；一_o_一，时一f日_h时n、_+譬一：；ni_o一一_譬_)；n1l oi)文，时v尊-o研p【季nncrbp n(一+5；n一o，)，时一套隧n(一+s；n。一o一(一。s；。n一o，)，时胃譬n土甘冬nz 恹摩星峰趟窭u b c 树性质的研究 第三章k 扩星形b c 树相关b c 子树数 k n u d s e n 在文献 8 】中为限定他的算法的时间复杂度，提出了可接受残留构型 这样一个数因子，即树的包含至少一片叶子的子树的个数，并且他估计了所有二 叉树可接受残留构型的最大值；s z e k e l y 和w a n g 7 等证明了在所有二叉树中好二又 树具有最大的可接受残留构型，并给出了玎叶二叉树可接受残留构型最大值的计 算公式本章中，我们提出可接受b c 子树残留构型的概念和以1 个分支的k 扩星 形b c 树的概念，并对k 扩星形b c 树的相关b c 子树数进行研究 3 1 相关概念和定义 如果一棵树是由星形树k 。扩。出发，每条边都再往外延伸k 倍的距离而形成的， 则称这样的树为刀1 个分支的k 扩星形树，记为k ! ；把顶点度为刀1 的那个顶点 定义为根节点，把距离根节点的距离定义为该顶点的层数，由此可知，当k = - i 时即 为星形树，同时规定k 的叶子节点为原叶其余未定义的概念和符号延用第二 章中的记法 3 2k 扩星形b c 树的b c 子树数 第二章中用生成函数解决了星形b c 树和路径b c 树的b c 子树的计数，下面 给出k 的b c 子树数 定理3 1 记叩( k 乙) 为七扩星形树k i m i 的b c 子树数，则 玎( 吃) = ( k - 1 ) 2 ( n - 1 ) 4+ ( k - l x 2 n - i - 1 ) q ( k + l x 2 n - l - n ) 2 t e c t 。 - z - i ( 芝( 点卑书膏- i 一+ 釜( 土专量) 一) 七为奇数， 堡二三鲁基业+ 主垡兰亏业+ 2 芝i ( 圭( 上等) 川- ，) 七为偶数 证明：设k i 的根节点为v ( 见图3 1 ) ，首先从总体上对k 的b c 子树进行 分类：包含根节点 ，的b c 子树和不包含，的b c 子树 当k 为奇( 偶) 数时： ( 1 ) 不含根节点，的b c 子树： 不含 ，的每个分支都刚好是一个路径b c 树，由第二章的定理2 3 ( 推论2 3 ) 可 知每个分支所含b c 子树个数为( k - 1 ) 2 4 ( ( 七2 - 2 k ) 4 ) ，因k i t 一有珈1 个分支，故 不含，的b c 子树的个数为( k - 1 ) 2 0 1 ) 4 ( ( k 2 - 2 k ) ( n 一1 ) 4 ) 后扩星形b c 树相关b c 子树数 图3 1 刀。1 个分支的j | 扩星形树k 乙 f i g 3 1 七e x t e n d e ds t a rb c - t r e ew i t h 疗- 1b r a n c h e s ( 2 ) 含根节点，的b c 子树： 当含根节点v 且叶子全在第l ( = 1 ，2 ，问层时，其b c 子树个数为2 一一刀( 当， 为奇时) ，或为2 俨1 1 ( 当，为偶时) ，故k 为奇( 偶) 数时共有b c 子树个数 ( k - l x z 2 n - i - 1 ) - i ( k + l x 2 z n - l - n ) ( k ( 2 n - 1 - 1 ) 2i - k ( 2 2 1 - n ) ) 当含根节点，且叶子所在的层数不都相i 司，但层数的奇偶性都相同时，其b c n - 2譬n - 2牟 子树个数为：k 为奇数时为q 一。( ( 半) 肛1 _ 7 ) ( 一，( ( 半) ”h ) ) ；k 为 偶数时为q 一，( ( 竽) 卜h ) ( 一。( ( 竽) ”卜7 ) ) 1 = 1 w = li = l - = i 所以，k 为奇( 偶) 数时， 梢乙) 一( k - 1 ) 2 4 ( n - 1 ) + ( k - l x 2 n - 1 - 1 ) 2 - - 4 - ( k + l x 2 n - l - n ) 2 _ ec t n 1 _ , - 2 - l ( 芝( 学) n - i - t + 芝( 半广h ) ( 邢乙) ：掣+ 业产+ 2 n - 2 - i ( 圭( 竽广t - ，) ) 定理得证 b c 树性质的研究 3 3 后扩星形b c 树的与原叶相关的b c 子树数 定理3 2k 乙的恰含指定的一片原叶的b c 子树个数记为 7 ( k l ，1 ) ，则 ，7 饭0 。，1 ) = ( k - 1 ) 2 柑+ q 一：( ( 学) n - 2 - 1 ) _ lr a = o n 一3h 2 ( k - 2 ) 2 ”3 + l + q 一：( ( 毕) ”2 一) 后为奇数， k 为偶数 证明：我们分两种情况进行讨论，即七为奇数时的情况和k 为偶数时的情况： ( 1 ) 七为奇数时 由第二章2 3 2 节的知识很容易知道恰含指定的一片原叶且不含根节点y 的b c 子树个数为( 七一1 ) 2 下面计算恰含指定的一片原叶且含根节点1 ，的b c 子树： 因为原叶所处的层数七为奇数，所以恰含指定的一片原叶且含根节点，的b c 子树的其余叶子( 相对于原叶) 只能处在奇层，七层除外( 若取七层，显然不满足要求) ， 为便于分析我们将恰含指定的一片原叶且含根节点1 ，的b c 子树按非原叶叶子所在