（应用数学专业论文）树同构的判定及树在概念格和逆矩阵中的应用.pdf

摘要 i p 一一i i 一, i l in ! 目i 鼍舅置曼鼍鼍曼皇鼍皇量! ! 曼暑 摘要 本文以图论中的树为研究对象和研究工具，首先对树同构的问题进行了探讨，然后 把树中任二顶点间恰有一条轨的特殊结构和性质应用到构造概念格和求逆矩阵中 本文将分三部分完成第一部分通过对图论中最简单的，也是图的骨骼和标架的树 的探讨，给出树同构的判定方法，从而为解决一般图的同构问题这个n p 一完全问题打下 了基础 第二部分利用树状结构对概念格节点进行索引，提出了属性优先的概念格渐进式构 造算法，有效地缩小了产生子的搜索范围以及新增格节点的父节点和子节点的搜索范 围，从而加速了概念格渐进式更新过程 第三部分将图论作为研究工具，利用树中任二顶点间恰有一条轨的特殊结构，给出 求一类可逆矩阵的逆矩阵的图论解法 关键词树同构邻接矩阵关联矩阵概念格 a b s t r a c t a b s t r a c t t h en o t a t i o no ft r e ei su s e df o ro b j e c ta n dt o o li ng r a p ht h e o r y , u s i n gt h i sn o t a t i o n ，t h i s p a p e rf i r s t l yr e s e a r c h e st h ep r o b l e mo fi s o m o r p h i s mb e t w e e nt r e e s ，a n df o l l o w e db ya p p l y i n g s p e c i a lf r a m ea n dc h a r a c t e rt h a tt h e r ei sj u s to n et r a i ld u r i n ga n yt w ov e r t i c e si nc o n c e p t l a t t i c ea n di n v e r s em a t r i x t h ep a p e rw i l lb ec a r r i e do u tb yt h r e ep a r t s t h ef i r s tp a r to ft h ep a p e rp r e s e n t sc r i t e r i o n o fi s o m o r p h i s mf o rt r e e sb yd i s c u s s i n gt h es i m p l eg r a p h ，n a m e l ys k e l e t o no ft r e e a f t e r w a r d s ， w es t r i d ea ne x p l o r i n gs t e pi no r d e rt os o l v et h ep r o b l e mo fg r a p hi s o m o r p h i s m t h es e c o n dp a r tu s e st r e es t r u c t u r et oi n d e xt h es e to fc o n c e p t si nc o n c e p tl a t t i c e ，a n d d e v e l o p sa t t r i b u t e p r i o r i t yi n c r e m e n t a lf o r m a t i o na l g o r i t h m i tg r e a t l yr e d u c e st h e s e a r c h s p a c eo fp a r e n t sa n d c h i l d r e no fn e wb o r nc o n c e p tn o d e ，t h e ni tc a ns p e e du pt h ep r o c e s so f i n c r e m e n t a lu p d a t i n go fc o n c e p tl a t t i c e t h el a s tp a r tp r e s e n t sag r a p hm e t h o dt os o l v et h ei n v e r s em a t r i xo fac l a s so fi n v e r t i b l e m a t r i xw i t hs p e c i a ls k e l e t o nt h a tt h e r ei sj u s to n et r a i ld u r i n ga n yt w ov e r t i c e so ft r e e k e yw o r d s t r e e i s o m o r p h i s ma d j a c e n c ym a r x i n c i d e n c em a t r i x c o n c e p t l a t t i c e i l 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教 育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了致谢。 作者签名： ! 童盎圭 日期： 丝竺艺年月卫日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 本学位论文属于 1 、保密口，在年月日解密后适用本授权声明。 2 、不保密囱。 ( 请在以上相应方格内打“4 ”) 保护知识产权声明 本人为申请河北大学学位所提交的题目为 的学位论文，是我个人在导师( 晃啤 i ( 协阁拍叫毫殿韧友蒯) 驴失p 卑中如另调 ) 指导并与导师合作下取得的研究成果， 研究工作及取得的研究成果是在河北大学所提供的研究经费及导师的研究经费 资助下完成的。本人完全了解并严格遵守中华人民共和国为保护知识产权所制定 的各项法律、行政法规以及河北大学的相关规定： 本人声明如下：本论文的成果归河北大学所有，未经征得指导教师和河北大 学的书面同意和授权，本人保证不以任何形式公开和传播科研成果和科研工作内 容。如果违反本声明，本人愿意承担相应法律责任。 声明人：霎肄主 作者签名： 导师签名： 嚷林立 日期：4 年月j 生日 日期：2 孕年月生日 第1 章概述 第1 章概述 1 1 课题的发展现状 离散数学是计算机科学技术与网络信息的思想基础，图论是离散数学的骨干分支， 是计算机科学最重要的基础之一离散数学，特别是图论，近年来异军突起般蓬勃发展， 在许多领域，诸如物理学、化学、运筹学、计算机科学、信息论、控制论、网络理论、 社会科学以及经济管理各方面都有广泛的应用因此受到世界数学界和工程技术界越来 越广泛的重视树是图的骨骼和标架，而且是图论难题的试金石，许多图论难题往往首 先用树来试探它是否成立，然后再向一般图推广 图的同构问题属于图论中的n p - 完全问题两图同构的必要条件是：( i ) 两图顶点 数相同( i i ) 边数相同( i i i ) 度数相同的顶点个数相同但这仅是必要条件，而不是 充分条件对于两个同构的图，易见它们有相同的结构，差异只是顶点和边的名称不同， 或两个图的形状不同由于我们关注的是图的结构和性质，所以判定看起来形状不同的 两个图的同构有很重要的意义关于图的同构，虽然有一个u l a m 猜想，但至今尚未解 决目前有些人提出了用度序列法判定图的同构1 4 1 ，但算法的复杂性为d ( 2 。) 概念格是由德国的w i l l e 教授在2 0 世纪8 0 年代首次提出的，是数据分析的有力工 具目前在数据挖掘、软件工程、信息检索和知识发现等方面，都有着成功的应用在 应用概念格的过程中，概念格的构造效率始终是一大难题目前的概念格构造算法主要 分为两大类：批处理算法和渐进式算法其中渐进式算法被认为是比较有前途的一类对 于渐进式算法又可细分为g o d i n 提出的基于对象的渐进式生成算法 9 1 和李云等提出的基 于属性的渐进式生成算法两类 矩阵论现已成为数学的一个重要分支，也是诸多应用领域的重要工具图论也引入 了邻接矩阵，关联矩阵，圈矩阵与割集矩阵等重要矩阵作为研究工具 1 2 本文的主要工作 本文以树为研究对象，给出树同构的判定方法，并以树为研究工具，利用树中任二 顶点间恰有一条轨的特殊结构给出概念格的构造算法和一类可逆矩阵的逆矩阵的图论 求法 本文首先从树的同构出发，用标号的方法给出树同构的判定方法，算法的复杂性为 1 河北火学理学硕十学位论文 d ( 门3 ) 从而为解决一般图的同构这个图论难题奠定了基础然后采用树结构对概念格 节点进行组织，基于属性的渐进式增加，提出了属性优先的概念格渐进式构造算法并 结合实例说明了概念格的树结构组织在属性优先的渐进式生成概念格时，能有效地缩小 产生子格节点的搜索范围和新增格节点的父节点和子节点的搜索范围，从而能快速生成 概念格在对象个数比属性个数大得多的实际形式背景的概念格构造过程中能显示出更 大的优越性因此，本算法对生物学中某些问题的研究有相当大的应用前景和实际意 义最后以图论为工具来求解一类可逆矩阵的逆矩阵通过讨论i 虚点的树的关联矩阵 的一个特殊性质，提出1 虚点树的关联矩阵的任意导出矩阵的逆矩阵的图论解法从而 为图论在线性代数方面的应用做了一次大胆的尝试 1 3 本文的组织方式 第2 章为预备知识，主要给出本文涉及的基本知识 第3 章对图的同构问题( n p 一完全问题) 做出了大胆探索，给出树同构的判定方法 第4 章将树结构组织形式运用于概念格的提取，提出了属性优先的概念格渐进式构 造算法 第5 章将图论作为研究工具，利用树中任二顶点间恰有一条轨的特殊结构，给出求 一类可逆矩阵的逆矩阵的图论解法 2 第2 章预备知识 第2 章预备知识 为了完成下面各章节的内容，本章分三部分分别给出图论、概念格和代数中的一些 所需基本知识 2 1图论中的基本知识 本节给出本论文涉及的图论的基本概念和性质 定义2 1 1u , 2 称数学结构g = 缈( g ) ，e ( g ) ，妒g 为一个图，其中v ( g ) 是非空集合，妒g 是从集合e ( g ) 到y ( g ) v ( g ) 的一个映射，则称g 是一个以v ( g ) 为顶点集合，以e ( g ) 为 边集合的有向图，y ( g ) 中的元素称为图g 的顶点，e ( g ) 中的元素称为g 的边，称为 g 的关联函数若( p ) = 0 ，v ) ，e ee ( g ) ，0 ，v ) v ( g ) y ( g ) ，则称p = r v 如果把有向 图的方向取消，就得到无向图只与一个顶点相关联的边叫做环妒ge 1 ) = g ：) = w ， 则称p ，与p ：是重边无环无重边的图称为简单图顶点或边用字母标定的图，称为标定 图 定义2 。1 ，2 u , 2 在顶点和边的交错链形= v o e l v 】e 2 e k v 女中，e j 三( g ) ，i = 1 , 2 ，k ， 1 ，矿( g ) ，j = 0 , i ，k ，且e ，= ，川v ，则称形是图g 的一条道路，其中允许v ，= v ，或 e ，= e ，f j ，称v o 是形的起点，v 女是的终点，k 为路长，1 ，m i k - 1 ) 称为缈的 内点各项点相异的道路称为轨道，记成p ( v 。，1 ，；) 起点与终点重合的轨道叫做圈，长 为k 的圈称为k 阶圈 定义2 1 3 l 2 1 在图g 中若存在道路以u ，v 为起止顶点，则称“与v 在图g 中连 通g 中任二顶点皆连通时，称g 为连通图无圈连通图称为树 定义2 1 4 l 2 1 设无向图g ；( y ，e ) 是以阶s 边的连通图，其顶点集为v = v l ，v ：， ) ，边集为e = 溉，e 2 ，e 。) 与同一条边关联的两个端点称为邻接的图g 的邻接矩 阵记为a = 如，) ，其中若v ，与 ，邻接时口妒= 1 ；若v ，与v ，不邻接或f = j 时，口口= 0 定义2 1 5 l 2 设无向图g ；( 矿，e ) 是，2 阶边的连通图，其顶点集为v = “，吃， ) ，边集为e = 编，p ：，e 。 若边p 的端点是”与v ，则称p 与u 、1 ，相关联g 的点 边关联矩阵记为m ( g ) = ( 屯) w ，其中1 ，和e ，关联时，勃= 1 ，否则岛= 0 河北大学理学硕十学位论文 定义2 1 6 【3 1 设v v ( g ) ，g 中与顶点v 关联的边的数目称为v ( 在g 中) 的度， 记作a ( v ) 如果y ( g ) = v lv 2r + r j v ，) ，称非负整数序列( d ( v 1 ) ，a ( v 2 ) ，a r ( v p ) ) 为图g 的 度数列 定义2 1 7 4 1 设有两个图g 1 = ( k ，e 。) 和g 2 = ( ，e 2 ) ，它们的顶点集之间有一一对 应关系，使得边之间有如下的关系：设u lhu 2 ，v 1h v 2 ，( “1 ，1 k ，“2 ，1 ，2 k ) 如果 ( “l ，1 ) e l ，那么( 甜2 ，v 2 ) e 2 ，而且( “l ，1 ，1 ) 的重数与( ”2 ，v 2 ) 的重数相同，这种对应叫 做同构，记作g 。兰g 2 定义2 1 8 【5 1 设卢= 0 1 l a 2 a 。为长为，z 的符号串，称其子串a l ，a l a 2 ，a l a 2 a 川 分别为口的长为1 ，2 ，疗一1 的前缀 定义2 1 9 【6 1g = ( y ，e ) 是，2 阶s 边的连通图，kcv ，e 1 是两个顶点都在k 中的g 的边的集合，且旧l = s 把k 中的顶点从g 中删去，当一条边的两个顶点都被删去时， 该边也删去；当一条边的两个顶点只有一个顶点被删去时，保留该边，最后得到的图形 称为有虚点的胛一k 阶s s 条边的图，简记为g k 它的顶点集为矿k ，边集为e 巨， 在图示中我们将用圆圈表示虚点含有一个虚点的树称为1 虚点树在有虚点的图中， 其它的概念( 比如连通性、连通分支、树、轨、圈等) 与通常意义下的有关概念相同，只 不过此时有些点可能是虚点g 的关联矩阵m ( g ) 中划掉k 的元素所对应的行后得到的 矩阵称为g k ) 的关联矩阵，仍记为m ( g k ) 例如对图2 - 1 所示的图g ，g v ，) 是两 个4 阶1 虚点的树分支( 见图2 2 ) g 图2 1 v ，) v 2屹 图2 2 性质2 1 1 【1 1 若g 是一个简单图，则关于树有下面的等价命题： 命题ag 是树 命题bg 中任二项点间恰有一条轨 u l a m 猜想1 1g 与是两个图，j v ( e ) | ，矿( g ) = v 。，屹，v v ) ，矿) = “，“：， 4 第2 章预备知识 u ，) 且g v ，兰h 一“，i = 1 , 2 ，v ，贝0g 兰h 引理2 1 1 【7 】如果图g 】与图g ：是同构的当且仅当按适当的顺序对其顶点标号后， 它们的邻接矩阵是相等的 引理2 1 2 【8 】设g = ( y ，e ) 是门阶边的连通图，a 是m ( g ) 的任意k 阶子方阵，记彳 在m ( g ) 中所在的行标集合为v = ( ，v ：，1 ，。) ，所在的列标集合为e = ( e ，p ：，e 。) ， 于是d e t ( a ) 0 ( = 2 。) ，当且仅当图g = ( v ，e ) 的每个分支或是1 虚点的树或是单奇圈 图，其中是g = ( v ，e ) 中单奇圈图的个数 引理2 1 3 【6 】设丁= ( y ，e ) 是1 虚点的树，v = v 1 ，1 ，2 ，v 。) ，e = e l ，p 2 ，e 。 x c t 的顶点v ，和边p ，记丁一e ，中不包含丁的虚点的那个分支为t ( e ，) ，包含在丁( p ，) 中的p ，的 那个端点称为t ( e ，) 的根；当1 ，v ( t ( e ，) ) 时，记由t ( e ，) 的根到v ，的唯一路长度为 l ( v ，e ，) 用丁的边和顶点分别标定m ( 丁) - 1 的行和列，记m ( 丁) 。( p ，1 ，) = m 即矩阵 m 仃) 的逆为m ( 丁) = ( 所，) 脚，则 = 当_ 矿( h p 瑚时， 其它 2 2 概念格中的基本知识 本节给出本文中涉及的概念格的基本概念 定义2 2 1 9 1 0 , i l l 在形式概念分析中，数据是用形式背景来表示的，一个形式背景 是一个三元数组k = ( g ，m ，i ) ，其中g 是对象集合，m 是属性集合，是g 与m 之间 的一个二元关系用( g ，m ) i 表示“对象g 有属性m ”对于a g 及b m ，定义： a = m mv g 么，( g ，聊) ，) ，曰7 = 信giv m b ，q ，m ) ， 则形式背景k = ( g ，m ，) 的概念为元素对( 彳，b ) ，其中a g ，b 互m ，厂0 ) = b ，g 佃) = 彳 概念( 么，召) 的外延是彳，内涵是丑 定义2 2 2 旧在所有概念的集合间建立一种偏序关系：给定两个概念c 1 = ( 彳。，且) 和c 2 = ( a 2 ，b 2 ) ，则c 1 c 2 a 1ca 2 ( 或b 13b 2 ) ，那么c l 是c 2 的子节点，c 2 是c 1 的父节点根据这种偏序关系，形式背景k = ( g ，m ，i ) 的概念节点的集合产生一种完备 格结构，格中元素满足： 气 河北大学理学硕十学傅论文 c lvc 2 = ( ( b l 厂、b 2 ) ，b l 厂、b 2 ) ；c 1 人c 2 = ( a lna 2 ，( a lr 、a 2 ) ) 称此完备格为k = ( g ，m ，) 的概念格，记为l ( k ) 并且由这种偏序关系可生成l ( k ) 的h a s s e 示图：对于l ( k ) 中的两个不同的节点c 。和c 2 ，如果c 1 c 2 ，并且不存在其它 的节点c 3 ，使得c l f ) ，称a 为下三角形矩阵 定义2 3 2 i 1 3 】既是上三角形又是下三角形的矩阵称为对角矩阵，即 a = 口1 1 0 0 a 2 2 00 o 0 ： d ” 为一刀阶对角矩阵；如果么中元素口。= 口( f = 1 , 2 ，刀) ，则称彳为数量矩阵；当口= 1 时， 称此矩阵为单位矩阵甩阶单位矩阵常记作， 定义2 3 3 1 1 3 1 对于门阶矩阵么，如果存在矩阵b ，使a b = b a = ，则称矩阵4 是可 逆矩阵或非奇异矩阵，且称b 是彳的逆矩阵 6 第3 章树同构的判定方法 第3 章树同构的判定方法 图的同构问题属于图论中的n p 完全问题对于两个同构的图，易见它们有相同的 结构，差异只是顶点和边的名称不同，或两个图的形状不同由于我们关注的是图的结 构和性质，所以判定看起来形状不同的两个图的同构有很重要的意义 两图同构的必要条件是：( i ) 两图顶点数相同( i i ) 边数相同( i i i ) 度数相同的顶 点个数相同但这仅是必要条件，而不是充分条件 树是图论中最简单的图，也是图的骨架树这一数学概念在不同的领域有着广泛的 应用在图论中，如果对一个一般的图的猜想不知是否成立，往往用树来验证它下面 给出树同构的判定方法 引理2 1 1 虽然是判定两图同构的充要条件，但是也仅指出在理论上存在适当的顶 点标号顺序，能使同构的两图有相同的邻接矩阵即便如此，此方法在其它文献中我们 并未发现，所以，可以说是用矩阵判定图同构的一个创新然而由于它存在上面所说的 缺点，使得它的应用受到了限制本章以构造的方式具体地给出一个标号方法，用于判 定两棵树的同构由于本章的方法具体、易操作，所以实际运用于判定两棵树的同构更 为适宜，并为实现计算机化打下基础 上面给出的两图同构的三个必要条件( i ) ( i i i ) 中，只要有一条不满足，则两图 必不同构所以以下讨论满足条件( i ) ( i i i ) 的两棵树是否同构下面给出两棵树的 标号方法，根据引理2 1 1 ，这种标号方法就是两棵树同构的判定方法 定义3 1 在简单图中，因为轨e = v l v ：v l 与轨昱= m v 2 1 ，是同一条轨，记罡= 只一 所以置的度数列口，- - ( d ( v 1 ) ，d ( v 2 ) ，：一，d ( v ) ) 与最的度数列a 2 = ( d ( h ) ，d ( v 2 ) ，d ( v ，) ) 间的 关系记为口，= a ，一 设g l ，g ，是满足条件( i ) ( i i i ) 的力阶树由性质2 1 1 知树中任二顶间恰有一 条轨，所以树g ，g ，中必有一条或几条最长轨判定过程分以下四个步骤完成 步骤l若树g 与树g ，中最长轨的条数或长度不相等，则树g 与树g ，必不同构若 树g ，与树g ，中最长轨的条数和长度都分别相等先把g 1 中的任一条最长轨( 设长度为 ，) 按从起点到终点的顺序把各项点依次标记为v 。，v ：，1 ，m ，并写出这条轨的度数列 7 河北大学理学硕士学位论文 a = ( a ( v 1 ) ，a ( v 2 ) ，d ( v f + 1 ) ) 步骤2 然后把g ，中的每条最长轨( 设有m 条) 都按从起点到终点的顺序分别写出 各顶点的度数列屈，卢：，卢。若卢，仅且卢，a ，( 1 f 朋) ，则树g 。与树g ：不同构若 存在f 0 , 2 ，m ) ，有卢，= a 或卢，= a ，则把度数列卢，对应的轨道的顶点按顺序或逆序标 记为“l ，“2 ，u ，+ 1 注意标记后必须满足( d ( “1 ) ，a ( u 2 ) ，a ( u ，+ 1 ) ) = a 步骤3 分别在g 。与g ：中找出还未被标记的以v ：与“：为起点的所有轨若它们的 条数和长度分别相等，并且相应的轨的度数列或其逆也相等，则对树g 1 与树g ，中对应 的顶点分别标记相同的序号若其中之一不相等，则树g 。与树g ：不同构 步骤4 在顶点1 ，与u ，1 ，。与u 。，v 与甜，处的操作同步骤3 只有当以各对 对应顶点为起点的所有轨的条数、长度分别相等，并且相应的轨的度数列也相等，或经 过变换之后相等时，树g 。的顶点标号才能从1 ，。一直标记到1 ，。，树g ：的顶点标号才能从u 。 一直标记到“。，即树g 。与树g ：完全标定否则，树g l 与树g ：不同构 由于按上述方法完全标定的树g ，与树g ：，各顶点之间的邻接关系完全相同，所以 它们的邻接矩阵相等，由引理2 1 1 知g 。与g ：同构 下面的例3 1 说明如何利用给定的标号方法来判定满足条件( i ) ( i i i ) 的两棵树是 否同构 例3 1 用给定的方法判定如图3 1 与图3 2 所示的树g ，与树g ，是否同构 qg 2 图3 1 图3 2 g ，与g ，满足：顶点数都为1 l ；边数都为9 ；都有6 个1 度顶点，2 个2 r 度顶点，2 个3 度顶点和1 个4 度顶点，即g ，与g ，满足两图同构的必要条件( i ) ( i i i ) 下面用给定的方法来判定树g 1 与树g ：是否同构，分下面几步完成 步g ，中有三条长度为5 的最长轨任取一条标记为1 ，1 v 2 1 ，v 。1 ，y 6 ，如图3 - 3 所示， 其度数列为口= ( 1 ，2 ，4 ，3 ，3 ，1 ) 8 第3 章树同构的判定方法 图3 - 3 图3 - 4 步g 2 中也有三条长度为5 的最长轨分别为e = r l r 3 r r t r s r 9 ，足= r 2 r 3 r 4 r t r g r 9 ， 只= r 6 r s r 4 r t r s r 9 ，如图3 4 所示。其度数列分别为筘1 = ( 1 ，3 ，3 ，4 ，2 ，1 ) ，卢2 = ( 1 ，3 ，3 ，4 ，2 ，1 ) ， 卢，= ( 1 ，2 ，3 ，4 ，2 ，1 ) ，其中卢。和卢：满足p ，= a 和卢：。1 = a 任取其一，不妨取卢。，将轨卢。所 对应的顶点逆序标记为“1 1 2 2 材3 甜4 “5 u 6 ，如图3 - 5 所示其度数列( d ( u 1 ) ，d ( u 2 ) ，d ( u 6 ) ) = a 图3 5 步在g ，中未被标记的顶点中，与v ，相邻的有2 个1 度顶点，g ：中未被标记的顶 点中，与“，相邻的恰有2 个1 度顶点，则分别对应标记为 1 1 71 l ，。和u 7 , 群。在g ，中未被标 记的顶点中，有一条以v 。为起点的长度为2 的轨，g ，中未被标记的顶点中，也恰有一 条以v 。为起点的长度为2 的轨，且它们的度数列都为( 3 , 2 ，1 ) ，故除起点外其它两个顶点 分别标记为v ，1 ，l o 和u 9 “l 。同理与v ，相邻的未被标记的1 度顶点记为v 1 1 ，与“5 相邻的 未被标记的1 度顶点记为“分别如图3 - 6 和图3 7 所示 图3 - 6图3 7 步完全标定后树g ，的邻接矩阵为4 ，树g ：的邻接矩阵为a ： 9 河北大学理学硕+ 学位论文 v 1 ， v 3 ，4 v t 4 = v 6 仉 吒 v o v l o h l 因为a 1 = a 2 ，所以g l 兰g 2 “ 坞 地 材c 以= “6 “- 蚝 甜o 1 1 i 9 ou l i o 0 o 0 0 0 0 0 0 l0 0 0 01 o o 0 0 0 0 0 0 0 o10 1o 0 o 0o 关于图的同构，虽然有一个u l a m 猜想，但至今尚未解决目前有些人提出了用度 序列法判定图的同构【1 4 1 ，但算法的复杂性为0 ( 2 ) 而本章给出的用适当标号的方法来 判定两棵树的同构，算法的复杂性为d g 3 ) 实例验证该方法行之有效 1 0 0 0 ，o 0 o 0 o o 0 o 蜘0 0 l 0 0 0 0 o 0 0 0 蚝0 o 0 o o 0 o o 0 o 蚝0 o o 0 ，0 o o o ， o o l 0 1 o 0 0 l o 0 鸭o l o l o o l 1 0 o 0 吃o l o 0 o o o o o 0 o 1 o o o o o d o o d o o o 0 o o o o o o o o o o o o o 0 ，o o 吩0 0 o l 0 o o o o l 0 o 0 1 o o 0 0 o o o 0 叶o o 0 0 o o o 0 o 0 o o o 0 1 0 o o o 0 o 如0 o o o 0 o o o ， k o o o 0 o o ，o o 吩o 1 0 o o 1 1 o o 0 心1 0 1 0 o o o o 0 0 0 吒o l 0 o o o 0 d 0 0 d 第4 章树状结构组织的属性优先的概念格渐进式算法 第4 章树状结构组织的属性优先的概念格渐进式算法 概念格是由德国的w i l l e 教授在2 0 世纪8 0 年代首次提出的，是数据分析的有力工 具目前在数据挖掘、软件工程、信息检索和知识发现等方面，都有着成功的应用 在应用概念格的过程中，概念格的构造效率始终是一大难题目前的概念格构造算 法主要分为两大类：批处理算法和渐进式算法其中渐进式算法被认为是比较有前途的 一类对于渐进式算法又可细分为g o d i n 提出的基于对象的渐进式生成算法【9 】和李云等 提出的基于属性的渐进式生成算法【l5 】两类其中g o d i n 算法受形式背景中对象个数的影 响，而李云等的算法受属性个数影响更大实际的数据表，比如生物学中按动物的某些 特征进行分类的研究中，数据表的记录( 对象) 个数较大，而字段( 属性) 的个数往往 是有限的因此，在实际的形式背景中对象的个数比属性的个数大得多的情况下，采用 属性优先的渐进式生成算法构造概念格会更快些谢志鹏、刘宗田的属性优先的概念格 的快速渐进式构造算法i l6 1 ，提出了采用树结构对概念格节点进行组织的方法，从而可以 有效地减少算法的执行时间 本章基于属性的渐进式增加，采用树结构对概念格节点进行组织，提出了属性优先 的概念格渐进式构造算法从而在对象个数比属性个数大得多的实际形式背景的概念格 构造过程中能显示出更大的优越性 下面的例4 1 将作为通例以说明利用树状结构的属性优先的概念格渐进式构造算法 的生成过程 例4 1 表4 1 给出了生物学的一个实例，表4 2 是表4 1 的实例建立的数学模型所 对应的形式背景k = ( g ，m ，i ) ，其中g = 1 ，2 ，3 ，4 ，5 分别代表五种动物：狮子、麻雀、鹰、 蝙蝠、驼鸟的集合，m = 口，b ，c ，d 分别代表四种特征：猎食、飞行、鸟类、哺乳的集合， ，描述了g 中元素拥有的m 中的属性值集图4 1 是相应的概念格l ( k ) 的h a s s e 示图 河北大学理学硕十学位论文 特征 猎食飞行 鸟类 哺乳 动叭 狮子 麻雀 鹰 蝙蝠 驼鸟 表4 1 口bcc ， l 10o 1 2 0110 3 1 1 1 0 4o1o1 5001o l 撑( 1 ，2 ，3 ，4 ，5 ) ，咖) 表4 2 图4 1 4 1属性优先的概念格渐进式构造算法的基本思想 属性优先的渐进式构造概念格就是在初始背景k = ( g ，m ，) 所对应的初始概念格 l ( k ) 和新增属性m 的情况下求解形式背景k = ( g ，m u m , ，) 所列应的概念格 l ( k + ) ，其中，表示新增属性m + 后g 与mum + 的二元关系属性优先的渐进式生成概 念格的求解过程中，需解决以下三个问题： ( 1 ) 所有新节点的生成 ( 2 ) 避免已有节点的重复更新 ( 3 ) 边的更新 为了有效地解决这三个问题，对于初始概念格l ( k ) 中的每个节点，根据它和新增 1 2 第4 章树状结构组织的属性优先的概念格渐进式算法 属性m 及包含该属性的对象集g ( m ) 之间的关系，可以定义它们的不同类型 对于概念c ，设其内涵、外延分别用i n t e n t ( c ) 和e x t e n t ( c ) 来表示 定义4 1 1 如果一格节点c 满足e x t e n t ( c ) sg ( m ) ，则c 被称为一个更新格节点 定义4 1 2 如果某个概念c 1 = ( 4 ，蜀) 满足： ( i ) 令n e w e x t e n t = 4ng ( m + ) ，而在l ( k ) 中不存在某个节点c 2 满足e x t e n t ( c 2 ) = n e w e x t e n t ( i i ) 对于三( k ) 中任意满足c 3 c 1 的节点c 3 ，都有e x t e n t ( c 3 ) n g ( m ) n e w e x t e n t 成立 则c l 称为一个产生子格节点 定义4 1 3 如果一个格节点c 既不是更新格节点，也不是产生子格节点，则c 被称 为是一个不变格节点 下面介绍初始概念格l ( k ) 中三种类型的概念格节点在渐进式生成新概念格l ( k ) 时的变化情况 如果c 是一个不变格节点，显然c 可以直接保留到新概念格l ( k ) 中 如果c 是一个更新格节点，则在l ( k ) 中c 被更新为( e x t e n t ( c ) ，i n t e n t ( c ) u m + ) 如果c 是一个产生子格节点，除了将c 保留到新概念格l ( k ) 中外，还将由c 产生 一个新增格节点g 。包含于l ( k ) 下面的性质说明新增格节点e 删的构成 性质4 1 1 如果初始概念格中某个概念c 1 = ( a 1 ，e ) 是产生子格节点，则由其产生 的新增格节点g 。= ( 4n g ( 柳+ ) ，尽u k ) 证明在初始形式背景k = ( g ，m ，) 中，若c l = ( 4 ，b 。) 是概念格l ( k ) 中的一个概 念，由概念的定义知，在二元关系，的作用下，满足蜀= 4 ，a 1 = 耳，即内涵b 1 是外延4 中对象的所有公共属性的集合，而外延4 是拥有内涵b 1 中属性的所有对象的集合而 在增加属性m 后的新形式背景k = ( g ，mum + , 1 ) 中，在二元关系，的作用下，概念c 1 的内涵b l 的扩大必将导致外延彳，的减少反之，外延a ，减少其内涵b j 就相应增大 由产生子格节点的定义( 定义4 1 2 ) 知，在l ( k ) 中不存在外延等于n e w e x t e n t = 4 n g ( m + ) 的概念，所以在l ( k ) 中一定需增加一个新节点，其外延就等于n e w e x t e n t ，且 n e w e x t e 甩to4 ，因此新增概念的内涵一定是蜀u k + 得证 河北大学理学硕士学位论文 由以上分析可知，新概念格l ( k ) 中的节点类型除了包含初始概念格l ( k ) 中的不 变格节点、产生子格节点和更新后的更新格节点外，还应包含新增格节点 下面回答本节开始提出的属性优先的渐进式生成概念格求解过程中需解决的三个 问题 由定义2 2 2 知，对于上( k + ) 中的任意一个新增格节点g 。，它的外延集e x t e n t ( c 。) 必然是新对象的外延描述g ( m ) 和l ( k ) 中某个旧节点的外延集e x t e n t ( c o t e ) 的交集， 也就是说，新增格节点和产生子格节点之间是一一对应的所以生成所有新增格节点的 关键是找出所有的产生子格节点，而不同的产生子格节点所对应产生的新增格节点是互 不相同的这种关系的建立就解决了格更新的前两个问题：所有新节点的生成和避免已 有节点的重复更新 更新格节点之间的边的基本思想是将每个新增格节点插入格中，并维护父子节点之 间的边的关系对于每个新增格节点g 删，分别求出它的父节点p a r e n t ( c 。) 和子节点 如蒯( o ) ：对于的每个父节点c p ，增加一条连线c ，一；对于e 。的每个子 节点e ，增加一条连线g 。一e ，再删除相应的连线c 。专c c 这样就解决了概念格 更新的第三个问题，即边的更新问题 以上说明了属性优先的概念格渐进式构造过程但在其更新过程中，为了识别产生 子格节点以及插入新增格节点后进行边的更新，需要多次重复访问各节点为了减少重 复访问次数，节省时间，将在下节引入格节点的树结构组织 4 2 格节点的树结构组织 本节介绍用索引树来组织概念节点、定义索引树的遍历次序并证明相关定理 如果给定对象集g 上的一个全排列f ，任薏一个对象子集g 1 = h ，2 ：，仇) 便唯一 地对应于一个数字串心致，强 n 2 n k 不妨使用函数符号y 来表示这种对应关 系，则每个概念节点c 都唯一地对应于g 上的一个数字串y ( e x t e n t ( c ) ) 因此我们可以 用树根为最低点的树状结构来对概念节点的集合进行组织，这种树状结构在本文中被称 为索引树 在索引树中，每条边代表一个对象如果五是瓦的子节点，而五到互的边是对象g ， 则称五是五的第g 个父节点，记为正= 五p a r e n t g 】每个树节点丁对应一个数字串a ( 丁) ， 1 4 第4 章树状结构组织的属性优先的概念格渐进式算法 其中函数a 定义为：对于根节点r o o t ，1 ( r o o t ) 三空串；如果互= 互p a r e n t g 】，则 九( 正) 暑a ( 互) + g 也就是说，a ( ，) 表示从根节点r o o t 到节点t 所经过的边( 对象) 的 排列 对于索引树节点丁，如果存在某个概念节点c 满足) , ( e x t e n t ( c ) ) = z ( t ) ，我们称丁为 有效树节点如果不存在c 满足y ( e x t e n t ( c ) ) = i ( t ) ，则称7 为辅助树节点在索引树中， 五是正的子孙节点当且仅当y ( 石) 是y ( 五) 的前缀 为了建立一个概念集合的索引树，我们首先将索引树初始化为一个根部节点，它对 应着外延为空的概念，然后可以将概念集合中的每个概念逐个地插入到索引树 接着，我们定义对索引树的遍历次序：先访问树根，再依次遍历它的所有子树，而 遍历子树的顺序是由大到小( 如图4 2 所示即从右向左) 图4 2 对于通例中的形式背景表4 2 ，若假定g 上的全排序为1 2 3 4 5 ，则图4 1 中概 念格所对应的索引树如图4 2 所示其各概念节点的遍历次序为：1 0 # ，8 拌，7 撑，6 拌， 2 ! ，3 舂，9 ，5 券，4 存，1 群 为了用符号来表示各节点被访问的先后次序，给出下面的定义4 2 1 定义4 2 1 由索引树中节点间的遍历次序又可定义树节点之间的一个访问顺序关 系，这是树节点的一个全序关系，记为 ，正 r 兀表示正在兀之前被访问 根据给定的遍历次序，先被访问的树节点和概念格节点应满足下面的两个定理 定理4 2 1 对于两个树节点五和正，如果正 ，兀，当且仅当它满足下列条件之一： 河北大学理学硕十学位论文 ( 1 ) a ( 王) a ( 互) 且a ( 疋) 不是九( 互) 的前缀 其中，“ ”表示数字串的顺序，而“ ，表示节点的访问次序 证明由定义的索引树的遍历次序，此定理的结论显然成立 当我们在概念格的概念集合上建立了索引树后，在有效树节点和格节点之间便存在 了一一对应关系因此这种树节点间访问次序同样定义了格节点间的访问次序，“ ， 关系可以直接扩展为格节点间的访问次序对于两个格节点c 。和c ：，如果： ( 1 ) y ( e x t e n t ( c 1 ) ) y ( e x t e n t ( c 2 ) ) i ；t y ( e x t e n t ( c 2 ) ) 不是y ( e x t e n t ( c 1 ) ) 的前缀 则c 。 rc 2 ，这意味着c 。先于c 2 被访问 定理4 2 2 如果概念格节点c 1 所对应的索引树节点为正，它的任意一个子节点c ： 所对应的索引树节点为疋，则有正 丁互和c 2 ，c 1 成立 证明由于麟纪甩f ( c 2 ) ce x t e n t ( c 1 ) ，那么我们分以下两种情况来讨论： 如果y ( e x t e n t ( c 2 ) ) 是y ( e x t e n t ( c 1 ) ) 的一个前缀，则y ( e x t e n t ( c 2 ) ) y ( e x t e n t ( c 1 ) ) 所以c ， rc 1 又由于a ( 正) = y ( e x t e n t ( c 1 ) ) 及a ( 互) = y ( e x t e n t ( c 2 ) ) ，根据上面的定理4 2 1 ，有 疋 7 正 4 3 算法原理 本节介绍利用树结构组织，按升序( r ) 访问初始概念格，能有效地缩小产生子格节 0 点的搜索范围以及新增格节点的父节点和子节点的搜索范围即利用树结构组织访问概 念格节点，可以节省传统方法中需要反复多次比较更新结果的时间，从而有效地解决4 1 开始提到的概念格更新需解决的三个问题，最终达到快速实现属性优先的概念格渐进式 更新过程之目的 下面我们来看对于用树结构组织的初始概念格，按照升序( 丁) 来访问初始概念格， 当访问每个格节点时，如何识别出该节点的类型并执行相应的操作 首先，考察一下更新格节点的识别和执行的操作 。 1 6 第4 章树状结构组织的属性优先的概念格渐进式算法 对于树节点互，如果从树根到正的路径集合是g ( m ) 的子集，则互被称为是更新树 节点显然，格节点c ，是更新格节点当且仅当它所对应的树节点互是更新树节点更新 格节点的子节点不变，父节点可能增加某些由满足c 1 ，c 的产生子c 所生成的新增格 节点，并且去除产生子格节点( 当产生子是g 的父节点时) 其次，考察一下产生子格节点的识别和执行的操作，下面用三个定理来解决这个问 题定理4 3 1 解决产生子格节点的识别与相应的新增格节点e 。的生成问题，定理4 3 2 和定理4 3 3 限制新增格节点g 。的父节点和子节点的搜索范围 对于由产生子格节点c 。所生成的新增格节点e 。，如果另一个格节点c 满足 c 1 ，c ，则称c 。是先于c 的访问而生成的用b e f o r e ( c ) 表示所有先于c 被访问的和 先于c 而生成的节点集合，则我们有如下定理 定理4