（概率论与数理统计专业论文）可分解层次模型.pdf

摘要 本文主要研究了可分解层次模型的一些性质，首先研究的是可分解的生成类，得 出了生成类c 是可分解的当且仅当c = k ( o ( c ) ) ，且g ( c ) 为可分解的结论，接下来利 用可分解的生成类超图的超边分解，给出了生成类c 的一种递归分解，这种分解使得 c 恰好分解为所有由生成元诱导的子生成类的直和，最后我根据c 的上述分解给出了 可分解层次模型的估计与检验的最简单形式。本文还研究了生成类树的渡性，传交性， 导出子树性，以及它们之间的关系。 关键词：可分解的生成类；超边分解；可分解的生成类超图；生成类树； 估计；检验 a b s t r a c t t h i sp a p e ra i m sa ts o m ep r o p e r t i e so fd e c o m p o s a b l eh i e r a r c h i c a lm o d e l f i r s ti d i s c u s s e dt h ed e c o m p o s a b l eg e n e r a t i n gc l a s sa n dg e tt h a tci sd e c o m p o s a b l ei fa n do n l y i fc = 女( g ( c ) ) a n dg ( g ) i sd e c o m p o s a b l e t h e nig a v ear e c u r s i o nd e c o m p o s i t i o no fc b yt h eh y p e r e d g ed e c o m p o s i t i o no fad e c o m p o s a b l eg e n e r a t i n gh y p e r g r a p h b yt h i s r e c u r s i o nd e c o m p o s i t i o ncc a nd e c o m p o s ei n t oa l lo f t h es u b g e n e r a t i n gc l a s si n d u c e db ya e l e m e n to fc a tl a s tig a v et h em o s ts i m p l er e s u l to fe s t i m a t i o na n dt e s tf o ra d e c o m p o s a b l e h i e r a r c h i c a lm o d e l ia l s od i s c u s s e dt h e j u n c t i o np r o p e r t y , t h e i n d u c e d s u b t r e ep r o p e r t y , t h er u n n i n gi n t e r s e c t i o np r o p e r t yo fag e n e r a t i n gc l a s st r e ea n d t h er e l a t i o n s h i pa m o n gt h e m k e yw o r d s ：d e c o m p o s a b l eg e n e r a t i n gc l a s s ；h y p e r e d g ed e c o m g o s f f i o n ；d e c o m p o s a b l e g e n e r a t i n gh y p e r g r a p h ；g e n e r a t i n gc l a s st r e e ；e s t i m a t i o n ；t e s t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东北师 范大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：李群聋日期：丝卑。1 6 。丛 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位 论文的规定，即：东北师范大学有权保留并向国家有关部门或机 构送交学位论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权东北师范大学可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编 学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：耋娶象指导教师签名：k 耋錾 日 期：迎21 1 幺鸱日期：2 业正! 学位论文作者毕业后去向： 工作单位：凌e 型垒垃坐盗随 通讯地址：薹b 划荤苤出面蕴面l 蔓 电话妨2 6 1 ! 五9 歹 邮编：鲤! 些! 第1 章引言 层次模型是随着网状数据的出现而出现的，对于多维数据我们可以采用列联表表 示，d a r r o c he ta 1 定义了列联表上的图模型。 设r 是变量的分类的集合，c 是生成类( r 上的互不相容的子集组成的集合类) 。 p 碍营l o g p ( o = 疙( o ， r 其中无= 0 ，除非j c e ，使得口c 。 称露为对应于生成类c 的层次模型，这样又给出了列联表上的层次模型。 g ( c ) = ( r ，e ( c ) ) 是层次模型的图表示且尼为包含层次模型r 的最小的图模 型，这样图模型上的理论全都可以推广到层次模型上，从而得到了层次模型的估计： 在见中有且只有一个壹满足方程p 也) = n ( o n ，c c ，互，且声为极大似然估计。 层次模型的龇_ 2 1 。g 2 = 军警豢盟，缸瓦则_ 2 l o g q 钌- 检 验都是渐进z 2 一分布，其自由度为d i m ( p c ) - d i m ( p c ) 进一步还得到了： 若生成类c = 巴。g ，层次模型的极大似然估计：p ( 。= 堡紫。 设c = 乞o g ，对应的岛= g 。0 c o 。，层次模型似然比检验： - 2 1 0 9 q = ( 一2 1 0 9 q ) + ( 一2 l o g q ) ， 其对应的z 2 - 检验为：z 2 * z + z 。 可分解的生成类c 对应与可分解的层次模型，关于生成类e 的分解我们已经知道 生成类c 是可分解的当且仅当c = 女( g ( c ) ) ，且g ( c ) 为可分解的。 但是如何找到可分解生成类c 的一种递归分解，使得c 恰为所有由生成元诱导的 子生成类的直和? 以及在这种分解下可分解层次模型的估计与检验又是什么形式 呢? 这就是本文所研究的问题。 第2 章可分解层次模型简介 2 1 可分解层次模型的基本概念 定义2 1 1 层次模型( h i e r a r c h i c a lm o d e l s ) r 是变量的分类的集合，c 是生成类( 1 1 上的互不相容的子集组成的集合类) 。 p b l o g p ( f ) = 疙( f ) a g g 其中丸- = 0 ，除非j c c ，使得a c 。 称只为对应于生成类c 的层次模型。 记忍= p ( 训p ( f ) = l i r a p “( 耽其中p ”( f ) 忍 定义2 1 2 层次模型的图表示：g ( c ) = ( f ，e ( c ) ) 喜e 中 口，) e ( c ) 3 c c ，使得 口，) c 。 注1 ：层次模型图模型 证明：当c 是图g = ( r ，d 的团集时，与c 对应的层次模型与由图g = ( r ，d 给出的图模型相同。 注2 ：尼( 。) 为包含层次模型弓的最小的图模型。 证明：( 1 ) 证明忍忍( c ) 。 v p 忍营l o g p ( i ) = 疙( f ) ，其中丸= - 0 ，除非了c c ，f f 得a c _ c ， 口r 而若j c c ，使得口c ，则口在g ( c ) 中是完全的。从而有：l o g p ( i ) = 屯( f ) ，其中 a t g r 丸= - 0 ，除非口在g ( c ) 中是完全的，即p 尼c ) ，所以忍尼( c ) 。 ( 2 ) 证明图模型尼( c ) 是包含层次模型r 的所有图模型中最小的。 用反证法，假设存在一个更小的图模型碍朋，使得忍三) 尼( o ，故 了p 尼( c ) 曩叫) ，使得l o g p ( f ) = 疙( f ) ，其中屯= - 0 ，除非口在g ( c ) 中是完全的。 a g g f 但同时由于，仨曰叫) ，故上述条件不成立，也即l o g p ( i ) = 丸( f ) ，但是3 口r ，口在 口r ( r ，d 中不完全，但也有屯0 成立。故必存在口，r ，使得 缸，所e ( c ) ，但缸，历正e ，又对p 尼，使得：l o g p ( f ) = 丸( f ) ，其中疙= - 0 ，除 q e 3 c c ，使得d c ，并且有欢。以( f ) o 。但另一方面由于缸，) 在( r ，d 中不完全， 故p 仨固。故忍名固与题设矛盾，假设不成立，得证。 定义2 1 3g 完全( g c o m p l e t e ) 对a c r ，若3 c c 使得a c c ，则称a 在g ( c ) 中是g 完全的。 注：g 完全必完全 证明：因为，若口r 是g 完全的，故3 c c ，使得a c ，故显然有 c a ，a ， 有缸，仍d e ，口，卢有边相连，即口是完全的。 但反之不成立： 例2 1 1r = 1 ，2 ，3 ，c = 1 ，2 ) ， 2 ，3 ) ， 1 ，3 ) ) ， 则g ( c ) = ( r ，e ( c ) ) ，如图2 1 1 所示，显然r 是完全的。但不存在c c 使得r c ， 故r 不是g 完全的。 1 尹1 图2 1 1 定义2 1 4 子生成类( s u b g e n e r a t i n gc l a s s ) v s r ，定义e = r e d c n s i c a ，称e 为生成类c 的子生成类。 引理2 1 1g 完全性具有遗传性。 证明：v s g f ，往i f f v a c _ s ，若口在g ( o 中g 完全，则口在g ( g ) 中也是g 完金 的，事实上，由于a 在g ( c ) 中g 完全，则了c c 使得口c ，又由c s 的定义，必定 3 c s g ，使得a g c s ，故a 在g ( c s ) j d s k 是g 完全的，得证。 定义2 1 5 生成类的分解( d e c o m p o s i t i o no f ag e n e r a t i n gc l a s s ) 若c = q o g c = q v g ，q g = c ) 。 其中g v q = ，e d g u q ) ，q g = r e d c l n c 2 ：c te g ，c 2 g ) 。 此时称生成类q ，g 是生成类c 的分解。 引理2 1 2 设a ，b g f ，且满足如下条件： ( 1 ) a u b = f ； ( 2 ) 3 c c ，使得a n b c ； ( 3 ) ( 口1 6 ) ( 6 口) i ( a n b ) g ( c ) 】； 此时有c = 巴o g ，并称此为图g ( c ) 的g 分解，简记为g ( c ) = g ( e ) o g ( g ) 。 证明：往证c = c o o 巴，只需证c = t v 0 ，c o g = 。 先r e ：c = 乞v 岛。 t ：h - t - ( a 1 6 ) u ( 6 口) i ( 玎n 6 ) g ( c ) 】，故口n 6 在g ( c ) 中分离口、6 与b a 。 圈2 1 2 如图2 1 2 所示：v 口a b ，b a ，口，不相连。即不j c c ，使得缸，历c _ c ， 故v c c ，都有f 口或者c b ，于是c e v 0 ，又由c a ，g 的定义，c d v g c ， 即c = 乞v g ，得证。 再证：乞 g = c + ，其中c f 。 由于了c c ，使得- a n b c ，又由乞，g 的定义，v 吒乞，c b 巴，显然n c 。 故可以找到这样的c 二乞，西g ，使得c n 矗在所有的巳n 中最大，取c = c 二nc ：， 显然c 满足： o ) v c o e ，气g ，有c 口n c ； ( 2 ) j z e ，岛，有c ：n o ；= c ； 即e ，、g = c ) 得证。 d 综上c = 乞e c , 得证 证明：因为若口n 6 是g 完全的，则其一定是完全的，但反之不成立。至于g 分解 与分解的其余两条都是一样的。 注l ：若g ( 乞) ，g ( g ) 是g ( c ) 的g 分解，贝e j g ( c o ) ，g ( g ) 也是g ( c ) 的分解，但反之 不一定成立。 注2 ：生成类c 的分解对应于g ( c ) 的g 分解。 定义2 1 6 可分解的生成类c ( d e c o m p o s a b l eg e n e r a t i n gc l a s s ) ，g 可分解的 g ( c ) ( gd e c o m p o s a b l eg ( c ) ) 生成类c 称为可分解的，若c = c ，或c = qo g ，且q ，g 均为可分解的营g ( c ) 为 g 可分解的，若g ( c ) 为g 完全的，或g ( c ) = g ( g ) o g ( g ) 且g ( q ) 、g ( 岛) 为g 可分解 的。 注：可分解的生成类对应于g 可分解的g ( c ) 。 定义2 1 7 可分解的层次模型( d e c o m p o s a b l eh i e r a r c h i c a lm o d e l ) 层次模型忍称为是可分解的，若其生成类c 是可分解的a 定理2 1 1g ( c ) 为g 可分解的铮c = 七( g ( c ) ) ，r g ( o 为可分解的。 证明：对j r i 用数学归纳法。当i f l - l 时，结论显然。现假设结论对i r l n 时都成 立。当l r l = n + l 时： “j ”，g ( o 为g 可分解的。若c = c ) ，结论显然成立。否则： g ( o = g ( g ) o g ( 岛) ，且o ( 0 ，g ( 岛) 为g 可分解的，其中g ( c a ) 2 ( r l ，e ( g ) ) ， g ( g ) = ( r ：，e ( 岛) ) ，r 。u r ：= r ，显然ir l j ) ，此时g ( c ) 如图2 1 3 所示，显然 c = 七( g ( c ) ) ，且g ( c ) 可分解，由定理2 1 1 知c 是可分解的，下面我们考虑c 的分解： 3 么 1245 图2 1 3 分解l ： c = 1 ，2 o 2 ，3 ，4 ， 4 ，5 ) = “1 ，2 ) ) o “2 ，3 ，4 o “4 ，5 ) 恰为所有由生成元诱导的子生成类的直和且不能进一步分解。 分解2 ： c = “l ，2 ，3 ) ) o “l ，2 ， 4 ，5 ， 2 ，4 = ( 2 ，3 ，4 l o 1 ，2 o ， 1 ，3 ) ) ) 。g ( h ) 如图2 2 1 所示，显然g ( ) = l ，2 ，3 ) ，且有 c i c g ( h ) 。 l 图2 2 i 性质2 2 1 ： ( 1 ) g 0 c g ) = g 。 证明：令g = ( 矿，e ) ，g ( c o ) = ( y ，e ( 肋) ) ，先证e c _ e ( 芄g ) ，v a ，卢v ，若 缸， e ，则j 七k ，使得 口，历k ，依定义有：缸，) e ( k 6 ) ，e e ( 肋) ， v 口，v ，若缸，历e ( 砭) ，故：i k e 使得缸，) k ，k 为e 的团集，故有 扣，) e ，即e ( z a ) e 。综上得证。 ( 2 ) 7 - t k ( ) ； 证明：只需证v 何，j 七砭( ，使得h c _ k ，事实上，对任意 盯，) h ，有 缸，历e ( 日) ，故 在g ( ) 中完全，所以3 k 砭( 肿，使得厅| 。得证。 ( 3 ) 巧j g ( q ) g ( 乜) ； 证明：v 口，v ，若缸，) e ( q ) ，则j 啊“，使得 口，) 啊，由于q ， 必存在，使得缸，历，即 口，厨e ( 凰) ，故g ( q ) g ( 马) 。得证。 但反之不成立。反例如下： 例2 2 2 ：设= 1 ，2 ，3 ) ， 3 ，4 ，5 ，7 ) ， 5 ，6 ，g ( q ) 如图2 2 2 所示a = l ，2 ，3 ， 3 ，5 ， 4 ，5 ，7 ) ， 3 ，7 ) ， 3 ，4 ， 5 ，6 ，7 ) ，g ( h o 如图2 2 3 所示。 黔， 图2 2 2 幽2 2 3 显然有g ( 珥) g ( h 0 ，但q 不成立 ( 4 ) g i g 2 营磁s k ； 证明： “j ”，v k , 镌，k l 在g 1 中完全，由于g l g 2 ，故如在g 2 中也完全，所以 j 屯k ，使得南屯，故k k ； “乍”，k k ，故v 毛k ，j 也k ，使得毛岛，所以若 口，历巨， 则一定有缸，所易，g l g 2 ，得证 ( 5 ) g ( v ) = g ( ) u g ( ) ； 证明：只需证e ( v ) = 三( ) u e ( ) 先证：e ( v ) e ( 巧) u e ( ) ； 对于v a ，历以v ) ，则必存在h 或h ，缸，刃h ，从而 缸，) 层( “) 或缸，历e ( ) ，即缸，) e ( q ) u e ( ) ，得证； 再证：e ( v ) e ( ) u e ( ) 。 若 口，) e ( ) u e ( ) ，故有似，历e ( ) 或缸，所f ( ) ，从而存在厅 或矗，即存在 v ，使得 口，历h ，因此缸，所e ( q v ) ，得证a ( 6 ) g ( a ) = g ( ) n g ( ) ； 证明：只需证e ( “a ) = e ( ) n e ( ) 。 先证：e ( ) 量( q ) n e ( ) ，v a ，卢) e ( ) ，则必存在啊， 吃，使得忸，) 啊n 吃，故有位，所e ( “) 且 a ，所e ( ) ， 缸， e ( “) n e ( ) ，从而e ( a ) e ( ) n e ( ) ； 再证：e ( a ) 2 e ( ) n e ( ) 。 若v a ，历e ( “) n e ( ) ，故有 口，历e ( ) ，弛，) e ( ) ，从而存在 啊，如，使得缸，) 啊n 嚏，因此缸，) e ( ) ， e ( “a ) 2e ( ) n e ( ) 综上得证。 ( 7 ) 证明：c ( g 1 ng 2 ) = i c ( g 1 ) a c ( g 2 ) ； 先证： i c ( g , n g 2 ) _ i c ( g 1 ) 瓦( g 2 ) ， 若k j c ( g , n g 2 ) ，k 是 g l ng 2 = ( k k ，置n 易) 的团，v a ，历七，有缸，历e n 最，显然七在g l ，g 2 中 完全，故了墨_ i c ( g 1 ) ，屯咒( g 2 ) ，使得k 南n 岛，事实上此时我们有_ i = 毛n 屯，否 则若_ i 南n 也，这与k 是g 1 ng 2 中的极大完全子图矛盾，所以k _ i c ( g 1 ) ，、_ i c ( g 2 ) ，故 c ( g , ng 2 ) 瓦( g 1 ) 足( g 2 ) ，综上即可得证。 再证：_ i c ( g 1 ng 2 ) 2 9 ( g , ) a c ( g z ) ，v 七尼( g 1 ) 瓦( g 2 ) ，存在毛( g 1 ) ， k 2 厄( g 2 ) 使得后= 岛n 如，显然k 在g l n g 2 中完全，只需证七是g l ng 2 中的极大完全 子图即可；反证法：若上述不成立，则3 k c ( g , ng 2 ) 使得k c k ，由于 ( g i ng 2 ) j i c ( g 1 ) ( g 2 ) ，则k 瓦( g 1 ) ( g 2 ) ，这与( g 1 ) 疋( g 2 ) 的定义矛盾， 故k 咒( g 1 n g 2 ) ，即瓦( g l ng 2 ) 2 ( g 1 ) ( g 2 ) 。 综上得证。 ( 8 ) ( g 1 ) v _ i c ( g 2 ) i c ( g lug 2 ) ； 证明：v k i c ( g , ) v i c g 2 ) ，b k 瓦( g 1 ) ( 或p c ( g 2 ) ，不妨设k 庀( g 1 ) ) ，对任 意口，j k ，则缸，) 巨，显然，缸，) 置u 最故七在g lug 2 中完全，所以 3 k 莨( g l u g 2 ) 使得七七，综上瓦( g 1 ) v ( g 2 ) s 尼( g l ug 2 ) ，得证。 定义2 2 6 虱( g r a p h ) 若i c ( g ( h ) ) h ，即爿= i c ( g ( h ) ) ，则称超图片是图。 注l ：团超图是图： 注2 ：若是图，则是g ( ) 的团超图。 伢2 2 3 设超图片= ( 1 ，2 ，3 ，4 ，5 ，6 ，7 ) ，“1 ，2 ，3 ，4 ， 3 ，4 ，7 ) ， 4 ，5 ，6 , 7 ) ) ，g ( h ) 如图 2 2 4 所示： 1 4 圈2 2 4 则尼( g ( 胃) ) = “1 ，2 ，3 ，4 ， 3 ，4 ，7 ， 4 ，5 ，6 ，7 ) ) ，爿= 瓦( g ( 日) ) ，由图的定义，超图日是 图。 引理2 2 i 若印，b ，c ) 为图g 的一种分解，则： c ( g ) = 咒( g u c ) o g ( b u c ) ) = g ( g ( a u c ) ) e k ( g ( b u c ) ) 证明：只需，g ( g l u g 2 ) s _ i c ( g 1 ) v _ i c ( q ) ，g l = g ( a u c ) g 2 = g ( b u c ) ，v 惫砭， 由，口，c ) 为图g 的一种分解及七的完全性知七a u c 或k b u c 所以| c ( g 1 ) ， 或j j c ( g 2 ) y , i l i i ( g l ug 2 ) = 足( g 1 ) v 咒( g 2 ) ，y 1 c ( g , ) a l c ( g 2 ) = c ) ，而c 完全，所 以砭= 咒( g ( 彳u c ) o g ( b u c ) ) = ( g ( 么u c ) ) o 咒( g ( 口u c ) ) ，得证。 推论2 2 1 如果生成类超图耳= ( 矿，q ) ，i = 1 ，2 均为图，则超图h = 0 4 也为 图。 证明：因为瓦( g ( 日) ) = i c ( g ( q ) ) o ( g ( 月j ) ) = g o 岛= c ，所以日也为图a 定义2 2 7 称生成类超图h = ( y ，c ) 为可分解的，如果日是简单的或者日能写成 两个可分解超图q 和马的直和，及c = q o 岛，其中i q i ，l g 阔c i 。 注：层次模型的生成类的可分解，生成类超图的可分解与g ( c ) = g ( ) 的g 可分 解三者是等价的。 定理2 2 1 生成类超图h = ( v ，c ) 可分解当且仅当月是可分解图g ( h ) 的团超图， 特别地，所有的可分解生成类超图都是图。 证明：由于层次模型的生成类的可分解对应着生成类超图的可分解，对于生成类 超图g ( c ) = g ( 日) 及c = 七( g ( c ) ) ，即日是g ( 日) 的团超图，所以定理2 2 1 与定理2 1 1 等价的，证明是类似的，此处不再证明。 注：基于定理2 2 1 与定理2 1 1 的等价性，前一节提出的问题2 1 1 就转化成了 这样一个问题：对于可分解的生成类超图，如何找到一种递归分解，使得生成类超图 h = ( v ，c ) 最后可以表示为由其所有的超边在日中的导出子超图的直和? 下一节我们 将研究这个问题。 2 3 超边分解 引理2 3 1h = ( v ，c ) 是一个生成类超图，且h = h ( a ) o n ( b ) 则以下结论成立： ( 1 ) v c c ，则c 口或c b 。而且c 相应的是h ( a ) 或h ( b ) 的超边； ( 2 ) c a n b ，c 是n ( a ) 或h ( b ) 的超边，则c 也是日的超边。 证明： ( 1 ) 用反证法：假设c 正a 且c 仁b ，则j a ( a b ) n c ，卢( 6 、a ) n c ，即 n ，卢) c ， 故a ，p 在g ( h ) 中也有边相连，这与h = h ( a ) o h ( b ) 矛盾! 从而c a 或c b ，而由 ( 口) ，h ( b ) 的定义c 相应的是h ( a ) 或( 6 ) 的超边，得证。 ( 2 ) 由c = c o e c , ，c 口或c b 以及c a n b 可知c 也是日的超边。 注：该引理给出了超边与生成类超图分解间的关系。 定义2 3 1 可分解的生成类超图h = ( v ，c ) 的超边分解 ( 彳，c ，b ) 将可分解的生成类超图日分解为h ( a u c ) 和h ( s u c ) ，如果这两个子 超图的超边互不相同，而且都是原超图日的超边。则称分解( a ，c ，b ) 为生成类超图h 的超边分解。分离子c 称为超边分解子。 注：由引理2 3 1 可得到可分解的生成类超图h 的超边分解的另一个等价定义： 分解( 4 ，c ，口) 为可分解的生成类超图日的超边分解，当且仅当c 不是h ( a uc ) 和 h ( b u c ) 的超边。 假设可分解的生成类超图h 被( 4 ，c ，曰) 分解为局= h ( a u c ) 和h 2 = h ( s u c ) ， 如果且和h ：还能被进一步分解，直到所有分解后的子超图都是的某些超边的子集 的导出子超图为止，称经过这样分解得到的日某些超边的子集的导出子超图为分解 系，如果一个可分解的生成类超图日被递归的进行超边分解，由超边分解的定义知道， f 2 最后得到的分解系必然是日的两两互不相同的超边的导出子超图。相反的，假如 ( 爿，c ，功将分解为喝和不是一个超边分解，即c 是目或日：的超边，但不是日的超 边。由引理的2 3 1 ( 2 ) 知，h = c ，由定义知该分解不是超边分解，因此得到如下命 题： 命题2 3 1 一个分解系恰好是可分解的生成类超图日的所有超边的导出子超 图，当且仅当所有的分解都是超边分解。 d - o r d e r e d 序在超边分解中起有关键作用。 c i ，c 2 ，c t v ，对t = l ，2 ，t ，记足= q f l ( q u c 2u u q 1 ) ，s = q 、置， 置，r ，辱) 称为c 1c 2 ，c t 的r - 系( r - s y s t e m ) 。 定义2 3 2d - o r d e r e d 序列 序列q ，乞，c t 被称为d - o r d e r e d 序列，如果对于任意的f = 1 ，2 ，t ，存在p t ， 使得r c p 。这样的序列q ，c 2 ，c r 也被称作是具有传交( r u n n i n gi n t e r s e c t i o n p r o p e r t y ) 的序列a 命题2 3 2 满足d o r d e r e d 的序列具有以下几个性质： 令c 1 ，乞，c 7 是一个d - o r d e r e d 序，则有； ( i ) 对l t t ，若存在最小的s ，s t ，使q 乞，那么有： ( 1 1 ) c l9 c 2 ，c i _ l ，c t + 19 9 c r 是一个d - o r d e r e d 序( 若s r ) ； ( i i ) q ，c 2 ，c r 的是d - o r d e r e d 序的不同排列有相同的r - 系； ( i i i ) 对每一个r ，t = 1 ，2 ，t ，都有一个排列圹： l ，2 9 - - , t ) 一 l ，2 9 - 9 t ，使 盯( 1 ) = t ，c o ( 1 ) 9 巳( 2 ) ，c o ( r ) 是d - o r d e r e d 。 证明见 2 第4 5 页。 定理2 3 1 对于可分解的生成类超图何的任何一个超边h ，都有一个日的超边 集c m ，c 2 ，c r 的序，使得c 1 ，乞，c t 是d - o r d e r e d 且c l = c 。 证明：对i 矿i _ 一运用数学归纳法。 当疗= l 时，显然成立。 假设对i v i r 时的可分解的生成类超图成立。当i v l = 拧时，若h 是简单的，结 论成立，否则设h = 日( 口) o h ( 6 ) 。由归纳假设知，对日( 口) 的超边集，存在一个 d - o r d e r e d 序4 ，4 ，4 。对日p ) 的所有超边集，存在一个d o r d e r e d 序 骂，岛，b p ，且使口n 6 马a 易知：4 ，4 ，4 ，且，8 2 ，也是d - o r d e r e d 。若日( d ) ， h ( b ) 是日的超边分解，则各个4 ，b ，都是h 的超边，得证。否则，若不是超边分解， 即c = a f q b 是h ( a ) 或h ( b ) 的超边，有两种情形： ( 口) c 在序列4 ，4 ，4 ，且，岛，吃中出现一次，且严格包含在该序y u f 朔- 个集合中： 或( ) c 在序列4 ，4 ，4 ，蜀，8 2 ，曰。中出现两次。 对这两种情况中的任何一种，据d o r d e r e d 序性质( i ) 都可将c 从序列中除去，而且除 去c 后的序列仍是d - o r d e r e d 。又由d - o r d e r e d 的性质( 3 ) 知存在一个日的超边集 q ，c 2 ，c t 的d o r d e r e d 序，使得q = c ，证毕。 推论2 3 1 ： ( i ) 若c 1 ，c 2 ，c t 是可分解的生成类超图日的超边集的d - o r d e r e d 序，则有 r l ( 4 ，c ，口) = ( 望q 、置，碍，s t ) 是h 的超边分解。 r i 它把h 分解为日( 爿u c ) = 日( u q ) 和 t = l h ( b u c ) = h ( c o ，c l ，乞，勺一1 是日( 一u c ) 的超边。 ( i i ) 若存在日的一个分解，则存在日的一个超边分解。 i 正n - ( i ) 由于q ，c 2 ，勺是d o r d e r e d ，则存在p t ，使得辱c 。，则由吩定 义可知目= c r n ，即 啦= c r f l c ，。又显然有h = v ，故 7 - t = u c o 只需证该分解是超边分解，事实上马= 白n c 。既不是日口u c ) 的超 边也不是h ( s u c ) 的超边，得证。 注：可递归地应用推论2 3 1 ，因为序列q ，乞，勺是d o r d e r e d 序，h ( auc ) 还 可以像h 一样分解下去，最终将日( q u c 0 分解为n ( c 。) 和n ( c o 。这样得到的分解系 恰好就是可分解的生成类超图日的所有超边的导出子超图的集合。因此，对可分解的 生成类超图日的超边的每一个d o r d e r e d 序，都相应地有h 的一种递归的超边分解， 将分解为它的所有超边的导出子超图的直和。另外由于生成类超图日的分解对应 于其g 成类c 的分解，故同时也相应的存在c 的递归分解，使得： 4 倒2 3 1 设生成类超图h = ( l ，2 ，3 ，4 ，5 ，“l ，2 ) ， 2 ，3 ，4 ) ， 4 ，5 ，) ) a 由前面的讨论知其生成类c 是可分解的，从而生成类超图日也是可分解的。且 q = 1 ，2 ) ，c 2 = 2 ，3 ，4 ，c ，= 4 ，5 l 是可分解的生成类超图日的超边集的一个d - o r d e r e d 序，由推论2 3 1 可做如下的递归分解： 日= 日( 1 ，2 ，3 ，4 ) ) 0 日( 4 ，5 ) ) = 日( l ，2 ) o 日( 2 ，3 ，4 ) o 日( 4 ，5 ) ) 这样日分解为它的所有超边的导出子超图的直和。对c 可做同样的递归分解： c = “1 ，2 ) ， 2 ，3 ，4 ) o “4 ，5 1 = “1 ，2 ) o 2 ，3 ，4 ) ) o “4 ，5 ) 。 2 4 可分解层次模型的生成类树及其性质 定义2 4 1 生成类图 ( 1 ) 令s 是一个集，f = 强，曼，瓯) 是s 的不同的非空子集的一个非空有限族， 这些子集的并是s ，f 的交 虱( i n t e r s e c t i o n g r a p h ) ，记做q ( f ) ，定义为：矿( q ( ，) ) = f ， 当i ，时且s n s ，a 时，s ，s ，有边连接； ( 2 ) 给定层次模型的生成类c ，则c 的交图称为层次模型的生成类图； ( 3 ) 层次模型的生成类图的支撑树记为t = ( c ，耳) 。 2 4 1 渡性( j u n c t i o np r o p e r l y ) 定义2 4 2 渡性 可分解层次模型的生成类图的某一支撑树r = ( c ，日) 称为满足渡性，如果 ，c c ，且c c ，恒有树r 上连接c 与c 结点的( 唯一) 路上所有结点都包含子集 c n c 。 注：渡性又称为类交性( c l a s s i n t e r s e c t i o np r o p e r t y ) 。 记：刃”= t = ( c ，e 1 ) l 树r 满足渡性 。 定义2 4 3 联结森林( j u n c t i o nf o r e s t ) c 的联结森林定义为厂= z 为g 上满足渡性的树，其中，= 1 ，c = y c , ，v i ， 恒有 c ，= o 。 引理2 4 1 如果，为生成类c 的联结森林，贝t j v c , ，c 2 ，q c ：，将边 c l ，白) 在树r 中移去后，令q = 【c l 】，、h q ，g = c q ，则有c = q 0 岛。 证明：因为q 岛= r e d a n b i a q ，b g ) ，为c 的联结森林，v a q ，b g ， r a r l b o ，则q ，乞都在，上连接口，b 的( 唯一) 路上，由渡性，a n b c i n 乞，所以 q g = c 1 n c 2 ) ，又显然有c = g v g ，所以c = g o g ，得证a 定义2 4 4 极端生成元( e x t r e m a l ) 称生成元c c 为极端生成元，如果3 c c ，c c ，使得vc l c ，q c ，恒有 c l n c c n c 。 注：c 实为某一满足渡性的树的叶子结点，c 为c 在这棵树上的父结点。 例2 4 1 设层次模型的生成类为“l ，8 ) ， 1 ，2 ，3 ) ，( 3 ，4 ， 4 ，5 ，6 ，7 ，其对应的生成 类图如图2 4 1 所示： 图2 4 1 对生成元c = l ，8 ) ，存在生成元c = 1 ，2 ，3 ) ，使得c 满足极端生成元的定义，即 c = 1 ，8 ) 为一个极端生成元。对生成元c = 4 ，5 ，6 ) ，存在生成元c = 3 ，4 ) ，使得c 满足 极端生成元的定义，即c = 4 ，5 ，6 为一个极端生成元。 进一步上图本身就是c 的一棵满足渡性的树，极端生成元 1 ，8 ， 4 ，5 ，6 ) 为其叶子 结点，生成元 1 ，2 ，3 ) ， 3 ，4 ) 分别为其对应的父结点。 定义2 4 5 连通层次模型( c o n n e c t e dh i e r a r c h i c a lm o d e l ) 若层次模型的图表示g ( c ) 是连通的，则称层次模型是连通的。 引理2 4 2 如果连通层次模型的生成类c 是可分解的，且l c p l ，则至少存在c 的两个极端生成元。 证明：对l c i 用数学归纳法。 证明：对| c l 用数学归纳法。 当i c l = 2 时，c = c 1 ，c d ，由定义，g ，巳均为极端生成元，现假设对i c l _ n - 1 时 结论都成立，当i c l = n 时，由于c 是可分解的，c = 乞o g ，且乞，g 都是可分解的， 且l 乞i _ n - 1 ，i 己峰n - 1 ，由归纳假设，要么i 乞j - 1 ，此时由于巴 g = a f l b ，c 口为c 的极端生成元，要么l 乞p 1 ，由归纳假设，c o 中至少存在两个乞的极端生成元q ，c 2 ， 且至少有一个不妨设为g 使得c l c _ ak b ，则c i 也为c 的极端生成元。对g 进行类似讨 论就可以至少找到c 的两个极端生成元，得证。 注：此性质实质上是对阶数大于l 的弦图至少有两个不邻单纯点的推广。 定理2 4 1 连通层次模型的生成类c 是可分解的当且仅当存在c 的一棵满足渡 性的树。 证明：对阶数i c i 用数学归纳法，当i c l _ 1 时结论显然成立，现假设结论对 2 q c 喀胛的层次模型都成立，下面考虑l c 降n + l 的情形。 “仨”，设t = ( c ，西) 是满足渡性的树，任取c 为树r 上的叶子结点( 总存在) ，其 邻接点为c ，在树r 中删去叶子结点c 得到树t = ( c 。，以r ) ) 其中c = c 、 c ) ，显然树， 满足渡性，且由渡性的定义c c ) = c n c ) ，且c = c v c ) ，故c = c o c ，又由归 纳假设c 可分解， c ) 也是可分解的，所以c 是可分解的，得证。 “j ”，生成类c 是可分解的，由引理存在一个c 的极端生成元c ，即3 c c ，c c ， 使得v c l c ，q c ，恒= f i g f l c c _ c n c 。 考虑c = c c j ，c 也是可分解的，由归纳假设，存在一棵c 的满足渡性的树z ， 且使得c 为树r 的叶子结点，可如下构造树r ，在树丁上增加一个结点c ，和一条边 c ，c ) ，则由极端生成元的定义之知r 是可分解生成类c 的一棵满足渡性的树，得证。 由定理2 4 1 知，若生成类c 是可分解的，j 甲囝，对任意非空的t 踏，称 r 为生成类c 的一棵联结树( j u n c t i o n t r e e ) 。 2 4 2 导出子树性( i n d u c e d - s u b t r e ep r o p e r t y ) 设层次模型的变量集为r ，对任意的v f ，记 c ( v ) = c c i v c ) 。 定义2 4 。3 连通层次模型的生成类图的某一支撑树t = 形，e r ) 称为满足导出子 树性( i n d u c e d s u b t r e ep r o p e r t y ) ，如果v v r 恒有c ( v ) 都导出丁的一棵子树( 即r ( c ( v ) ) 连通) 。 记：刀= t = ( c ，e r ) i 树r 满足导出子树性) 。 定理2 4 2 对任意连通层次模型，恒有c ”一- - 咒 证明：先证以9 刀，v 刀，v v e f ，考虑c ( v ) ，v c ，c c ( v ) ， 为c f l c 包含在上& c 至t l c 的路上的所有结点中，所以v v c n c ，恒有v p ，