（运筹学与控制论专业论文）mn树的判定和计数.pdf

摘要 树是图论中的一个基本概念，b e i n e k e 与p i p p e r t 在 2 中首先将其推广到高 维空间，后来d e w d n e y 在 1 中又进一步把它推广到n 维复形上，得到了( m ，n ) 一树 的定义，并且类似于图论中树的特性，给出了以下( m ，1 2 ) 一树的基本性质： 若k 是一个( m ，n ) 一树，则k 满足以下条件： ( 1 ) k 是( i n ，n ) 一连通的； ( 2 ) k 不含( m ，n ) 一回路： ( 3 ) 口 ( k ) = b m 。( 七，世) ，= 1 , 2 ，一， ， 其中b 。伥耻掣m 腻t ) _ 掣 盯一i 舸+ j以磁 单形的个数，( k = 1 , 2 ，- ，”) 。 口( k ) 表示k 中k 维 本文首先在 1 与 5 的基础上，结合以上( m ，n ) 一树的三个基本特性，给出 了判断( m ，n ) 一树的一系列充分必要条件。然后，再通过( 【，n ) 一树的图论定义，用 组合的方法，给出了以下顶点数为口。的，标号的( m ，n ) 一树的数的计数公式： 口m”c甜。，=喜i!兰羔s(：一s+，“2 其中d = 胛一m ，r = 胛+ 1 ，d = 州+ l ，s = ! 生二型，门 坍o 。 关键词：单形，复形，( m ，n ) 一树，( m ，n ) 一回路，( m jn ) 一连通，( m 1n ) - 自a j 计数公式。 a b st r a c t t r e ei sab a s i cc o n c e p ti ng r a p ht h e o r y ，a n di tw a sf i r s t y e x t e n d e di nh i g h e rs p a c ei n 2 b yb e i n e k ea n dp i p p e r t l a t e r ， i tw a sd e v e l o p e df u r t h e ri nn d i m e n s i o n a lc o m p l e x e si n 1 b y d e w d n e y ，a n dt h ec o n c e p to f ( m ，n ) 一t r e ew a so b t a i n e da tt h es a m e t i m e f u r t h e r m o r es i m i l a rt o t h et r e e c h a r a c t e r i z a t i o no f g r a p ht h e o r y ，t h e f o l l o w i n g r e s u l ta b o u tt h e ( m ，n ) 一t r e e c h a r a c t e r iz a ti o nw a sg i v e n ： i fki sa ( m ，n ) 一t r e e ，t h e nks a t is f i e st h ef o l l o w i n g c o n d it i o n s ： ( 1 ) ki s ( m ，n ) 一c o n n e c t e d ： ( 2 ) kc o n t a i n sn o ( m ，n ) 一c i r c u i t s ： ( 3 ) 盘。( k ) = b m , n ( k ，k ) ， w h e r e 女= 1 , 2 ，一，；君( 女，足) 口o ( k ) 一m i 以一卅一 口o ( k ) 一 1 h 一，竹 时卜d 口。( k ) d e n o t e s t h en u m b e ro f 一d i m e n s i o n a l s i m p l e x e s i n k i nt h ep a p e r ，o nt h eb a s i so f 1 a n d 5 ，b yc o m b i n i n gt h e a b o v et h r e eb a s i cf e a t u r e s ，s o m en e wn e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n so f ( 1 1 1 ，n ) 一t r e ea r ef i r s t l yg i v e n a tt h el a s t ，b yt h e d e f i n i t i o n o f ( m ，n ) 一t r e e i n g r a p ht h e o r y a n d u s i n g t h e c o m b i n a t o r i a lm e t h o d ，t h ef o l l o w i n gc o u n t i n gf o r m u l ao fl a b e l e d ( m ，n ) 一t r e e o fo r d e r 口ow a s g i v e n ： 吃。c 口。，= 击( 。，。，：倥。一曲 s ( ：) 一s + t 5 。 矗面一 w h e r e 盘= 门一卅，r = ”+ 1 ，d = + 1 ，s 竺! 二竺二! ，舯 o 一，“u ”一m k e y w o r d s ： s i m p l e x ，c o m p l e x ，( m ，n ) 一t r e e ，( m ，n ) 一c o n n e c t e d ( m ，n ) 一c i r c u i t ，( m ，n ) 一h o l e ，c o u n t i n gf o r m u l a 2 一引言 1 1 基本概念 设矿是一个有限的顶点集，k 是矿上的一个非空子集簇，v x k ，x 称为k 的 一个单形，如果k 中的每个单形的每个非空子集还是k 中的一个单形且k 的顶点 集v ( x ) = 【j x ，则称k 为一个复形。这与同调论中“有限抽象单纯复形”的定义 j e r 等价。以下的k 均表示为一复形。对于k 中的任何单形x ，h 一1 称为单形x 的维数， 而m a x x l _ 1 ，lx k 称为复形k 的维数。以下我们将具有维数为n 的单形称为”维 单形( 或n 一单形) ，具有维数为n 的复形称为i l 维复形( 或”一复形) 。从这我们可 以看出，图论中一般的图实际上可看作是维数l 的复形。 对于复形三，若l k ，则称为k 的一个子复形。任给复形k ，若存在 l l 映射f ：y ( 足) - v ( l ) 使得x = v 。，”，v 。) 是足中的一个单形，当且仅当 f ( x ) = f f ( v 。) ，f ( v 。) ，f ( v 。) ) 是l 中的一个单形，则称k 与三是同构的，记作k 望 l 。v s k ，记s = z k 卜y 对某一y s ) ，显然s 是k 的一子复形，s 称为s 在k 中的闭包。如果s 中只有一个元素，即s = y ) ，则我们将s 记作y 。 设n 维复形k 有p 个顶点( h p ) ，且v ( k ) 的每一个n + l 元子集都是k 的一个 单形，则称k 是完全的，记作k ：。 设x 。，y ，x 2 ，y 2 ，x h ，y h ，x ，是复形足中的一个由m 维单形与”维单形组成的 交错序列沏 2 聃1 ) ( i i i ) 对至多的一女，1 ：，有口。( 彪) = b 。( ，世) 。 定理1 2 8 嘲纯n 维复形k 是一个( m ，n ) 一树的必要条件是： 口。c k ， ( 三：) 一 口。c k ，。 定理1 2 9 设( m ，n ) 一简单的纯n 复形足的维单形为s i , s z ，s 。( r ) ，若 s 是恰好d ，个n 维单形闭包的交，则k 是( m ，n ) 一树当且仅当足不含( m ，n ) 一回路 且有d ，= q 。( k ) 一l j + d 。( k ) 。 二( m n ) 一树的判定条件 本节主要是在上面已有结论的基础上，通过进一步深入地研究，得到了一系 列有关( m ，n ) 一树的新的充分必要条件。 21 ( m ，n ) 一树的充分必要条件 首先，由 4 中纯n 维复形k 的( m ，n ) 一图的作法和性质，g c l t 箱- 定理21 1 纯n 维复形x 是- - + ( m ，n ) 一树当且仅当它满足下列条件： ( i ) k 是( m ，n ) 一简单的： ( i i ) k 是( m ，n ) 一连通的； ( i i i ) a , ( k ) = c r ( k ) 慨川乩 证明：先证必要性。若k 是一个( m ，n ) 一树，则由定理1 2 1 得：( i ) ，( 1 1 ) 成 立。又由定理1 2 2 ，我们有口。( k ) = b 。( m ，k ) ，口。( k ) = b 。( n ，k ) 。即有 的，、口o ( k ) 一m 一1 a 一( k ) 5 等 消去a 。( k ) ，i 更彳导( i i i ) 。对于充分性。作复形k 的( m ，n ) 一图g ，由于k 是( ，“) 掣 掣 连通的，故g 是连通的。又由k 与其( m ，n ) 一图g 的关系( 2 ) ，以及( m ，n ) 一图g 的 作法和条件( i i i ) ，我们有： e c g ，= 口。c k ，( 三：1 ) 一a 。c k ，= 口。c k ，( 三：； 一口。c k ，f ( 二： 一- f 一- = a 。( 足) 一1 = j 矿( g ) l - 1 从而可知：g 是一棵树。又由条件( i ) 和引理1 2 5 可得：k 是- - 5 ( m ，n ) 树。 证毕。 其实，对于定理1 2 4 ，我们可将其条件( i i ) 更加一般化，即有以下结论 定理2 1 2 纯h 维复形k 是一个( m ，n ) 一树当且仅当它满足以下条件： ( i ) k 不含( m ，n ) 一回路； ( i i ) 口。( 芷) = b 。( 肌，k ) ； ( i i i ) 对某一个t ， m ) 维单形，于是其中至少存在一个 p 维单形z ，且在z 中可以找出两个不同的m 维单形x 。，x ：，于是x i , y l ，x 2 , y 2 ，x ，形 成一个( m ，n ) 一回路。这与足不含( m ，n ) 一回路矛盾，由此可得以上事实成立。所以 我们可知此时k 中的k ( m k s 月) 维单形的个数只与h 维单形的个数有关，即有 吒( 足) = 口。( 足) l ：l 。从而由( i i ) 可得：d 。( k ) = b 。( ，k ) 因此由定理1 2 ，4 ， ly t q4 - lj 充分性成立。证毕。 为了对( m ，n ) 一树的结构有更深入地了解，我们在n 维复形中引进度的概念： 定义2 1 3 设k 为纯h 维复形，x 为k 中的任一单形，若x 在k 中属于且仅 属于d 个 维单形的闭包，则称x 在k 中的度为d 。 定理2 1 4 设纯n 维复形k 的m 维单形的度之和为d 。，则k 是( m ，n ) 一树当 且仅当它满足以下条件： ( i ) k 是( m ，n ) 一简单的： ( i i ) k 不含( m ，n ) 一回路； ( i i i ) d 。= k 。( k ) + 口。( 足) ) 一1 。 证明：对应于复形k ，按以下方法作它对应的二部图g 。= ( _ ，：) ：将k 中 的每个h 维单形看作一个顶点，这些顶点组成g 。的点集k 。同时将置中的每个m 维单形也看作一个顶点，这些顶点组成g 。的点集。v v k ，v ：，且设v 所 对应的 维单形为y 。v ：所对应的m 维单形为x 叫则v - 与v z 邻接当且仅当 x 。、c y 。显然，按这种作法作成的二部图g 。，它与k 有以下关系： ( 1 ) k 无( m ，n ) 一回路当且仅当g 。无圈； ( 2 ) k 是( m ，n ) 一连通当且仅当g ，连通： ( 3 ) g 。的顶点数为：i v ( g 。) l = l u l + i = 口，( 世) + 口。( k ) ，g 。的边数为 i e ( g 。) l ：d 。 对于必要性：由于世是一个( m ，n ) 一树，则由定理1 2 1 ，( i ) ，( i i ) 成立。同时 可知k 是( m ，n ) 一连通的，故得g 。无圈且连通，从而g 。为棵树。因此有 i e ( g 。) i = l v ( o 。) 卜1 ，即d 。= 。( k ) 十盘。( 足) ) 一1 。 对于充分性：由于k 不含( m ，n ) 一回路，故g 。无圈，又由( i i i ) 可得： i e ( g 。) 【= l v ( g 。) 卜1 ，故g 。是一棵树。从而可知g 。是连通的，又k 是( m ，n ) 一简单 的，故由定理1 2 1 得：k 是一个( i l l ，n ) 一树。 证毕。 由定理2 1 4 的证法，我们还可以类似地证明以下结论： 定理2 1 5 设纯, 维复形k 的m 维单形的度之和为d 。，则k 是( m ，n ) 树当 且仅当它满足以下条件： ( i ) k 是( m ，n ) 一简单的； ( i i ) k 县( m ，1 3 ) 一连通的； ( i “) d 。= 忸。( 瓦) + 口。( k ) ) 一1 。 证明：同样，按定理2 1 4 的作法，作复形足所对应的二部图g 。若世是 ( m ，n ) 一树，( i ) ，( i i ) 明显成立。同时可知k 不含( m ，n ) 一回路。从而由k 与g 。的关 系可得：g 。是一棵树，因此有l e ( g 。) | = i v ( g 。) | _ 1 = | _ j + i 卜1 ，再由足与g 。的 关系( 3 ) 得：( i i i ) 成立。反之，若( i i ) ，( i i i ) 成立，则可得g 。是一棵树，从而g 。 无圈，故k 无( m ，n ) 一回路。再综合( i ) ，( i i ) ，由定理1 2 1 得：k 是一个( m ，n ) 树。证毕。 在定理1 2 3 中，k 的取值范围是l k m ，下面的结论表明：当m k 时，也有类似于定理1 2 3 的结论成立。我们先看当k = h 时的情形。首先引进几 个变量和引理。 设s ? ，蹈分别表示含有一个m 维单形，含有至少一个m 维单形的”，维复形的 集合。 引理2 1 6 若一个纯n 维复形k 有一个黠一序j ，l ，y 2 ，y ，则有 口。( k ) b ( h ，k ) ，且等号成立当且仅当h ，y 2 ，y ；是一个足二一序。 证明：设y l , y ：，y ，是k 中的一个霸一序，且令k ，= ，y ：，y ，) i = 1 , 2 ，一，s ，其中s = 口。( k ) 。则由粘的定义：我们有 n + 1 一 。( k ) 一a 。( k ，) ) m + l ，( f 1 ，2 ，j 一1 ) ，从而可得： 口o ( k 1 ) 一口o ( k 。) n m ， 又由于 b 。 置。m 。帆岸弘业篙型一掣 ：丛坠幽( f ：1 “2 ，s 一1 ) 。 一m 因此我们有 b 。( n ，kj + 【) 一b 。( n ，k ，) 1 从而可得：b 。( ”，k ) - b 。( ”，k 。) = 忙。，。( n ，足) 一b 。，。( n ，k 。) ) + 忙。，。( n ，k ，一，) 一b 。，。( n ，k ，一：) ) + - + 忙。，( n ，k ，) 一b 。( n ，k ，) ) s 一1 ， 因此， 口帆。( 门，k ) s 一1 + b m 。( 玎，k 1 ) = j 一1 + 1 = j = 口。( k ) 。 另外，当y ，y ：，y ，g ：- q - k ：，一序时，由( m ，n ) 一树的定义 ( m ，n ) 一树，显然有口。( 丘) = 吃。( ，t o ) 。 ( 2 ) 此时k 是一个 现证由口。( k ) = b 。( n ，足) 可推出y ，y ：，y ，是一个k 二。一序。假设 y 1 ，y 2 ，y 。不是一个k 二一序，则显然存在一正整数r ( 1 r 茎s 1 ) ，使得 a ( y ，k h ) 不同构于足二。，即有口。( k 。) 一2 。( k ，) n m ，从而有： b 。( h ，k ) 一b 。( n ，k ，) i ，则我们由( 2 ) 式可得：b 。( ，足) 一b ( n ，k 1 ) b 。( h ，k ) ，这与口。( k ) = 吃。( n ，k ) 矛盾。因此可知假设错误， 从而可得y 。，y ：，y ，是一个足二，一序。证毕。 引理2 1 7 纯h 维复形k 是( m ，n ) 一连通的当且仅当k 有一个霸一序。 推论2 1 8 如果足是一个( m ，n ) 连通的纯n 维复形，则有口。( k ) b ( n ，k ) 。 证明：由引理2 1 6 ，引理2 1 7 直接可得。 定理2 1 9 一个纯n 维复形k 是一个( m ，n ) 一树当且仅当它满足以下两个条 件：( i ) k 是( m ，r 1 ) 一连通；( i i ) 口。( k ) = b m 。( h ，k ) 。 证明；由定理1 2 1 ，定理1 2 2 可知，必要性成立。对于充分性，由于k 旱 ( m ，n ) 一连通，所以k 有一个黠一序，设为y l , y 2 ，y “k ) ，又由于 口。( k ) = b 。( n ，k ) ，因此由引理2 1 6 可得：y t , y 2 ，儿。( k ) 是一个k 二，一序。从 而由( m ，n ) 一树的定义可得k 是一个( m ，n ) 一树。 证毕。 现在我们讨论当m k 时的情形： 引理2 1 1 0 设k 是一个( m ，n ) 一树，k ：是足的含有p 个顶点的完全维子 复形，其中1 k p ，p 兰n + l ，则在k 中一个存在一n 维单形y ，使得k ：y 。 引理2 1 1 1 若女，m ，r ，r 都是整数，且有0 m k 志 且当0 ， h m 时，不等式( 3 ) 严格成立。 证明：当r = 0 或p = 九一m 或n r k 时，( 3 ) 式显然成立。现假设 门一r k ，0 ， 志 暇证篇 0 ) 所以有旦! 二生丛 兰! _ 二旦，即( 4 ) 式成立。从而可得 n门一m ( 4 ) 剃湍十 证毕。 引理2 1 1 2 如果纯n 维复形世有一个霸一序y ，y ：，y 。，则有( k ) 口( ，世) ，m k n ，且等号成立当且仅当y ，_ y ：，y 。是一个足2 l 一序。 证明：设y 。，y ：，儿是世中的一个戈一序，s 为k 中”维单形的个数，令 k = m ，y 2 ，y ，) ，i = 1 , 2 ，s 。同时假设口表示a ( y f + l ，k ) 中k 维单形的个数 i = 1 川2 ，s 一1 。由于a ( y 。，k 。) 中有n + 1 一仁。( k 。) 一( 茁) ) 个顶 点，黼n + 1 - ( c t o ( k , + , 。卜皤j ) ( 5 ) 又由于n + l 一0 。( e + i ) 一口。( 世) ) m + l ，故有( 足) 一口。( k ，) 蔓”一m 。 同时又因为b 。c t ，足。，一吃。c 屯足，= ! 墨掣( ： ， 且0 m + 1 k + 1 学 因此综合c s ，c e ，可得：( ： 一吼。当墨堡掣g ：1 。即有： f 刀+ 1 1 【川j 叫础”( 2 ，k m ) 一b m 一( 七，一) 当杉别取1 , 2 ，s 一1 时，连加( 7 ) 式的左右两边，可得： 北：扣。，博s - 1 k 。呱卜b 。 足，) ( 8 ) 式的左边等于口。( k ) 删一( ：b 。限 ( 6 ) ( 7 ) 右边等于b 。c t ，k ，一( ： ，因此我们有 1 1 lj ，即有 吼( 世) 础”( o ，k ) 。 ( 8 ) 志 q 旷斛“ + + i l 小u 玲 现在证明等号成立当且仅当y ，y ：，y ，是一个足：一序。首先证必要性。 当y 。，y ：，y 。是一个k l ，一序时，可知此时k 是一个( m ，n ) 一树，则显然有 c t i ( k ) = b ( k ，彪) ，( m k m + 1 ，从而可得：口o ( k ，+ ，) 一口o ( k ，) 0 。 此时有以一埘 口o ( k ，+ 1 ) 一口o ( k ，) 0 ，因此由引理2 1 1 1 可得： 甜k 1 皈j ) 坐篙m 盟k1 ) ， + j n l+ j 、1 1 再综合( 5 ) ，( 7 ) ，( 1 1 ) 可得：( ：) 一， 吃女，足。i ) 一吃，k ，) 。 因此，综合两种情况及( 8 ) 式我们可得出：口( k ) b 。( ，足) 。这与前提条件 口t ( 足) = 口。，。( 七，k ) 矛盾。从而假设错误， y 。，y ：，y ，是一个k 卅+ m 一序。 证毕。 类似于推论2 1 8 ，我们也有 推论2 1 1 3若纯”维复形k 是( m ，n ) 一连通的，则有 口女( k ) b 。( i ，世) ( m k n ) 类似于定理2 1 9 ，同样可得以下结论： 定理2 1 1 4 一个纯h 维复形k 是一个( m ，i 3 ) 一树当且仅当它满足以下两个条 件：( i ) k 是( m ，n ) 一连通； ( i i ) 口 ( k ) = b 。( t ，世) ，对至少一个k ， ( m k ： 一。m 。+ + 。1 c z ， 证明：由于c m + ，( ： 一c n + ， ：二： 一 ( ： 一、m 七+ + 。l ， r n + l 、m + 1 1 啪k j _ ”l t + j 故要z ，式魁蝴是要证m ( ： 九卜要证 而 + 1 ) ：塑二型垡型： 竺型 ( 九一七) ! ( 七+ 1 ) ! ( 肌+ 1 ) ! ( ”一七) ( 竹+ 1 ) ! ( 肌一七) ，ll，一、ll “一“ 一一暖 、一j “一“ 伽h一暖 ! 竺! ! ! ! 竺二! 1 2 1 竺= ! 型：! 竺二生! 二竺2 + 1 ) ! m ( m + 1 ) ( m - k + 1 ) ( m - k + 2 ) - ( m - k + ( n - m ) ) n ( n + 1 ) m ( m + 1 ) ( m + n m 一1 ) 显然，当1 sk m ，n m 时， 一k + ( 胛一m ) m + n 一n 一1 ， m k t - 1 m ，m k + 2 m + 1 ，一 m + 1 c w 一， ： 一。r e 。+ + ，1 ) ， 即， w l ，这与引理2 2 3 矛盾。故假设错误，所以w = 1 。即世只有一个连通 片，也就是说足是( m ，n ) 一连通的。 ( 2 ) 当m 1 ，由于m 1 ，因此有， w 一1 。这 与， w 矛盾，故w = 1 ，从而也可得k 为( m ，i 1 ) 一连通。 综合( 1 ) ，( 2 ) 两种情况，可得x 是( m ，n ) 一连通的，所以k 是一个( m ，l q ) 一树。 证毕。 尽管猜想( 1 ) 不成立，但是d e w d n e y 似乎早有预知，为此，他在提出猜想( 1 ) 之后，又提出了比猜想( 1 ) 条件更强的猜想( 2 ) ： 猜想( 2 ) “1 一个纯，z 维复形k 是一个( m ，n ) 一树当且仅当它满足以下两个条 件：( i ) k 不含( m ，n ) 一回路。 ( i i ) 对所有的k ，l k 聊，都有：瑾i ( k ) = b m , n ( 七，世) 成立。 三( m ，n ) 一树的计数 顶点标号的( m ，r l 卜树的个数，称为( m ，n 卜树的数。自d e w d n e y1 9 7 4 年在1 1 中首先提出( m ，n 卜树的概念以来，国内只有毛经中教授和柳柏濂教授分别在【4 】和 5 中对其进行了研究，但他们研究的都是( m ，n 卜树结构和性质。本节主要研究的是 ( m ，r l 卜树的计数，得到了顶点标号的( m ，n ) - 树的计数公式。 另外，从超图的观点来看，( i n ，n ) - 树也是一种特殊的超树。因此，我们也从胛 维复形的领域，独立地得到了【l o 】中的结果。 本节我们先给出( n l ，n ) 一树的图论定义，然后再用组合的方法得到了( m ，n 卜树的 计数公式。 3 1 ( m ，n ) 一树的图论定义 由图论中的知识我们知道：由n 个互相邻接的顶点组成的图称为n 阶完全 图。下面我们将完全图的概念应用到( m n 卜树的定义中去。首先引入以下定义： 定义1设k ，l 都是完全图，则k 邻接l 是指将k 中的每个顶点与l 中 的每个顶点互相邻接，同时也称k 与l 是互相邻接的。 n j“卜v等。i 柳_ 一一西一o 。h 显然，由两个相邻接的完全图组成的图还是一个完全图。 下面我们先来看一类特殊的( m ，n 卜树即k 一树的定义。在【8 】中，l w b e i n e k e 和r e p i p p e r t 是这样使用归纳原理定义k 一树的：有k 个互相邻接的顶点的图称为 一个k 一树，而具有( n + 1 ) 个顶点的k 一树是指将第n + 1 个顶点与具有h 个顶点的k 一 树中某一互相邻接的k 个顶点中的每一个顶点相联结而得到的。按照这一归纳定 义，则不难类似地给出如下的( m ，n ) - 树的定义：我们称具有m + 1 个互相邻接的顶 点的完全图是一个( m ，n ) - 树，而具有口。个顶点的( m ，n ) - 树是将含有n m 个顶点的 完全图与具有a 。一一肌) 个顶点的( m ，n 卜树中的某一个含有( m + 1 ) 个顶点的完全 子图相邻接而得到的，( 其中口。2 n + 1 ，且口。一m l 整除疗一m ) 。很显然，k 一树的 定义实际上是( m ，n ) - - 树的定义的一种特殊形式。对于k 一树，每次是增加一个顶点， 而对于( i n ，n ) - 树，每次是增加一个具有n m 个顶点的完全图。另外，通过对比以 上定义与( m ，n ) - 树在【l 】中的定义可知：此定义与( m ，n ) - 树在单纯复形上的定义是 等价的，( m ，n ) - 树中的复形相当于以上定义中的完全子图，而单形则相当于以上定 义中的完全子图的顶点集的子集。因此，对于( m ，n ) - - 树，每增加一个含有m 一肌1 个 顶点的完全图，即相当于原来的( m ，n 卜树基础上增加了一个玎维复形。 3 2 ( m n ) 一树的计数公式 定义2 设k 是一个完全图，l 是k 的一个完全子图，且k 被标根在l 上，则 称l 是k 的标根完全子图。 现用c 卅。( 口。，x ) 表示具有口。个顶点，且标根在某一含有m + 1 个顶点的完全子 图上，并且有x 个由n m 项点组成的完全子图与之相邻接的( m ，n ) - 树的数。( 即在 此( m ，n ) - 树中，标根的完全m 维复形正好是x 个n 维复形的交) 。其中 1 m + l 一树，结论( 1 9 ) 式都成立，则 对于顶点数等于口。的( m ，卜树，首先由( 2 0 ) 式我们可得： 隆 c 。氓= 莩脚s - x ”叫胁h 凹， c 。( z ) = 巳。( 一驯) ：川x ( 2 1 ) i t il | 、“， l 而由归纳假设可得： c ”2 南鲤雌f 1 肚叫( 加叫十僻， 将( 2 2 ) 式代入( 2 1 ) 式得 巳一( 口。，x ) 2 j l 飞( 竺a ：o ：- ：d ：z 篁。一1 。，飞( a 竺：o 竺- ：x ：a ：! - ：d ! ! 、l s - - ，一x ，- - 1 ) 。 c s x ，( ：) 一c s x ， 5 。吖 ： 一 x 2 丝型器志瞄1 h c s x ，( ： 一c s x ， 3 一 ( ：) 一- x ) ” =(口，：?-，三，口罢s-?x丽1-(s-，一x。-1(：一， 了i 一 卜，x ， 5 一。 ：) z ) 一。 2 鹾氍一懿- - _ x - - h 制邯叫广 心斗 f - 1 令f = t 一1 ，则上式化为。 簧( ： ( ： 一t 蒿1 ( s 一歹一1 ) c s x ，( ： 一c s x ， 3 一。1 小 f 2 邕妊撒h s ( ：) 趔托嫩爿 s 5 s r 故此时( 1 9 ) 式也成立。因此由归纳法原理可知，结论成立。证毕。 - 2 i 疋j ；呈3 22 砹吃，。( ) 表不 页点数为的( m ，n 卜树的数，若 l 1 9 l + 1 n + 1 口。，贝0 有 吃，c 口。，= 击( 岛以一，：口。一) 厂s ( ： 一s + ， 5 c z 。， s + 1 i 证明：先设r 。似。) 表示标根在任一由沏+ 1 ) 个互相邻接的顶点组成的完 全子图上帆m ，渊的数。掣蝴o ) 的含义确 且”( 2 萎c 一z ) 由于在一含有个顶点的集合中选择d 个顶点的方法数为【0j ，故( ：) 月。 。) 表示具有口。个顶点，且标根在一个确定的由m + 1 个顶点- 组- 成的完全子图上的 文a s + - c 即为c m ，n 卜树中的所维单形的个数，个由m + 一个顶点组成的完全子 图。故我们可得： ： r 。 。，= s ( a s + - 吃“，。由此可得： 引2 黼， 又由于 卧= 瞧去璧薹：一s r 2 幽斌：嫩州“1 令z = x 一1 ，则上式可化为： ( 啦廖护( ”叫瓤1 托) 一s r 鬲f = 蚓批一r 眦胎引批) m ，r 弹 我们知道，当”= 1 ，m = 0 时，( m ，n 卜树便是我们图论中一般的树，此时( 2 3 ) 式为b o l ( 口o ) = 口o “一，这便是树的c a y l e y 计数公式( 见【1 2 ) 。当h = 2 ，m = 1 时， 此时的( m ，n 卜树便是2 一树，( 2 3 ) 式变为b 2 , 1 以。) = l0 ( 2 一3 户。，这便是顶点 标号的2 一树的计数公式( 见 1 4 ) 。进一步推广下去，当胛= i ，m = k l 时，此时的 ( m ，n 卜树便是一树，( 2 3 ) 式变为b 一( ) = i 擘1 仁一t 2 + 1 广。“，这便是顶点 “ 标号的k 一树的计数公式( 见【8 ) 。 对照超图的概念( 【1 0 ) ，本节的结论也可以认为是在h 维复形的领域独立地 得出了标号匀称超树的计数结果( 见 1 0 】) 。 四今后工作的展望 最后，我们来展望一下有关( m ，n 卜树及其相关数学结构在今后的研究方向与 发展趋势。 首先，我们想知道文中的猜想2 是否成立? 但是到目前为止，还无人提出反 例。然而要想证出猜测想2 也不是那么容易的。我认为，它不但与复形理论有关， 同时也可能牵涉到集合论与超图理论。因此，如果在复形中证不出，我想也许可 以用集合论与超图的有关结论试着去证明。如果猜想2 成立，将不仅会进一步完 善( m ，r l 卜树的结构理论，同时还会进一步完善超图的有关理论。另外，即使猜想2 不成立，但通过对其研究，或许可以得到其它的相关结论。因此我认为这是今后 研究( m ，n 卜树的一个重点。 其次，( m ，n _ 卜树与超图的关系问题也是一个值得我们关注与探讨的问题。实 际上，( m ，n ) - 树与超图有许多相似点，由于超图的相关结论较多，因此我认为可以 将超图中有关结论应用n ( m ，n 卜树的研究中去。这或许也是研究( m ，n ) 树的一个非 常好的思路与方向。 最后，有关( m ，n 卜树的计数问题，也是( m ，n 卜树今后研究的一个重点。本文我 们只是用组合的方法得到了顶点标号的( m ，渊的计数公式，面对于顶点没有标号 的( m ，n ) - 树的计数公式，到目前为止，还没有什么结果。由于( m ，1 1 卜树的结构很有 规律性，我想，用组合的方法与图的计数理论是可以得到其计数公式的。 以上只是我个人的一点看法，仅供参考。 参考文献 1 d e w d n e y ，a k h i g h e r d i m e n s i o n a l t r e es t r u c t u r e s j c o m b i n a t o r i a l t h e o r y ( b ) ，( 1 9 7 4 ) 1 7 ，1