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

摘要 本文定义了图的p g - 分解，层次模型生成类和层次模型超图的分解，研究了 超图的一种分解子有特殊性质的分解一素分解( p - 分解) ，这种分解的特点是不会 产生新的极大素子超图( m p - 子超图) 分解最终得到的分解系是最小的，恰好是 原超图的全部极大素子超图 有了超图的紊分解，层次模型参数的极大似然估计就可以在各个极大素子超 图的子层次模型上来完成本文通过超图全部极大素子超图的d - o r d e r e d 集列给出 了超图的素分解，任何一个超图都可以成功分解为它的全部极大素子超图组成的分 解系超图的裹分解子就是关联图p g - 分解的p g - 分解子 关键词层次模型；生成类；超图；m p - 子超图；素分解( p _ 分解) ；素分解 子( p - 分解子) ；d - o r d e r e d 集列；g - 完全；g - 分解；p g - 分饵子 a b s t r a c t t h ep g - d e c o m p o s i t i o no fg r a p ha l s od e c o m p o s i t i o n so fg e n e r a t i n gc l a s sa n dh y p e r - g r a p ha x ed e f i n e di nt h i sp a p e r d c o m p o s i t i o n so fah y p e r g r a p hb ys e p a r a t o r sw i t hs p e c i a l p r o p e r t y ( p - d e c o m p o s i t i o n ) a r ei n v e s t i g a t e dw h i c hh a v ea d d i t i o n a lp r o p e r t yt h a tt h e yd o n o tg e n e r a t en e wm a x i m 丑lp r i m es u b h y p e r g r a p h s ( m p - s u b h y p e r g r a p h s ) s u c hd e c o m - p e s i t i o n sl e a dt o8m i n i m a ls y s t e mo fd e r i v e ds u b h y p e r g r a p h s j u s ta l lo ft h e 扣址u d m a l p r i m es u b h y p e r g r a p h sc o m p o s et h ed e r i v e ds y s t e m t h el i k e l i h o o dm a i x i m a le s t i m a t i o nc a nb ec o m p l e t e do ns u b - h i e r a r c h i c a lm o d e l s a t t r i b u t i n gt ot h ep - d e c o m p o s i t i o no fh y p e r g r a p h p - d e c o m p o s i t i o n sc a nb es p e c i f i e d t h r o u g had - o r d e r e ds e q u e n c eo ft h em a x i m a lp r i m es u b h y p e r g r a p h e ，i nt h i sp a p e r s h o wt h a te v e r yh y p e r g r a p hhc a ns u c c e s s i v e l yb ed e c o m p o s e ds u c ht h a tbu n i q u em i m m a l s y s t e mo fp r i m es u b h y p e r g r a p h si sd e r i v e dw h i c hi st h es y s t e mo fm p - s u b h y p e r g r a p h so f h t h ep - s e p a r a t o ro fah y p e r g r a p hi st h ep g - s e p a r a t o ro ft h eg r a p h k e y w o r d slh i e r a r c h i c a lm o d e l s g e n e r a t i n gc l a s s ；h y p e r g r a p h ；m p - s u b h y p e r g r a p h ；p - d e c o m p o s i t i o n ；p - s e p a r a t o r ；g - c o m p l e t e ；c - d e c o m p o s i t i o n ； p g - s e p a r a t o r ；d - o r d e r i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东北师范大学或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：主意，玉日期： 学位论文版权使用授权书 本学位论文作者完全了解东北师范大学有关保留、使用学位论文的规定，即：东 北师范大学有权保留并向国家有关部门或机构送交学位论文的复印件和磁盘，允许论 文被查阅和借阅。本人授权东北师范大学可以将学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其它复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：五盘! 圣 日 期：湖，噬，堕 学位论文作者毕业后去向： 工作单位： 通讯地址： 指导教师签名： 电话： 邮编： 引言 列联表的图模型借助于图的分饵理论，将统计估计和检验同题降低到边缘表的 图模型上来完成列联表图模型的参数估计( 极大似然估计) 可以分别在两个分解 后的子图的图模型上完成对于嵌套的图模型的似然比检验而言，统计量的分解又 具有一些与图的分解相关的特性，可以利用图的分解给出似然比检验统计量的一种 分解，可以通过了解图的性质对原统计量进行图的意义下的分解，得到若干统计量 的和，这些统计量是渐进独立且具有渐进卡方分布的统计量，并且这些统计量渐进 卡方分布的自由度的和等于原统计量渐进卡方分布的自由度 b i s h o p ，f i e n b e r ga n dh o l l a n d ( 1 9 7 5 ) 关于列联表对效线型模型的经典著作，定理 2 4 - 1 处理了三维表的叠合变量3 对于1 、2 的交互是可折叠的，只要变量3 与变 量1 或变量2 不相连，或者与它们两个都不相连对三维表而言存在可折叠的变量 时至少由一个两因子不出现分割。将数据按某一变量分类划分，对每段数据拟合 的是列联表的个轮廓( 边缘表) 使被拟合的轮廓维数降低 所考虑的叠合、分割事实上就是模型分解想法 l a u r i t z e n ( 2 0 0 2 ) 给出了基于图分解的层次模型生成类分解思想，相应于生成类 的分解有层次模型的分解 模型分解后不仅降低了变量维数，提供了一种处理高维数据的办法而且；边 缘表中每个格子中的频数是原表格中某些格子频数的加和，使得基于大样本的推断 更可靠对于检验而言，分步检验提高了检验的势 l e i m e r ( 1 9 9 3 ) 年论文给出了一般图素分解算法和结果本文的目的是要将图模 型的素分解推广到层次模型图模型中条件独立性与图的分离性相等价层次模型 生成类关联图相应的图模型，是包含层次模型的最小的图模型研究层次模型分解 要借助于生成类的超图分解 本文定义了层次模型生成类超图和超图的分解，在第二章中研究了生成类的分 解、超图的分解与图的g - 分解之间的等价关系，超图的( 极大) 索子超图与超图分 解间的关系第三章提出超图素分解的概念，依据极大素子超图的d - o r d e r e d 集列 1 给出紊分解过程，超图的素分解将它分解为的全部的极大素子超图，刻画了超图素 分解子的性质以及与图的素分解子的关系证明了超图h 的素分解与所定义的关 联图g 的p g - 分解是相互等价的超图的素分解子就是关联图g 的p g - 分解子 有了超图的素分解，第四章将层次模型参数的极大似然估计降低到在各个极大 素子超图的子层次模型上来完成 2 一、基本知识与记号 用v 表示些分类变量的集合，v 是有限的，i v l 表示v 中变量的个数，对任意 的r e v ，r 的阶层j r 也是个有限的集合列联表中的一个单元格记为i = 体) r y ， 这里e l = r e y f r 假若有n 的对象被分类n ( i ) 记被分到i 单元格的对象的个 数所有的n ( i ) 组成的集合构成了一个列联表n = n ( t ) 分类变量的个数l v i 称为列联表的维数边缘表仅考虑某些分类变量a c _ v 将n 个对象分类边缘表单 元格缸= 佴) m ，i a l 。= x r e a l r 相应的边缘表单元格中的对象数n ( 乱) - 单元格 豇中的对象数= en j ，a = “ 用p ( i ) 表示个对象被分到单元格i 中的概率，p c i ) 0 ，p o ) = 1 如果样 本总数n 是固定的，整个表上的联合分布是多项分布- p 州o a ) ，往工) 。丽羞丽耳烈习哟 边缘概率p ( 如) = 一个对象被分到边缘表格l 。中的概率= p u ) j 巧o = “ ( 列联表的) 生成类彤有关的层次模型( h i e r a r c h i c a lm o d e l s ) ：。形是一个已 有的生成类( 定义2 1 1 ) ，j 护对应的超图( 定义2 2 1 ) 是h ，矿舻是分类变 量集v 的列联表上联合分布的集合p e 尹帮当且仅当l o g p ( i ) = 仇( t ) 其中 a _ c y 0 ，除非存在h 形，使得d h 称使一个与生成类第有关的层次模型 用二元组g - - ( v ，e ) 表示一个无环，没有重边的简单无向图，其中t ( 1 ) v 称为图g 的结点( 顶点) 集( v e r t e xs e t ) ，n f l v i 是有限的； ( 2 ) e v x v 是诸结点之间的边的集合，称为边集( e d g es e t ) v e e ，e = ，t ，) ，t ，口v 称e 为以u 和v 为两端点的无向边u ，v v ，g 中u ， v 问的一条路是指一个结点序列t v o ，。1 ，t j 2 v ，满足； u ，口) = 枷， ， 一1 ，q ) e( i = 1 ，e t ) 3 对任意的o e v ，a 的邻集( s e to f n e i g h b o r s ) 定义为 n e ( a ) = v ：影口， 口，q ) e ) 对任意的a c v ，a 的邻集定义为 n e ( a ) = um 缸) a a e a 接触点集( v e r t i c e so fa t t a c h m e n t ) i 称s _ c v 为g s 的连通子图x 的接触点集或称s 与x 接触，若s = n e g ( s u x ) ( x ) ， 即对任意的a s ，存在卢x ，使得 a ，卢) e 记u 为图g 结点集v 的子集合，称g ( u ) = ( u ，e ( u ) ) 为u 在图g 中的导出 子图( i n d u c e ds u b g r a p h ) ，其中e ( u ) = “，口) e ：“， 研若u 中任意两个 结点之间都有边相连，即tv 口矾 e 则称u 为完全的( c o m p l e t e ) 特别的，空集0 是一个完全集若图g 的顶点集v 是完全的，则称g 是完全图 图g 的分离子( s e p a r a t o rh 如果在图g 中删去子集s c _ v 后，图的连通分支数增加了，则称s 为图g 的 ( 点) 分离子( v e r t e xs e t ) ，又称s 为图g 的( 点) 割集( v e r t e xc u ts e t ) ； 对u ，v e v ，若存在s g t ， ) ，使得任一条u 到v 的路都经过s 中某点， 则称s 为图g 的一个u v - 分离子( u v - s e p a r a t o r ) ； s c _ v ，a ，b _ c v s ，且a n b # o ，v u e a ，v e b ，若图g 中u ，v 间的任何一 条路都经过s 中某点，则称s 是g 的个a b - 分离子，又称s 在g 中分离a 和b 图g 的分解( d e c o m p o s i t i o n ) i 给定简单无向图g ，a ，b ，c 是v 的子集合且两两不交，满足以下两个条件， ( 1 ) a u b u c = v ； ( 2 ) c 是a ，b 的分离子； ( 3 ) c 是g 的完全子集； 贝0 称( a ，c ，b ) 形成了g 的一种分解，它将g 分解为两个子图e ( a u c ) 和o ( b u c ) ， 4 简记为g = g ( a u c ) o g ( b u c ) ，进一步，若a ，b o ，则称该分解为真分解( p r o p e r d e c o m p o s i t i o n ) 记a = a u c ，b = b u c ，通常也称8 ，b 为g 的一种分解 如果图g 包含有一个完全的分离子，存在一种真分解，称它是可约的( r e - d u c i b l e ) ，否则称为素的( p r i m e ) ，例如t 完全图就是一个素图 如果u 的导出子图g ( u ) 是素的，则称g ( u ) 是g 的索子囹，如果还有，对于 真包含u 的任何的集合x ，x c _ v ，x 的导出子图g ( x ) 都是可约的，那么称c ( u ) 是g 的个极大素子图( 或称素块m p - 子图) 图的素扩张定理f 1 】 给定简单无向图g = ( v ，e ) ，设x c v 在g 中连通，c c _ v 在g 中完全若 c 为x 的接触点集，则存在b ，使得c c b ，g ( b ) 为g ( c u x ) 的一个素子图 在许多问题的证明素扩张定理起着关键性的作用，它是个很本质的定理 可分解图( 也称之为弦图) 是一种特殊的图，可分解图中任意一个长度大于4 的 圈必有弦事实证明，弦图在图分解中最具有基础研究价值对于一般图的分解， 一般图的素分解，最终都要借助于弦图来解决 弦图本质的几个等价刻画【l l 。 ( 1 ) g 的任意相对极小分离子在g 中都是完全的； ( 2 ) g 是可分解图； ( 3 ) 存在g 的一个完美消无序； ( 4 ) 存在满足渡性的团树； ( 5 ) 存在满足导出子树性的团树； ( 6 ) 存在团集的一个d - o r d e r e d 集列 如何判定一个图是否是可分解的，若是，如何将它分解成所有团集( 极大素子图) 的直和的直和t a r j a n ( 1 9 7 6 ) 和t a r j a na n dy a n n a k a k i s c ( 1 9 8 4 ) 系统的考虑了这 一问题，给出了一个著名的算法一一最大基数搜索算法( m c s 算法) 对于弦图， 由m c s 算法给出的序为完美消元序，同时可得到一个有序的团集集列 5 对于不可分解图，即非弦图的一般图，自然考虑将图分解到不能再分解为止， 把图分解为若干个素子图的直和但是一般的分解并不能保证得到的子图都是原图 的素块( 或称为极大素子图m p - 子图) 如一 z345 g g 能分解为g ( 1 ，3 ，4 ) ) 和g ( 2 ，3 ，4 ，5 ) ) ，g ( 2 ，3 ，4 ，5 ) ) 最终又分解为g ( 亿3 ”， g ( 3 ，4 ) ) ，g ( 4 ，5 ) ) 但得到的子图g ( 3 ，4 ) ) 并不是原图的素块，而是包含在g 的素块g ( 1 ，3 ，4 ) ) 之中l e i m e r ( 1 9 9 3 ) 的著名论文就考虑了一种特殊的分解一 素分解( 1 - 分解) 从分解结果定义p - 分解t 若分解后的两个子图的素块互不相同，且都是原图 的素块，则分解是素分解 从分离子定义：因为图分解后的子图的非分离子的素块均为原图的素块，所以， 只要保证分解时的分离子不是任何子图的素块，分解就是素分解原图的任何一个 素块图都是分解后子图的素块图，因此，只要保证分解过程为p 分解，分解最后 得到的分解系( d e v i e ds y s t e m ) 就恰是原图的全部素块集 d - o r d e r e d 集列在素分解中起有关键作用 ，场y ，对拇1 ，t ，记岛= k f l ( m u u k 一1 ) ，忍= k 恼， 研s t ) 称为，b ，场的s - 系( s - s y s t e m ) ，特别的有岛= 0 ，岛= m 集列，许被称为d - o r d e r e d 集列，如果对于任意的t = 2 ，t ，存在p t ， 使这样的集列h ，许也被称作是具有传交性( r u n n i n g i n t e r s e c t i o n p r o p e r t y ) 的集列 满足d - o r d e r e d 的集列具有以下几个性质f 2 】， 6 令k ，k 硌是个d - o r d e r e d 集列，则有。 ( 1 ) 对1 t t ，若存在最小的b ，s t ，使k k ，那么有t ( i i ) h ，k “k + l 玢是d - o r d e r e d ( 着s t ) ； ( 2 ) h ，k 硌的是d - o r d e r e d 集列的不同排列有相同的s - 系 ( 3 ) 对每一个t ，t = l t ，都有一个排列口： 1 ，r + 1 ，r ，使 a ( 1 ) = t ，u ( 1 ) ( 是d o r d e r e d l e i m e r ( 1 9 0 3 ) 给出了一般图素分解的结果； 对于任意的可约图g ，考虑g 的全部m p - 子图，就存在一个m p - 子图的n o r d e r e d 集列，使得其相应的顶点集构成的集列为d - o r d e r i n g ，且h = u ，其中g ( u ) 为g 中任意一个m p - 子图给出可约图g 的m p - 子图的d - o r d e r e d 集列，就能递 归的将图素分解为其全部的素块图 论文中还给出了对p 分解子的本质刻画，e y 则以下性质相互等价， ( 1 ) c 是完全的，而且是g 的一个相对极小分离子； ( 2 ) c 是g 的可容许分离子； ( 3 ) c 是g 的p 分解子； ( 4 ) c 属于s - 系 ，s ) ； d a r r o c he ta 1 ( 1 9 8 0 ) 定义了关于图g 的列联表的图模型，在图g 上，每一个 点表示个离散的随机变量两个变量在图中无边相连等价于两变量间的条件独立 性图模型在很多自然科学领域有其本质的来源用图可以将模型很直观的表示出 来，从图上直接看出条件独立性，更方便统计学家和实际工作者之间的交流合作， 其结构的直观表示更有利于发挥计算机的强大功能图模型中图的分解是关键的， 分解后的子图保持了全图上的许多性质其中最根本的分离性质没有改变， 即- 若c 在原图中分离s t ，b ；则c 在子图中也分离a ，b ( abc 属于同一子图) 由 7 于分离性与条件独立性相等价，因此图分解保持所有变量间的条件独立结构不变 如果一个列联表图模型的图g 能分饵为两个子图c ( a ) 、g ( b ) 那么一个对象 被分到单元格i 的概率( 模型参数) 就能表示成两个子图上概率的乘积形式t p = 吲掣 列联表图模型的参数估计问题( 极大似然估计) 相应的也可以分别在两个子图上完 成，这就降低了变量的维数，提供了一种处理高维数据的办法 8 二、层次模型超图的分解 图模型中条件独立性与图的分离性相等价，层次模型的分解与超图的分解相关 联，给出超图之前先介绍生成类的概念 ( 一) 生成类与生成类的运算 定义2 1 1 生成类( g e n e r a t i n gc l a s s ) 用第代表由v 的一些子集构成的集合，即v h 彤，h y 且这些集合之 间两两互相不包含，则称彬为一个生成类，澎中集合h 称为生成元 定义2 1 2 生成类的运算 ( 1 ) 约化运算tr e d ( 澎) 指从j 纩中将包含在另个集合中的集合全部移去， 从而得到一个约化的生成类； ( 2 厢个生成类嬲和粥的联合运算镅v 嬲定义为t 嬲v 弼一r e d 嬲u 嬲) ； ( 3 ) 两个生成类的交运算嬲a 确定义为t 。嬲 。糍= r e d ( h l n 圯， 1 嬲，圯嬲 定义2 1 3 生成类的分解 若两个生成类嬲，嬲满足，彬= 嬲v 。糍，。辫 嬲= h ) ，则称生成类第 能分解为嬲和嬲简记为澎= 镅o 。税其中。嬲 。弼= h 包含了两个方面t ( 1 ) 对任意的h 嬲，如粥，h l n 的h ； ( 2 ) 弓h l j 缀，| h 2 纪，使得 l n 2 = h ( 二) 生成类的超图与超圈的分解 定义2 2 1 生成类。形的超图( h y p e r g r a p h ) 生成类的超图h 实际上是一个二元组，记做h = ( v ，澎) 其中t ( 1 ) v 是一个非空集合，称为超图h 的结点集( 顶点集v e r t e xs e t ) 9 ( 2 ) 生成类澎称为超图h 的超边集v 彤，h 称为超边( h y p e r e d g e ) 一般情况下都有v = uh h e v 舻 例1 - 图g 的团集记为繇，则h = ( v ，渤) 称为图g 的团超图 例2t 层次模型的生成类记为，全体变量记为v ，则h = ( v ，澎) 称 为层次模型生成类超图 定义2 2 2 超图h 的分解 如果生成类j 纩能分解为粥和粥，定义相应的超图分解是t 称超图h = ( v ， ) 能分解为- i = m ，。嬲) ，玩= ( ，确) ，简记为h = 日1o 现，其中 = u e 粥h ，= u 嬲h 定义2 2 3 超图h 的导出子超图 以u 记超图h = ( v ，j 垆) 的结点集v 的子集，称h ( u ) = ( u ，纩( u ) ) 为u 在超 图h 中的导出子超图其中。形( u ) = r e d u n h ：h ，纩) 例3 ，超图h 的生成类纩= 1 ，2 ，4 ) ， 2 ，3 ) ， 3 ，4 ) ) ，u = 2 ，3 ，4 ) ，则 。形( u ) = 2 ，4 ) ， 2 ，3 ) ， 3 ，q ) 注，导出子超图h ( u ) 中，超边 2 ，4 ) 不是原超图的超边，而是包含在超边 1 ，2 ，4 ) 中，与图的导出子图不相同的是，超图的导出子超图中的超边有可能不是 原超图的超边，而是包含在某个超边之中 定义2 2 4 超图h 的关联图g 称图g 是超图h 的关联图，记作g = ( v ，e ( 彤) ) ，其中 t ，口) e ( j 纩) ，当且 仅当存在h 彬，使 t ， ) h 注t 本文中图g 均指超图h 的关联图g 由关联图定义知超图h 的超 边在关联图中都是完全的 定义2 2 5 关联图g 上的乎完全集( g - c o m p l e t e ) c y ，若jh 钟，使c ! 澎，则称c 在关联图g 上是g - 完全的显然， 若c 是g - 完全的，则c 的子集也是g - 完全的 1 0 注关联图g 上g - 完全的子集一定是完全的，但在关联图g 上完全的子集不 一定是g 完全的例如，生成类彤= l ，2 ) ， 2 ，3 ) ， 1 ，3 ) ) - - - - 1 ，2 ，3 ) 在矽的 关联图g 中是完全的，但不是g - 完全的，j 垆中的任何一个集合都不能包含v 定义2 2 6 图g 的g - 分解( g - d e c o m p o s i t i o n ) a ，b v ，且满足以下条件 ( 1 ) d u 6 = v l ( 2 ) c = a n 6 在g 中g - 完全； ( 3 ) c = a n b 在图g 中分离a b 和b a 称( a b ，0 = a n b ，叭o ) 形成了图g 的一种g 分解，并简称a ，b 将图gg - 分解为 两个子图g ( a ) 和g ( b ) c 称为g - 分离子记为g = o ( a ) o g g ( b ) 注t 因为图g 上g _ 完全的子集一定是完全的，因此图的g 分解是一种条件更 强的分解 定理2 2 1 图g 是可约的，( a = 8 6 ，e = d n 6 ，b = b o ) 是图g 的一种g - 分 解则以下结论成立t ( 1 ) 若g ( u ) 是g 的( 极大) 素子图，则u c a 或u c _ b 而且g ( u ) 相应的是 g ( a ) 或g ( b ) 的( 极大) 素子图 ( 2 ) u # c ，g ( u ) 是g ( a ) 或g ( b ) 的极大素子图，则g ( u ) 是g 的极大素子 图 ( 3 ) g ( 矾) ，g ( 巩) 是g 的两个不同的极大素子图，则巩n 现在g 中是完 全的 证明t( i ) 假设a n u # 0 且s n u # 仍，则有： ( 口) ( 0 n u ) u ( 6 n u ) = v ； ( 卢) ( a n n ( b n u - ) a nb ( 在g 中是g - 完全的) ； n ) c n u 在g ( u ) 中分离a n u 和b n u 故g ( u ) 分解为g c a n u ) 和g ( b n u ) 与g ( u ) 是素的矛盾从而u _ a 或u c _ b g ( u ) 显然是子图g ( a ) 或g ( b ) 的( 极大) 素子图 1 1 ( 2 ) 如果c ( u ) 是o ( a ) 的极大紊子图，且u # c 因为g ( c ) = ( c ，c ) 是素的，故 m a # d 如果在g 中有个极大素子图c ( x ) ，满足u x kx n a 0 由( 1 ) 知c ( x ) 是g c a ) 的极大素子图因此u = x 故c ( u ) 是g 的极大素子图 ( 3 ) 记u = 巩u 巩，因为g ( 巩) ，g ( 沈) 是g 的两个不同的极大素子图，则c ( u ) 是可约的若g ( u ) - g ( o ) e g ( b ) o n b 在g 中是乎完全的由( 1 ) 知g ( 巩) ， g ( 观) 也是c ( u ) 的极大素子图而且巩n ，阮( 或巩，觇d ) 巩n 观n n ，因此巩n 观是完全的 定理2 2 2 以下三种分解相互等价t 生成类形的分解 辛超图h = ( v ，) 的分解哥关联图g 的g - 分解 证明；有超图分解定义可知生成类分解与超图分解等价下证生成类分解与关 联图g _ 分解等价t 1 0 由生成类的分解得到关联图的g - 分解； 若生成类j 纩分解为。嬲，。弼。嬲a j f f 2 = h 记a = u 粥h ，b = u h 粥h 则分离子c = h ，( a ，c ，b ) 分解图g ，分离子c 是g - 完全的只须说明c 在g 中分 离a ，b 对v 口e a ，v 卢e b ，连结o l ，卢问的任意一条路记为口= 咖，q 1 ，一l ， 卢= a 。，则必然存在一个啦( 1 i n 一1 ) ，使得啦一1 a ，8 件l b 即存在 h l 嬲，屯嬲使 啦“o i ) h l ， 啦，啦+ 1 ) b 由生成类的分解知a h = d 所以a ，卢，间的路包含由c 中的点，故关联图上的分离性得证 2 0 由关联图的争分解得到生成类的分解： 如果关联图g 上存在一种分解( a ，c ，b ) 。满足分离子c 是g 完全的若 令彤( a ) = r e d h n c a u c ) ：h 澎) ，( b ) 一r e d d n ( b u c ) ：h 彬) 则 能分解成这两个生成类事实上，因为对任意的h 彤h 在关联图上是完 全的，故h a u c 或h b u c 因此，生成类j 纩= 彤( 口) v ( 6 ) ，而且 。形【8 ) j r ( b ) = c ) 由以上定理2 2 2 中超图分解与关联图 分解的等价性知，可通过关联图的g _ 1 2 分解来定义超图的分解， 定义2 2 7 超图h = ( v ，j 垆) 的分解 d b c v ，且满足以下条件 ( 1 ) a u b = v ； ( 2 ) c = a n b 在g 中g - 完全； ( 3 ) c = a n 6 在关联图g 中分离a b 和叭d 即( n b ，c = d n 6 ，扒d ) 形成图g 的一种 分解，令j 矿( 口) = r e d n o ：h j 终， 护( 6 ) = r e d h n b ：h j 乃则称( 口6 ，c = 口n 6 ，b a ) 形成了超图h 的一种分解， 并简称a ，b 将h 分解为两个子超图h ( a ) 和h ( b ) c 称为分离子记为h = h ( a ) e h ( b ) h ( a ) = “兹( a ) ) ，h ( b ) = ( b ，澎9 ( b ) ) 定义2 2 8 素超图( p r i m eh y p e r g r a p h ) 若超图h 存在以上定义的一种分解，则称h 是可约的( r e d u c i b l e ) ，否则称h 是不可约的( p r i m e ) ( 或称素的) 如果导出子超图h ( u ) 是紊的，也常常简称u 是素的 注，只有一个超边的超图就是素的，由超图分解定义知，若u 在图g 上是察 的，则u 在超图h 上也是索的 定义2 2 9 超图的素块( p r i m eb l o c k ) 称超图h 的极大素子超图( m p - 子超图) h ( u ) ( 即h ( u ) 是素的，但是对于任意 的真包含u 的集合x ，【，c x v ，x 的导出子超图h ( x ) 都是可约的是h 的 个素块也常常称结点子集u 是一个紊块 定理2 2 3 超图的素扩张定理 给定超图h ，x c _ v 在h 的关联图g 中连通，c v 在g 中完全，若c 为x 在图g 中的接触点集，则存在一个真包含c 的集合b ，使得h ( b ) 为h ( c u x ) 的 个素子超图 证明。由于图g 上素的结点集在超图h 上也一定是的素因此由图的素扩张 定理知以上定理成立 下面定理给出了( 极大) 素子超图与超图分解间的关系 定理2 2 4h 是一个可约超图( a = o 6 ，c = o n b ，b = b a ) 是h 的一种分 解则以下结论成立， ( 1 ) 若h ( u ) 是h 的( 极大) 素子超图，则u c _ a 或u cb 而且h ( u ) 相应 的是h ( a ) 或h c b ) 的( 极大) 素子超图 ( 2 ) u # c ，h ( u ) 是h ( a ) 或h ( b ) 的极大素子超图，则h ( u ) 是h 的极大素 子超图 ( 3 ) i i ( 仉) ，h ( 觇) 是h 的两个不同的极大素子超图，则巩n 觇在g 中是 g _ 完全的 证明，( 1 ) 假设a n u 0 且b n u d ，则有 ( n ) ( 0 n u ) u ( b nc 厂) = v ； ( 卢) 0 n u ) n ( b n v ) o n 6 ( 在h 中是g _ 完全的) ； ( 7 ) c n u 在a c u ) 中分离a n u 和b n u 故a ( u ) 分解为( o n u ) 和1 日( b n u ) 与h ( u ) 是素的矛盾从而uc _ a 或u _ cb n ( u ) 显然是子超图h ( a ) 或r i ( b ) 的( 极大) 素子超图 ( 2 ) 如果h ( u ) 是h ( a ) 的极大素子超图，且u # c 因为h ( c ) = ( c ，c ) 是素的，故 u n a o 如果在h 中有一个极大素子超图i t ( x ) ，满足u x c v ，x n a d 由( 1 ) 知h ( x ) 是h ( a ) 的极大察子超图因此u = x 故a ( u ) 是h 的极大素子 超图 ( 3 ) i 8 u = 巩u o - 2 ，因为h ( 巩) ，h ( 沈) 是h 的两个不同的极大素子超图，则t i ( u ) 是可约的记h ( u ) = 日( 口) e l l ( b ) ，d n 在g 中是g - 完全的由( 1 ) 知n ( v t ) ， h ( 巩) 也是h ( u ) 的极大索子超图而且巩口，巩6 ，( 或仉f ，巩o ，) 巩n 沈口n6 ，因此矾n 巩是g 完全的 1 4 三、层次模型超图的素分解与素分解子 ( 一) 超图的素分解 例1 超图h - ( v ，彤) ，彤= “2 ，3 ) ， 1 ，3 ) ， 1 ，4 ) ， 3 ，4 ) ， 4 ，5 h ，h 对应的 关联图g 如下所示t， 23 4 5 f 匆，1 h 的极大素子图为珏( k ) ，i = 1 ，2 ，3 h = l ，3 ，4 k = 2 ，3 ) ，= 4 ，5 ) 图 g 的分解方法、结果不唯一( 为方便，不妨直接用g 表示g ) ( 1 ) g 能分解为c ( o ，3 ，4 ) 和g ( t 2 ，3 ，4 ，5 ) 分廨子( 3 ，4 e 劳，是 g - 完全的因此超图h 能分解为h ( 1 ，3 ，4 ) ) = ( 1 ，3 ，4 ， l ，3 ) ， 1 ，4 ) ， 3 ，4 ) ) 和 h ( 2 ，3 ，4 ，5 ) ) = ( 2 ，3 ，4 ，5 ) ， 2 ，3 ，) “3 ，4 ) ， 4 ，5 ) ) ； g ( 2 ，3 ，4 ，5 ) ) 还能分解为g ( 2 ，3 ，4 ) ) 和g ( 4 ，5 ) ，分解子 4 ) 是g - 完全的， 因此h ( 2 ，3 ，4 ，5 ) 能分解为h ( 2 ，34 ) 和h ( 4 ，5 ) ； g ( 2 ，3 ，4 ) ) 还能分解为g ( 2 ，3 ) ) 和g ( 3 ，4 ) ) ，分解子 3 ) 是g _ 完全的，因 此h ( 2 ，3 ，4 ) ) 能分解为h ( 2 ，3 ) 和h ( t 3 ，4 ，) ； 故h 经三个分解步最终分解成t 日= 日( 1 ，3 ，4 ) ) o 日( 2 ，3 ) ) 毋日( 3 ，4 ) ) o 日( 4 ，5 ) ) ( 2 ) g 能分解为g ( 2 ，3 ) ) 和g ( 1 ，3 ，4 ，5 ) ) ，分解子 3 是g - 完全的，故 h 能分解为h ( 2 ，3 ) ，h ( 1 ，3 ，4 ，5 ) ) ； g ( 1 ，3 ，4 ，5 ) ) 能分解为g ( l ，3 ，4 ) ) ，g ( 4 ，5 ) ) ，分解子 4 为g - 完全的， 故h ( 1 ，3 ，4 ，5 ) ) 能分解为h ( 1 ，3 ，4 ) ) 和h ( f 4 ，5 ) ) ，因此超图h 的另一种分解是， 日= 日( 2 ，3 o 日( 1 ，3 ，4 ) ) o 日( 4 ，5 ) ) 发现( 2 ) 的分解，恰好将超图h 分解为其全部极大素子图，而( 1 ) 的分解， 分解结果中的h ( ( 3 ，4 ) ) 并不是h 的极大素子图，而是包含在极大素子图h ( 1 ，3 ，4 ，) 之中 理想的分解，应该能使得最终分解后得到的素( 超) 图都是原( 超) 图的极大 察子图这样的分解，分解结果是唯一的! 不会产生除极大素子图以外的子( 超) 图 定义3 1 1 超图h 的素分解( p - 分解) ( a ，c ，b ) 将超图h 分解为h ( a u c ) 和h ( b u e ) ，如果这两个子超图的极大 素子超图互不相同，而且都是原超图h 的极大素子超图则称分解( a ，c ，b ) 为超 图h 的素分解( p - 分解) 分离子c 称为索分解子( p - 分解子) 注，由定理2 2 3 可得到超图索分解的另一个等价定义。分解( a ，c ，b ) 为超图 h 的p 分解，当且仅当h ( c ) 不是h ( a u c ) 和h ( b u g ) 的极大素子超图 假设可约超图h 被( a ，c ，b ) 分解为玩= h ( a u c ) ，日2 = h ( b u c ) ，如果 研和飓还能被进一步分解，壹到所有分解后的子超图都是素的为止，称经过这样 分解得到的h 的所有素子超图为分解系如果一个可约的超图h 被递归的进行素 分解，由素分解的定义知道，最后得到的分解系必然是h 的两两互不相同的极大素 子超图相反的，假如( a ，c ，b ) 将h 分解为皿和凰不是一个素分解，即h ( c ) 是风或飓的极大素子超图，( 或是玩和玩的极大素子超图) ，但不是h 的极 大素子超图由引理( 1 ) 知，h ( c ) 包含在分解系中( 在分解系中出现两次) 因 此得到如下结论t 一个分解系恰好是超图h 的所有极大索子超图，当且仅当所有的分解都是素 分解例1 中超图如f i g 2 所示的分解，每一步的分解都是素分解 1 6 ( 4 ，5 ) ) 日( 2 ，3 ) 日( l ，3 ，4 ) t 。暑g 2 超图h 极大素子超图的d - o r d e r e d 集列t ，t n 对t = l t 。记岛= k n ( m u u k 一1 ) ，忍= k 岛， 研，s t 称为h ，硌的系( s - s y s t e m ) ，特别的有& = d ，= m 定理3 1 1 对于超图h 的任何个极大素子超图h ( 哪，都有个h 的全部极 大素子超图日( h ) 一r ( v t ) 的序，使得h ，许是d - o r d e r e d 且= u 证明；用归纳法证明对i v l f n 进行归纳 当n = l 时，显然成立 假设对l v i n - 1 时的超图成立当l v i - n 时，若h 是素的，结论成立，否则，记 h ( a ) ，h ( b ) 为h 的分解后的两个子超图由归纳假设知，对h ( a ) 所有极大素子超 图，存在一个d - o r d e r e d 集列a 1 ，a 2 a 对h ( b ) 的所有极大素子超图，存在一 个d o r d e r e d 集列b 1 b 2 ，b ，且使c = o n b 至玩易知，a 1 也，马岛 是d o r d e r e d 若h ( a ) 。h ( b ) 是h 的素分懈，则各个a ，鼠都是h 的极大素子超 图得证否则，若不是素分解，即h ( c ) 是h ( a ) 或( 和) h ( b ) 的极大素子超图， 有两种情形t ( a ) c 在集列a 1 也，岛岛中出现一次，且严格包含在该集列列的 另一个集合中； 或( 卢) c 在集列a 1 ，a 。，b l ，岛中出现两次 对这两种情况中的任何一种，据d - o r d e r e d 集列性质( 1 ) 都可将c 从序列中除去， 而且除去c 后的集列仍是d - o r d e r e d 证毕 1 7 推论3 1 2 ( 1 ) 若h ，场是可约超图h 的全部极大素子超图的d o r d e r i n g ，则有 ( a ，c ，b ) = ( u k 曲，s v ，r t ) 是h 的素分解它把h 分解为h ( a u c ) = h ( uk ) 和素块h ( b u c ) = h ( v t ) h ( m ) ，h ( v t 一1 ) 是h ( a u c ) 的极大素子超图 ( 2 ) 若存在h 的一个分解，则存在h 的个索分解 证明：( 1 ) 由于，场是d o r d e r e d ，则存在p t ，使曲，则