（应用数学专业论文）赋权树上的组合及渐近结果.pdf

摘要 摘要 有根树具有非线性结构，在组合数学中占有重要的地位。有序树是一类特 殊的有根树，其节点的子树具有序关系。格路与有根树有着紧密的联系，利用 格路语言，本文给出了一些等式的组合证明。c h e n ，d e u t 8 c h 和e l i z a l d e 把有 序树上的叶子分类为右叶子和非右叶子，构造了有序树和二m o t z k i n 路之间的 双射。c o k e r 在研究m u l t i p l ed y c k 路时，给出了两个关于n 盯a 归n a 多项式和 c a t m a n 数的组合恒等式，它们的组合证明是c o k e r 提出的公开问题。我们利用 c h e n - d e u t s d 卜e u z 酊d e 双射，通过2 一m o t z l 【i n 路上的权值变换，给出了c o k e r 等 式的组合解释。e u ，l i u 和y 曲利用生成函数的方法研究了有序树上叶子个数 的奇偶性问题，得到了一个关于n a r a 蛳n a 数和c a t a l a n 数的关系式，给出了这 个关系式的部分组合解释。本文描述了此关系式的三种不同的组合证明。 在庆祝r ps t a n l e y 教授6 0 岁生日的学术会议上，p o s t n i k d v 给出了一 个关于二叉树h o o kl e n g t h 的组合等式，并要求给出其组合证明。本文给出了 p o s t n i k o v 等式的一个简单递归证明。s e o 通过引进标号树上正常点的概念构造 了一个双射，给出了p o s t l l j k o v 等式的组合证明，该双射由三个双射复合而成， 进一步s e o 导出了一些关于叉树，有序森林h o o k k n g t h 的组合等式，他的证 明引进了标号树上正常点的概念。本文利用l a 玎出e r t r d t h e 等式，给出了一个 统一的方法来证明s e o 公式和几个p o s t n i k a 、，类型的等式。 m e i r 和m o o n 定义简单生成类( s i m p l y - g e n e r a t e d 知a l i l y ) 为一类节点赋权 的有序树。本文考虑了一类特殊的简单生成类，我们称之为二项式树( b i n o m 瑚 t r e e s ) ，其权值是一些二项式系数。二项式树包括了有序树和七叉树。特别 地，标号无序树是二项式树的极限形式。本文主要研究了简单生成类上的四个 统计量：叶子，非右叶子，正常边和正常点，运用d 缸b o u x 定理得到了其期望 地( n ) 和方差的渐进结果，这里n 是树的节点数；进一步证明对于任何一个常数 0 c l ，都存在一个简单生成类，当n 趋近于无穷时，地( n ) 加趋近于c ( 对 于正常边而言，0sc 1 2 ) 。对于二项式树，我们给出了四个统计量的期望 值的精确公式。根据l y 印1 1 n o v 条件，本文证明二项式树的正常点的分布接近于 正态分布。 本文的结构如下：第一章介绍关于各种有根树的定义和计数公式，给出一 摘要 些a b e l 等式的组合证明，引进简单生成类的概念，二项式树的定义和例子；第 二章研究了叶子和非右叶子统计量，得到了一些关于其分布的结果，进一步， 根据有序树和2 一m o t z l 【i n 路的双射，给出c o k e r 等式和叶子奇偶性等式的组合证 明；第三章利用l a m b e r t r _ o t h e 等式研究p o s t n i k o v 等式和s e o 公式；第四章讨 论了正常边和正常点统计量，得到了关于其分布的结果。 关键词：赋权有序树，简单生成类，二项式树，叶子，非右叶子，正常边，正常 点 i i a b s t r a c t a b s t r a c t t h ec l a s so fr o o t e dt r e e si so n e t h em o s ti m p o r t a n tn o n l i n e 盯s t r u c t l l r e si n t h ef i e l do fc o m b i n a t o r i c s 0 r d e r e dt r e e sa r er o o t e dt r e e sw i t ha no r d e r i n ga s s 0 - c i 曲e dw i t ht h es u b t r e e so fe a c hv e r t e x i ti sw e l l - k n o w nt h a t1 a t t i c ep a t h s 射e c l o s e l yr e l a t e dt o0 r d e r e dt r e e s w 色p r e s e n tl a t t i c e - p a t hi n t e r p r e t a t i o n sf o rs o m e c o l b i n a t o r i di d e n t i t i 韶c h e n ，d e u t s c ha i l de l i z a l d eg a eab i j e c t i o nb e t w e e no r - d e r e dt r e e sa n d2 - m o t z k np a t h s ；t h e i ra r g u m e n ti n v o l v e dd i s t i n g u i s h i n gb e t w e e n r i g h t m o s ta n dn o 小r i g h t m o s tl e a v e si no r d e r e dt r e e s c o k e rr e c e n t l yu s e dg e n e r a t i i l gf u n c t i o n st od e r i v e 伽oc o m b i n a t o r i 址i d e n t i t i e si n v o l v i n gn a r a 恤am m l b e r 8 a n dc a t a l a nn 啪b e r 8a n da s l 【e df o fc 0n 1 _ b i n a t o r i a lp r o o f 8 w 宅a 1 1 s w e rc o k e r s q u e s t i o n sb yl l s i n gt h ec h e n _ d e u t s c h e u z a l d eb i j e c t i o na n dt r a n s f o r i n i n gw e i g h t s i n2 一m o t z l 【i np a t h s i n8 t u d y i n gt h ep a r i t yo ft h en 岫b e ro fl ea _ v i no r d e r e d t r e e s ，e u ，l i ua n dy e h1 1 s e dg e n e r a t i n gf u n c t i o n st od e r i v eac o l b i n a t o r i a li d e n - t i t yi i l v o l v i n gn a r 8 y a n a 肌1 b e r sa n dc a t a l a nn 岫b e r s ；t h e y8 1 s 0g a v eap a r t l a l b q e c t i v ep m o w j 舀v et h r e ed i f f e r e n tb i j e c t i o n sf o rt h i si d e n t i t y _ a tt h ec o n f e r e n c eh o n o r i n gm c h a r ds t a i l l e y s6 0 t hb i r t h d a yp o s t n i k d vg a v e ac o m b i i l a t o r i a li d e n t i 锣i n v o l 、，i n gh o o kl e n 昏h so fb i n a 珂t r e e s ，a n da s k e df o ra c o i n b i n a t o r i a lp r o o fw 色g i v eas i m p l ei n d u c t i v ep r o o f0 fp o s t n i k o v si d e n t i t ys e o c o i l s t r u c t e dab i j e c t i v ep r o o ft h a ti n _ v o l v e dt h ec o m p o s i t i o no ft l l r e eb i j e c t i o i l s ； h ea l s od e r i v e da n a l o g o l l si d e n t i t i e sf o r h o o kl e n g t h so f 七一a r yt r e e sa n df o r e s t s0 f o r d e r e dt r e e s s e o sp r 0 0 f si i n ，0 1 v e da ni n t e r p r e t a t i o ni nt e r m so fw h a ta r ec 以l e d p r o p e rv e r t i c e si nt r e e s w bu t h el a n 幽e r t - r d t h ei d e n t i t yt o 舀v eau n j f i e dp r o o f o fs e o sf o m u l a s8 n dp o s t n i b v - 乜，p ei d e n t i t i e s m e i ra n dm o o na n do t h e r sh a v es t 咀i e ds i i n p l y - g e n e r a t e df 砌n e so ft r e e s ； t h e s ea r ew e i g h t e df 锄i l i e so fo r d e r e dt r e e si nw h i c ht h ew e i g h t sa r ea s s i 9 1 l e di n ac e r t a i nw a y w ed e f i n eas u b _ f a m i l yo fs i m p l y - g e n e r a t e dt r e e s ，b i n o m i a lt r e 船， i nw h i c ht h eu n d e r l y i n gw e i g h t sa r ec o e 币c i e n t si nb i l l o m i a le x p a i l s i o n s b i n o m i a l t r e e si n c l u d et h eo r d i n 御yo r d e r e dt r e e sa n dt h e 拓龇yt r e e s ，f o re x 锄p l e ；a n d ， 舔w es h a l ls e e ，t h e1 a b e u e du n o r d e r e dt r e e sc a nb er e g a r d e d 私al i m i t i i l gc a s e i a b s t r a c t o fc e r t a i nb i n o m i a lt r e e s t h em a j np u r p o s eo ft h i st h e s i si st oi i l v e s t i g a t ef o u r s t a t i s t j c so ns i m p l 弘g e n e r a t e df a m i l i e s ：1 e a v e s ，n o n - r i g h t m o s tl e a v e s ，p r o p e re d g e s a n dp r o p e rv e r t i c e s w eu s e 【) 缸b o u x st h e o r e mt oo b t a i na s y i n p t o t i cr e s u l t so n t h e i re x p e c t a t i o n sp t ( n ) a n dv a r i a n c e s ，w h e r end e n o t e st h en u i 】曲e ro fv e r t i c e si n t h et r e e sb e i n gc o 璐】d e r e d f o ra n yc o i l s t a n to c 1 ( f o rp r o p e re 电e s ，o c 1 2 ) ，w ep r a v et h a tt h e r ee 妇s t 8a8 i m p l p g e n e r a t e df 啪i l ys u c ht h a t 肌( n ) n t e n d st ocw h e nn o o f b rb i n o i i l i a lt r e e s ，w ed e r i v ee ) ( p l i c i te x p r e 箱i o n sf o r “( n ) u s i n gl y a p u n a v sc o n d i t i o n ，w ep r o 、，et h a tt h ed l s t r i b u t i o no ft h en u h l b e r o fp r o p e rv e r t i c e si sa s y m p t o t i c a l l yn o r m a l w 毫c o n c l u d et l l i sa b s t r a c tw i t hac h 印t e 卜b y - c 1 1 a p t e rs u m m a r y w 色b e g i nc h 妒 t e r1w i t hd e 6 n i t i o n sa n de n 呦e r a t i o nf o m u l 嬲f o rr o o t e dt r e e sa 1 1 d 舀v ec o m b i - n a t o r i a li n t e r p r e t a t i o i l s0 fs o m ea b e li d e n t i t i e s ；n e ) ( tw ed e l i n es i m p l y - g e n e r a t e d f 砌l i e sa n dr e v l e w8 0 m eb a s i cr e s u l t s ；t h e nw ei n t r o d u c eb i n o m i a lf 眦i l i e sa n dg i v e s o m ee x a m p i e s w bs t u d yl e a 嘲a i l dn o n r i g h t m o s t1 e a e 8i nc h a p t e r2a n do b t a j n s o m er e s u l t 8o nt h e i rd i s t r i b u t i o n ；t h e nw ea n s w e rq u e s t i o 璐r 撕s e db yc o k e ra n d b ye u l i u - y e hb y 舀、，i n gb i j e c t i v ep r o o f 8o fc e r t a i ni d e n t i t i e 8i n v o m n gn a r a y a n a n u r n b e r sa n dc a t 出a n 删m b e r s i i lc h a p t e r3w eu s et h el a 1 b e m r o t h ei d e n t i t y t op r o v es e o sf o r m u l a sa n dp o s t n i l 【o v - t y p ei d e n t i t i e s i nc h a p t e r4w ei i l v e s 七i g a t e p r o p e re d g e 8a n dp r o p e rv e r t i c e s 舢l do b t 缸nr e s l l l t so nt h e i rd i s t r i b u t i o n s k e y w o r d 8 ：o r d e r e dt r e e s ，s i m p l y - g e n e r a t e df 锄i l y b i n o m l a lt r e e s ，1 e a e s ，n o n - r 蟾h t m o s tl e a v e s ，p r o p e re d g e s ，p r o p e rv e r t i c e s i v 生! 壁! ! ! ! 鲤! 竺 1 1 1 2 13 1 4 1 ，5 1 6 1 7 1 8 1 9 l i s to ff i g u r e s a ne x 眦p l eo fr o o t e d t r e e s 3 - v e r t e xa n d4 - v e r t e xo r d e r e dt r e e s 3 - v e r t e xb i n 缸yt r e e s ac o m b i n a t o r i a le x p l a n a t i o no ft h ea b e li d e n t i t y ( 1 8 ) t h e 丘r s td e c o m d o s i t i o n f b r0 r d e r e d t r e e s t h es e c o n dd e c o m d o s i t i o nf b ro r d e r e dt r e e s t h ed e u t s d l - s h a p i r ob 巧e c t i o n t h e c h e n - d e u t s c h e u z 出eb i j e c t i o n 3 - v e r t e xa n d4 v e r t e xs i n l p l y - g e n e r a t e df 锄i u e s 2 1a n 既锄p l eo f t h es e tc 1 3 2 2t w oc a s e sf o rl e g a lv e r t i c e 8 钉 2 3t w oc a s e sf o rt h ef i r s tm e g a lv e n e ) 【口 2 4a ni i y v o l u t i o no no r d e r e dt r e e s 2 5t h ed e u t s m s h a p i r ob i j e c t i o na n di n v o l u t i o nt 2 6t h ec h e n - d e u t s c h e n z a l d eb i j e c t i o na n di i 啪1 u t i o nt 2 7ah o r i z o n t a lm e r g ea n dv e r t i c a lm e r g e 2 8a n i n v o l u t i o no n l a b e u e do r d e r e d t r e e s 3 1h o o kk n g 七h so f3 - v e r t e xb i n 哪7 t r e e s v i i 1 0 1 3 1 3 1 5 1 5 1 6 4 0 4 0 4 1 4 1 4 3 4 3 4 4 4 5 4 7 l i s to f t 如1 e s l i s to ft a b l e s 2 1 p 0 1 y n o m i a l s f o r l e a e sa n dn o n - r i g h t m o s t k a v e s 2 2o n l e a 8a n dn o n - r i g h t m o s t l ea _ v e s i i lo r d e r e d t r e e s 2 3o n l e a e sa n dn o n - r i g h t m o s t l e a e s i nb i n a r y t r e e s 2 4o nl e a v e sa n dn o n r i g h t m o s tl e a 聊i nl a b e l k dr o o t e dt r e e s 4 1 p o l y n o m i a l s f o rp r o p e re d g e sa j l dv e r t i c e s ， 4 2o np t o p e re d g 船m l a b e u e do r d e r e dt r e 瞪，。 4 30 np r o p e re d g e s i n l a b e l l e db i n a z y t r e ， 4 4o np r o p e re d g e s i n l 8 | b e l l e dr o o 屯e d t r e 髓， 4 5o np r o p e rv e r t i c e s i n l a b e l l e do r d e r e d t r e 鹤 4 60 np r o p e rv e r t i c e si n1 a b e l l e db i n a r yt r e e s 。 4 7o np r o p e rv e r t i c e s i n l d b e l l e dr o o t e d t r e e s a 】a b e lj d e n t i t j 船， 孔孙卯勰 ；n礼讫跖 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：扬雨烈 叻6 年sa | f 黾 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：杨确铋 御6 年岁只f 雪日 c h a p t e r1 e n 啪e r a t i n gn 嘲 c h a p t e r1 e n u m e r a t i n g 叶e e s t h ec l a s so ft r e e si 8o n eo ft h em o s ti m p o r t a n tn o n l i n e a rs t r u c t l l r e st h a t 盯i s ei n c o m b i n a t o r i c s 7 n e e 8w e r e 丘r s ts t u d i e db yc a y i e y ( 1 8 5 7 ) i n 8 j t h em a i n 缸m0 f t h i sc h a p t e ri st oi n t r o d u c ec o n c e p t sa n de n 啪e r a t i v ef b r m u l l 【i n d so fr o o t e d t r e e s 1 1d e 6 n i t i o n s at 他ei sa na c y c l i cc o n n e c t e dg r a p h t h ee 仃妒匆慨h a v i n gn ov e r t i c e 8a n dt h e 加们口ft r 优w i t ho n e 、，e r t 钗a r et w os p e d a lc a s e sf o rt r e e s f o rt h en o n - e m p t yt r e e ， t h e r ei so f t e no n ed i s t i n g u i s h e dv e r t 旺c “l e dt h er d d ta n dt h et r e ei 8s 出dt ob e am d t 甜t r n o w ，l e t1 1 s1 1 s et h ed e 矗n i t i o nb yk n u t h 【4 4 ，p 3 0 8 】o rs t a n l e y 【8 3 ， p 2 9 3 _ 2 9 5 1 d e f i n i t i o n1 1 ar d d t e d 抑b ei sd e f i n e df o r m a l l ya saf i n i t es e tto fo n eo rm o r e v e r t i c e ss u c ht h a t ( 1 ) t h e r ei so n es p e c i a d l yd e s j g n a t e dv e r t e xc a l l e dt h em 以ro ft h et r e e ；a n d ( 2 ) e i t h e rt i st r m 出，o re 1 t h e 删n a i n i n gv e r t i c e s ( e x c l u d i n gt h er o o t ) a r e p a r t i t i o n e di n t om 1d 埘o i n tn o n - e m p t ys e t s 丑，2 m ，a n de a c ho f t h e s e s e t si nt 啪i 8ar o o t e dt r e e t h et r e e s 正，了ka r ec a u e dt h es 曲抑咄o f t h er o o t 冗e m o 他l 1 ( i ) f o rc o n v e n i e n c e ，w ec a l lt h a tt h es u b t r e eo ft h er o o ti st h e e m p t yt r e ef o rt h et r i 、，i a lt r e e 1 c h 印t e r1 e n u m e r a t i n g 皿e e s ( i i ) t h i sd e n i t i o nj u s t 百v e ni sr e c u r s i v e t h e r ea r en o n r e c u r s i v ew a y st od e f i n e r o o t e dt r e e s ，b u tar e c u r s i v ed e 丘n i t i o ns e e m sm o s ta p p r o p r i a t es i n c er e c u r s i o n i sa ni n n a t ec h a r a c t e r i s t i co ft r e es t r u c t u r e s i nf a c t ，t h i sd e f i n i t i o n 西v e su 8 ad e c d m p d s o t z d 仃o fr o o t e dt r e e s w bw l ut a c i t l ya s s u m et h a t 削ft 他即t j e d 诂c u s s 口他m d t e 面伽l f e s se 印托c 。t 嘻s t 口t e dd e 伽e n o t e 七h a ta l lt r e e sc a n b ed r a nw i t ht h er d d tn tt et d p ( i i i ) t h e r ei sav e r yc l o s er e l a t i o nb e 七w e e nr o o t e dt r e e 8a n dt r e e s i fw et 蠢i ( et h e d i a g r 锄o far o o t e dt r e ea n di 9 1 1 0 r et h ed e s i g n a t i o n0 ft h er o o t ，t h e nw e o b t a j na 出a g r a m at r e e c o n v e r s e l y ，g i v e nat r e e ，i fw ed e s l g n a t eo n eo f i t sv e r t i c e sa sar o o t t h e nt 1 1 i sd e f i n e st h es t m c t u r eo far o o t e dt r e e h e n c e a “r o o t e dt r e e ”m e a n i n gat r e et o g e t h e rw i t har o o tv e r t e x ，i sc o n c e p t u a u y i d e n t i c a jt oar o o t e dt r e e i tf o l l o w s 行o mt h ed e 6 n i t i o nt h a te v e r yv e r t e xo fat r e ei 8t h er 0 0 t0 fs o m e s u b c r e ec o n t a i n e dl nt h ew h o l et r e e t h en u n 山e ro fg u b t r e e so fav e r t e ) 【i 8c a l l e d t h eo 乱 d 印他eo ft h a tv e r t e x an o n - r o o tv e r t e xw i t ho u t d e g r e ez e r oi sc a l l e da ? e 巧an o n - l e a fv e r t e xi so f t e nc a l l e da n 伽钯m 础 e n 瞄i np a r t i c u l a r ，t 比虮们o f z r e e n s 竹d ? 甜e s u s u “y ，e a c hi n t e m 蛆v e r t e xi ss a i dt ob et h ep o 卵耐o ft h e r o o t so fi t ss u b t r e e s ，a n dt h el a t t e r 盯es a i dt ob e6 r d 晓e 邝；t h e y 盯ec 2 f d r e 竹o f t h e i rp a r e n t t h er o o to ft h ee n t i r et r e eh a sn op a r e n t a 1 lv e r t i c e si nt h es u b t r e e m o t e da tav e r t e xt j ( i n c l u d i n gt h i sv e r t e x ) 盯es a i dt ob ed e s c e n d 口n 如o f 口 t h ej e 口e fd rn 尬t “d eo fav e r t e xw i t hr e s p e c tt oti sd e f i n e dr e c u r s i v e l y ：t h e l e v e lo ft h er o o tri sz e r o ，8 n d 七h el e v e lo fa n yo t h e r 、，e r t e xi so n e1 a r g e rt h a nt h a t v e r t e x sl e v e l 晰t hr e 8 p e c tt ot h es u b t r e eo frc o n t a j n i n gi t t h el e 口“d ，口r b ei 8 t h el a r g e s to n ei nt h e1 e v e l so f 甜lv e r t i c 既t h e s ec o n c e p t sa r ei l l u s t r a t e di nf i g u r e 1 1 ，w h i c hs h o w sa4 v e r t e xt r e e t h er o o ti srw i t ho u t d e g r e e2 t h e r ea r et w o l e a v e s r l e v e l0 一 【删1 一 l 酬2 一 f i 9 1 l r e1 1 ：a ne ) 【锄p l eo fr o o t e dt r e e s 2 c h 印t e r1 e 肌m e r a t i n gn e 图 f o ra n ym v e r t e xm o t e dt r e e 死，i ti 8w e l l 1 【n o 咖t h a t 竹= 1 + fo u t d e g r e eo f 仉 z j u t k s o m ei m p o r t a n tv a r i a t i o n so fr o o t e dt r e a r eo b t a j n e db ym o d i 聊n gt h er e - c u r s i v ed e f i n i t i o n d e f i n i t i o n1 2 a nd r d e 他dz 他eti sa 觚t e 舱to fo n eo rm o r ev e r t i c e s8 u c ht h a t ( 1 ) t h e r ei so n es p e c i a l l yd e s i g n a t e dv e r t e xc d l e dt h em 耐r o ft h et r e e ；a n d ( 2 ) e i t h e r 丁i st r i v i a l ，o re l s et h er 锄a i n i n gv e r t i c e s ( e x c l u d 她t h er o o t ) a r e p u ti n t oa nd r d e 侣dp a r t i t i o ( 五，7 k ) o fmd 埘o i n tn o n e m p 锣t s 冗，a n de a c ho f w h i c h i sa no r d e r e d t r e e 月e m o 础1 2 o r d e r e dt r e 鹤a r e 幽oc a l l e d p l a n et r e e ”b y8 0 m ea u t h o r s ，s i n c et h e m 锄e ro fe m b e d d i n gt h et r e ei nap l a n ei sr e l e v a i l t f i g u r e1 2g i v e se ) 【锄p l 郎o f3 v e r t e ) 【a n d4 - v e r t e xo r d e r e dt r e e 8 八 工八八爪 ii f i g u r e1 2 ：3 - v e r t e xa 埘4 - v e r t e x0 r d e r e dt r e e s d e f i n i t i o n1 3 l e t m 2 ，a i l m 一口叫t 他e t i sa 缸i t es e to fv e r t i c 皤s u c h t h a t ( 1 ) e i t h e r ? i se m p t y ，o re l s eo n es p e c i a l l yd e s i 印a t e dv e r t e ) 【i 8c a l l e dt h er d o tr o f t h et r e e ：a n d ( 2 ) t h er e m 出n i n gv e r t i c e s ( e x c l u d i n gt h er o o t ) 盯ep u t i n t oa no r d e r e dp a r t i t i o n ( 乃，) 0 f e x a c t l y 仇d 蠲o i n t ( p o s s 曲匆e 唧幻) s e t s 正，a n de a c h o fw h i c hi sa nm a r yt r e e r e m n 北1 3 a2 一a r yt r e ei sa l s oc a l l e da6 2 伽i 付t 他e w h e nd r a w i n ga nm a r yt r e e f o r m 锄a u ，t h ee d g e s j o i n i n gav e r t e ) 【甜t o t h er o o t so f i t ss u b t r e e st 1 ，7 m 材e d r a w na te q u 蛆a n 百e ss y m m e t r i cw i t hr e s p e c tt oav e r t i c a la 商s t h u st h ee m p t ) r s u b t r e e 正i si n f e r r e db yt h ea b s e n c eo ft h e t he d g e 丘o m f i 9 1 l r e1 3d e p i c t 8 f i v e3 - v e r t e xb i n 棚了t r e e s 3 c h 印t e r1 e n u m e r a t i n gn e e s 入 f i g l l r e1 3 ：3 - v e r t e xb i n 骶yt r e e s d e 丘n i t i o n1 4 l e tm 2 ，w es a yt h a ta _ n 打p a r yt r e ei sac d 们p k f 8m d 叫t 代圯i f e v e 巧i n t e r n dv e r t e xe x a c t l yh a smc h n d r e n ， r e m n 讹1 4 f o rac o m p l e t em 一缸yt r e et ，i fi th a sni n t e r n a lv e r t i c e s ，t h e nt h e n u 瑚b e ro fk a e 8m u s tb e 疗m + 1 一几，w h i c hi m p l i e st h a tt h en u i i 】【b e ro fv e r t i c e s i s n m + 1 t h e r ei sav e 叮c 1 0 r e l a t i o nb e 讹，e e ni n c o m p k t em - a r yt r e e s8 i l dc o m p l e t e 竹卜舭yt r e 朗d e l e t i n ga l lk a e so fa n ( n m + 1 ) 一v e r t e xc o m p l e t em ，踟yt r e e ，w e h a ea n ，卜v e r t e xm 一锄yt r e e ；c 0 1 w e r s e l y