第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201704022 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170s08.0922.010.html 利用二元拟阵K.图的一种建格方法 毛华，史明 (河北大学数学与信息科学学院，河北保定，071002)】 摘要：由于交通网络纷繁复杂，难以直观分析和直接处理。若出行者根据自己喜好和习惯决定出行策略，则需对 出行方案有清楚的了解。针对此问题，建立交通网络图一K模型，对具有带环路和重边路的复杂网络结构图，可 以完全转化为K图处理。通过概，念格理论，得到Hsse示图，方便人们对某些属性条件方案的提取，便于后续工作 处理。对K图进行研究之后发现，在特定的多个属性影响下，会形成一个三角形圈，于是结合拟阵中二元拟阵的标 准矩阵的定义，挖掘出一种特殊形式背景。根据这种形式背景的特殊性，给出基于二元拟阵的K图的概念格算法。 结合生活中的例子，验证该算法可行性。由于模型具有这种普遍性，所有结果可推广到具有类似形式背景的其他领 域研究中。 关键词：二元拟阵；标准矩阵表示；K图；二部图；图论；概念格；形式背景；Hsse示图 中图分类号：TP18文献标志码：A文章编号：1673-4785(2017)03-0333-08 中文引用格式：毛华，史明.利用二元拟阵K图的一种建格方法[J].智能系统学报，2017,12(3)：333-340. 英文引用格式：MAO Hua,SHI Ming.A constructive method of lattice using the K。diagram of binary matroid[J].CAAI transactions on intelligent systems,2017,12(3):333-340. A constructive method of lattice using the K,diagram of binary matroid MAO Hua,SHI Ming School of Mathematics and Information Science,Hebei University,Baoding 071002,China) Abstract:Because of the complexity of traffic networks,it is difficult to directly analyze and deal with them.If some travelers wish to determine their travel strategy based on their preferences and habits,they should have a clear understanding of their travel plan.To address this problem,a traffic network,K model,was established in this study.It was used to elucidate how to transfer complex networks comprising loops or multiple edges to the K. diagram.With the assistance of formal concept analysis,the corresponding Hasse diagram of the K model was provided.The Hasse diagram facilitates travelers to extract some attributes under certain preconditions,after which the travelers can easily continue their work.Hence,the study of the K.diagram revealed that a triangle circle would form under some effects of specific multiple attributes.Thus,combining with the standard definition of the matrix for binary matroids,a special formal context was obtained.According to the particularity of the formal context,an algorithm was proposed based on the binary matroids for the K diagram.Utilizing an example,the feasibility of the proposed method was proven.Because the model is universal,the discussions of this research can be extended to other fields with similar formal context. Keywords:binary matroid;standard matrix representative;K.diagram;bipartite graph;graph theory;concept lattice:formal context:Hasse diagram 现代经济发展中，大城市经济圈)]内至少有一 式现已成为城市经济圈发展的增长级。实践证明， 个或多个经济发达并具有较强城市功能的中心城 经济圈中以三个地区为最好，例如京津冀经济圈、 市，以便带动周围其他城市的发展，这种经济圈模 长江三角洲经济圈、珠三角经济圈等。另外，从数 学方面分析，若将经济圈中每个城市视为一个顶 收稿日期：2017-04-19.网络出版日期：2017-05-08. 点，城市间有路可达时连接为边，则一个经济圈为 基金项目：国家自然科学基金项目(61572011). 一个图。依据图论的知识可知，在多边形图中，三 通信作者：史明.E-mail:ming1254610676@163.com
第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ． ２０１７０４０２２ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０５０８．０９２２．０１０．ｈｔｍｌ 利用二元拟阵 Ｋ ｎ 图的一种建格方法 毛华，史明 （河北大学 数学与信息科学学院，河北 保定， ０７１００２） 摘 要：由于交通网络纷繁复杂，难以直观分析和直接处理。 若出行者根据自己喜好和习惯决定出行策略，则需对 出行方案有清楚的了解。 针对此问题，建立交通网络图———Ｋｎ模型，对具有带环路和重边路的复杂网络结构图，可 以完全转化为 Ｋｎ图处理。 通过概念格理论，得到 Ｈａｓｓｅ 示图，方便人们对某些属性条件方案的提取，便于后续工作 处理。 对 Ｋｎ图进行研究之后发现，在特定的多个属性影响下，会形成一个三角形圈，于是结合拟阵中二元拟阵的标 准矩阵的定义，挖掘出一种特殊形式背景。 根据这种形式背景的特殊性，给出基于二元拟阵的 Ｋｎ图的概念格算法。 结合生活中的例子，验证该算法可行性。 由于模型具有这种普遍性，所有结果可推广到具有类似形式背景的其他领 域研究中。 关键词：二元拟阵；标准矩阵表示；Ｋｎ图；二部图；图论；概念格；形式背景；Ｈａｓｓｅ 示图 中图分类号：ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３３３－０８ 中文引用格式：毛华，史明．利用二元拟阵 Ｋｎ 图的一种建格方法［Ｊ］． 智能系统学报， ２０１７， １２（３）： ３３３－３４０． 英文引用格式： ＭＡＯ Ｈｕａ， ＳＨＩ Ｍｉｎｇ． Ａ ｃｏｎｓｔｒｕｃｔｉｖｅ ｍｅｔｈｏｄ ｏｆ ｌａｔｔｉｃｅ ｕｓｉｎｇ ｔｈｅ Ｋｎ ｄｉａｇｒａｍ ｏｆ ｂｉｎａｒｙ ｍａｔｒｏｉｄ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３３３－３４０． Ａ ｃｏｎｓｔｒｕｃｔｉｖｅ ｍｅｔｈｏｄ ｏｆ ｌａｔｔｉｃｅ ｕｓｉｎｇ ｔｈｅ Ｋｎ ｄｉａｇｒａｍ ｏｆ ｂｉｎａｒｙ ｍａｔｒｏｉｄ ＭＡＯ Ｈｕａ， ＳＨＩ Ｍｉｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ， Ｈｅｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ， Ｂａｏｄｉｎｇ ０７１００２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｅｃａｕｓｅ ｏｆ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｒａｆｆｉｃ ｎｅｔｗｏｒｋｓ， ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ ｔｏ ｄｉｒｅｃｔｌｙ ａｎａｌｙｚｅ ａｎｄ ｄｅａｌ ｗｉｔｈ ｔｈｅｍ． Ｉｆ ｓｏｍｅ ｔｒａｖｅｌｅｒｓ ｗｉｓｈ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅｉｒ ｔｒａｖｅｌ ｓｔｒａｔｅｇｙ ｂａｓｅｄ ｏｎ ｔｈｅｉｒ ｐｒｅｆｅｒｅｎｃｅｓ ａｎｄ ｈａｂｉｔｓ， ｔｈｅｙ ｓｈｏｕｌｄ ｈａｖｅ ａ ｃｌｅａｒ ｕｎｄｅｒｓｔａｎｄｉｎｇ ｏｆ ｔｈｅｉｒ ｔｒａｖｅｌ ｐｌａｎ． Ｔｏ ａｄｄｒｅｓｓ ｔｈｉｓ ｐｒｏｂｌｅｍ， ａ ｔｒａｆｆｉｃ ｎｅｔｗｏｒｋ， Ｋｎ ｍｏｄｅｌ， ｗａｓ ｅｓｔａｂｌｉｓｈｅｄ ｉｎ ｔｈｉｓ ｓｔｕｄｙ． Ｉｔ ｗａｓ ｕｓｅｄ ｔｏ ｅｌｕｃｉｄａｔｅ ｈｏｗ ｔｏ ｔｒａｎｓｆｅｒ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ ｃｏｍｐｒｉｓｉｎｇ ｌｏｏｐｓ ｏｒ ｍｕｌｔｉｐｌｅ ｅｄｇｅｓ ｔｏ ｔｈｅ Ｋｎ ｄｉａｇｒａｍ． Ｗｉｔｈ ｔｈｅ ａｓｓｉｓｔａｎｃｅ ｏｆ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ， ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ Ｈａｓｓｅ ｄｉａｇｒａｍ ｏｆ ｔｈｅ Ｋｎ ｍｏｄｅｌ ｗａｓ ｐｒｏｖｉｄｅｄ． Ｔｈｅ Ｈａｓｓｅ ｄｉａｇｒａｍ ｆａｃｉｌｉｔａｔｅｓ ｔｒａｖｅｌｅｒｓ ｔｏ ｅｘｔｒａｃｔ ｓｏｍｅ ａｔｔｒｉｂｕｔｅｓ ｕｎｄｅｒ ｃｅｒｔａｉｎ ｐｒｅｃｏｎｄｉｔｉｏｎｓ， ａｆｔｅｒ ｗｈｉｃｈ ｔｈｅ ｔｒａｖｅｌｅｒｓ ｃａｎ ｅａｓｉｌｙ ｃｏｎｔｉｎｕｅ ｔｈｅｉｒ ｗｏｒｋ． Ｈｅｎｃｅ， ｔｈｅ ｓｔｕｄｙ ｏｆ ｔｈｅ Ｋｎ ｄｉａｇｒａｍ ｒｅｖｅａｌｅｄ ｔｈａｔ ａ ｔｒｉａｎｇｌｅ ｃｉｒｃｌｅ ｗｏｕｌｄ ｆｏｒｍ ｕｎｄｅｒ ｓｏｍｅ ｅｆｆｅｃｔｓ ｏｆ ｓｐｅｃｉｆｉｃ ｍｕｌｔｉｐｌｅ ａｔｔｒｉｂｕｔｅｓ． Ｔｈｕｓ， ｃｏｍｂｉｎｉｎｇ ｗｉｔｈ ｔｈｅ ｓｔａｎｄａｒｄ ｄｅｆｉｎｉｔｉｏｎ ｏｆ ｔｈｅ ｍａｔｒｉｘ ｆｏｒ ｂｉｎａｒｙ ｍａｔｒｏｉｄｓ， ａ ｓｐｅｃｉａｌ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｗａｓ ｏｂｔａｉｎｅｄ． Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｐａｒｔｉｃｕｌａｒｉｔｙ ｏｆ ｔｈｅ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ， ａｎ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｂｉｎａｒｙ ｍａｔｒｏｉｄｓ ｆｏｒ ｔｈｅ Ｋｎ ｄｉａｇｒａｍ． Ｕｔｉｌｉｚｉｎｇ ａｎ ｅｘａｍｐｌｅ， ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｗａｓ ｐｒｏｖｅｎ． Ｂｅｃａｕｓｅ ｔｈｅ ｍｏｄｅｌ ｉｓ ｕｎｉｖｅｒｓａｌ， ｔｈｅ ｄｉｓｃｕｓｓｉｏｎｓ ｏｆ ｔｈｉｓ ｒｅｓｅａｒｃｈ ｃａｎ ｂｅ ｅｘｔｅｎｄｅｄ ｔｏ ｏｔｈｅｒ ｆｉｅｌｄｓ ｗｉｔｈ ｓｉｍｉｌａｒ ｆｏｒｍａｌ ｃｏｎｔｅｘｔ． Ｋｅｙｗｏｒｄｓ： ｂｉｎａｒｙ ｍａｔｒｏｉｄ； ｓｔａｎｄａｒｄ ｍａｔｒｉｘ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ； Ｋｎ ｄｉａｇｒａｍ； ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ； ｇｒａｐｈ ｔｈｅｏｒｙ； ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ； ｆｏｒｍａｌ ｃｏｎｔｅｘｔ； Ｈａｓｓｅ ｄｉａｇｒａｍ 收稿日期：２０１７－０４－１９． 网络出版日期：２０１７－０５－０８． 基金项目：国家自然科学基金项目（６１５７２０１１）． 通信作者：史明． Ｅ⁃ｍａｉｌ：ｍｉｎｇ１２５４６１０６７６＠ １６３．ｃｏｍ． 现代经济发展中，大城市经济圈［１］ 内至少有一 个或多个经济发达并具有较强城市功能的中心城 市，以便带动周围其他城市的发展，这种经济圈模 式现已成为城市经济圈发展的增长级。 实践证明， 经济圈中以三个地区为最好，例如京津冀经济圈、 长江三角洲经济圈、珠三角经济圈等。 另外，从数 学方面分析，若将经济圈中每个城市视为一个顶 点，城市间有路可达时连接为边，则一个经济圈为 一个图。 依据图论的知识可知，在多边形图中，三
·334 智能系统学报 第12卷 个顶点构成的圈（即三角形）是最稳定的，因此本文 [L,D]是M在模2域上的一个标准矩阵表示，其中 考虑的圈将以三角形为基本单元。 p(b)是I中第i列，而p(e)是D中的第j列，1≤ 随着经济的发展，许多城市面临着严重的交通 i≤r,1≤j≤qo 拥堵。若出行者对自己要经过交通网络的路径、费 引理14 在一个具有n个顶点的无向完全图 用、时间等能够以清晰地、直观地方式得到，则完成 任务的效率将会大大提高。关于在复杂的交通网 中，包含的边数为(n-1) 络的条件下，研究合理的出行路径模型和算法，请 定义4)]形式背景K=(G,M,)定义为一个 参见文献[2-9]。基于多属性条件路径选择问题， 三元数组，其中G中的元素被称为对象，M中的元 文献[2-9]以及目前掌握的材料中，均没有涉及对 素被称为属性。IGxM,用glm表示(g,m)∈I,即 于交通网路信息提取的概念格[1]可视化研究。 对象g具有属性m。 概念格建立了对象和属性之间的一种概念层 定义5)形式背景(G,M,I)中的概念定义为 次结构，是数据分析和规则提取的一种有效工具。 元素对(A,B),其中A二G,BCM,A称为概念的外 Whitney!在1935年首次提出的拟阵已经被广泛 延，B称为概念的内涵，并且满足以下条件： 地应用于信息编码[]和网络安全[]等领域。将拟 1)B'={a∈GHb∈B,alb},A'={b∈M|Ha∈ 阵与概念格理论结合、图论[4]与概念格理论结合 来解决问题，已有许多成功的案例[6-2) A,alb 2)ACA",BCB"; 由于现实生活中，人们出行受多个属性条件的 限制，针对这些限制，经过研究发现K。简单图中形 3)(A)'=04,(9B,)'=0B'。 成三角形圈的一种特殊性质。由此，可以对复杂的 定义6设(A1,B,)、(A2,B2)是L(G,M,I) 交通网络进行分析、转化，形成K简单图。进而，能 中的两个概念，定义二元关系(A1,B,)≤(A2,B2)台 够建立网络模型，构建模型所对应的关联矩阵。依 ACA2台B,CB2,称(A1,B,)是(A2,B2)的子概念， 据K,图所产生的特殊形式背景，建立概念格信息提 (A2,B2)是(A1,B,)的父概念。若不存在概念(A3, 取方法。从而，给出基于二元拟阵K图的一种建格 B3)使得(A1,B1)≤(A3,B3)≤(A2,B2)成立，则称 方法，并利用具体实例验证方法的正确性与有效性。 (A1,B)是(A2,B2)的直接子概念，(A2,B2)是(A1, 1 预备知识 B,)的直接父概念。 不难证明这种父概念一子概念关系（也称泛 本节主要介绍网络K图、拟阵和概念格一些定 化-特化关系)是L(G,M,I)上的一个偏序关系。事 义与相关结论。有关图的基本概念和完全图的定 实上L(G,M,)关于该偏序关系是一个完备格，称 义，读者请参见文献[14]。有关二元拟阵和图的拟 为形式背景(G,M,I)的概念格，记为L(G,M,I)。 阵可表示性请参见文献[11]。 引理2]设(G,M,)是一个形式背景，则 定义1设任意（无向）图G=(V,E),其中 L(G,M,)关于上面定义的序“≤”构成的是完备 顶点集V={u1,2,…,vn},边集E={e1,e2,…,e.}。 格，其中上下确界由下式给出： 用m表示顶点：与边e,关联的次数，可能取值为 0,1,2,称所得矩阵M(G)=（m:)x.为图G的关联 V(4,B)=(A)”,0B) 矩阵。 Λje(4,B)=(∩A,(UB)") 定义24V(G)=XUY,X∩Y=⑦，X中任二 为了模型的建立和讨论表述简捷，给出如下几 项不相邻，Y中任二项不相邻，则G为二部图；若X 个定义。 中每个顶点皆与Y中一切顶点相邻，则G为完全二 定义7含圈基：在K图中满足从一个顶点出 部图，记Km,a,其中m=|x|,n=|Y|。 发，到其他n-1个顶点的相连接的边叫做含圈基。 定义3)设M是关于E={b1,b2,…,b,e1, 定义8基顶点：在K,图中满足从一个顶点出 e2,…,e,}的一个拟阵，其中B=b1,b2,…,b,}是M 发包含的所有相连的含圈基的顶点叫做基顶点。 的一个基。设C,是BU{e,}所含的基本圈，定义r× 定义9基最小圈：在一个三角形最小圈中，满 足一个最小圈中包含两个基的三角形圈，叫做基最 q阶矩阵D=(dg),其中d,= ,若b,∈C,则A= 0,其他 小圈
个顶点构成的圈（即三角形）是最稳定的，因此本文 考虑的圈将以三角形为基本单元。 随着经济的发展，许多城市面临着严重的交通 拥堵。 若出行者对自己要经过交通网络的路径、费 用、时间等能够以清晰地、直观地方式得到，则完成 任务的效率将会大大提高。 关于在复杂的交通网 络的条件下，研究合理的出行路径模型和算法，请 参见文献［２－９］。 基于多属性条件路径选择问题， 文献［２－９］以及目前掌握的材料中，均没有涉及对 于交通网路信息提取的概念格［１０］可视化研究。 概念格建立了对象和属性之间的一种概念层 次结构，是数据分析和规则提取的一种有效工具。 Ｗｈｉｔｎｅｙ ［１１］在 １９３５ 年首次提出的拟阵已经被广泛 地应用于信息编码［１２］ 和网络安全［１３］ 等领域。 将拟 阵与概念格理论结合、图论［１４－１５］与概念格理论结合 来解决问题，已有许多成功的案例［１６－２１］ 。 由于现实生活中，人们出行受多个属性条件的 限制，针对这些限制，经过研究发现 Ｋｎ 简单图中形 成三角形圈的一种特殊性质。 由此，可以对复杂的 交通网络进行分析、转化，形成 Ｋｎ 简单图。 进而，能 够建立网络模型，构建模型所对应的关联矩阵。 依 据 Ｋｎ 图所产生的特殊形式背景，建立概念格信息提 取方法。 从而，给出基于二元拟阵 Ｋｎ 图的一种建格 方法，并利用具体实例验证方法的正确性与有效性。 １ 预备知识 本节主要介绍网络 Ｋｎ 图、拟阵和概念格一些定 义与相关结论。 有关图的基本概念和完全图的定 义，读者请参见文献［１４］。 有关二元拟阵和图的拟 阵可表示性请参见文献［１１］。 定义 １ ［２２］ 设任意（无向）图 Ｇ ＝ （ Ｖ，Ｅ），其中 顶点集 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝，边集 Ｅ ＝ ｛ ｅ１ ，ｅ２ ，…，ｅｅ ｝。 用 ｍｉｊ表示顶点 ｖｉ 与边 ｅｊ 关联的次数，可能取值为 ０，１，２，称所得矩阵 Ｍ（Ｇ） ＝ （ｍｉｊ ）ｎ×ｅ为图 Ｇ 的关联 矩阵。 定义 ２ ［１４］ Ｖ（Ｇ）＝ Ｘ∪Ｙ，Ｘ∩Ｙ ＝ ⌀，Ｘ 中任二 项不相邻，Ｙ 中任二项不相邻，则 Ｇ 为二部图；若 Ｘ 中每个顶点皆与 Ｙ 中一切顶点相邻，则 Ｇ 为完全二 部图，记 Ｋｍ，ｎ ，其中 ｍ ＝ Ｘ ，ｎ ＝ Ｙ 。 定义 ３ ［１１］ 设 Ｍ 是关于 Ｅ ＝ ｛ ｂ１ ，ｂ２ ，…，ｂｒ，ｅ１ ， ｅ２ ，…，ｅｑ｝的一个拟阵，其中 Ｂ ＝ ｛ｂ１ ，ｂ２ ，…，ｂｒ｝是 Ｍ 的一个基。 设 Ｃｊ 是 Ｂ∪｛ｅｊ｝所含的基本圈，定义 ｒ× ｑ 阶矩阵Ｄ ＝ （ ｄｉｊ ），其中 ｄｉｊ ＝ １， 若 ｂｉ∈Ｃｊ ０， 其他 { ，则Ａ＝ ［Ｉｒ Ｄ］是 Ｍ 在模 ２ 域上的一个标准矩阵表示，其中 φ（ｂｉ）是 Ｉｒ 中第 ｉ 列，而 φ（ｅｊ）是 Ｄ 中的第 ｊ 列，１≤ ｉ≤ｒ，１≤ｊ≤ｑ。 引理 １ ［１４］ 在一个具有 ｎ 个顶点的无向完全图 中，包含的边数为 ｎ（ｎ－１） ２ 。 定义 ４ ［１７］ 形式背景 Ｋ ＝ （Ｇ，Ｍ，Ｉ）定义为一个 三元数组，其中 Ｇ 中的元素被称为对象，Ｍ 中的元 素被称为属性。 Ｉ⊆Ｇ×Ｍ，用 ｇＩｍ 表示（ｇ，ｍ）∈Ｉ，即 对象 ｇ 具有属性 ｍ。 定义 ５ ［１７］ 形式背景（Ｇ，Ｍ，Ｉ）中的概念定义为 元素对（Ａ，Ｂ），其中 Ａ⊆Ｇ，Ｂ⊆Ｍ，Ａ 称为概念的外 延，Ｂ 称为概念的内涵，并且满足以下条件： １）Ｂ′＝ ｛ａ∈Ｇ ∀ｂ∈Ｂ，ａＩｂ｝，Ａ′ ＝ ｛ｂ∈Ｍ ∀ａ∈ Ａ，ａＩｂ｝； ２）Ａ⊆Ａ″，Ｂ⊆Ｂ″； ３）（∪ ｊ∈Ｊ Ａｊ）′＝∩ ｊ∈Ｊ Ａｊ ′，（∪ ｊ∈Ｊ Ｂｊ）′＝∩ ｊ∈Ｊ Ｂｊ ′。 定义 ６ ［１７］ 设（Ａ１ ，Ｂ１ ）、（Ａ２ ，Ｂ２ ）是 Ｌ（Ｇ，Ｍ，Ｉ） 中的两个概念，定义二元关系（Ａ１ ，Ｂ１ ）≤（Ａ２ ，Ｂ２ ）⇔ Ａ１⊆Ａ２⇔Ｂ１⊆Ｂ２ ，称（Ａ１ ，Ｂ１ ）是（ Ａ２ ，Ｂ２ ） 的子概念， （Ａ２ ，Ｂ２ ）是（Ａ１ ，Ｂ１ ）的父概念。 若不存在概念（ Ａ３ ， Ｂ３ ）使得（Ａ１ ，Ｂ１ ） ≤（Ａ３ ，Ｂ３ ） ≤（Ａ２ ，Ｂ２ ） 成立，则称 （Ａ１ ，Ｂ１ ）是（Ａ２ ，Ｂ２ ）的直接子概念，（Ａ２ ，Ｂ２ ）是（Ａ１ ， Ｂ１ ）的直接父概念。 不难证明这种父概念 － 子概念关系（ 也称泛 化－特化关系）是 Ｌ（Ｇ，Ｍ，Ｉ）上的一个偏序关系。 事 实上 Ｌ（Ｇ，Ｍ，Ｉ）关于该偏序关系是一个完备格，称 为形式背景（Ｇ，Ｍ，Ｉ）的概念格，记为 Ｌ（Ｇ，Ｍ，Ｉ）。 引理 ２ ［１７］ 设（ Ｇ，Ｍ，Ｉ） 是一个形式背景，则 Ｌ（Ｇ，Ｍ，Ｉ）关于上面定义的序“ ≤” 构成的是完备 格，其中上下确界由下式给出： ∨ｊ∈Ｊ（Ａｊ，Ｂｊ） ＝ （∪ ｊ∈Ｊ Ａｊ ( ) ″， ∩ ｊ∈Ｊ Ｂｊ） ∧ｊ∈Ｊ（Ａｊ，Ｂｊ） ＝ （∩ ｊ∈Ｊ Ａｊ，（∪ ｊ∈Ｊ Ｂｊ）″） 为了模型的建立和讨论表述简捷，给出如下几 个定义。 定义 ７ 含圈基：在 Ｋｎ 图中满足从一个顶点出 发，到其他 ｎ－１ 个顶点的相连接的边叫做含圈基。 定义 ８ 基顶点：在 Ｋｎ 图中满足从一个顶点出 发包含的所有相连的含圈基的顶点叫做基顶点。 定义 ９ 基最小圈：在一个三角形最小圈中，满 足一个最小圈中包含两个基的三角形圈，叫做基最 小圈。 ·３３４· 智 能 系 统 学 报 第 １２ 卷
第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·335· 模型的建立 很难给人们带来直接帮助，需要对交通运输网络进 行简化和直观化，得到一个简化的网络。若出行者 图论主要研究图的拓扑性质，为任何一个包含 需要计算出自己所居住的城市和其他任意两个城 某种二元关系系统提供一种分析和描述模型。众 市的距离和，即第1节定义9中的基最小圈，判断走 所周知，交通网络可以用图表示出来，也可把交通 哪个基最小圈距离和最短时，探究交通网络K图模 网络里的距离当作两点之间的权值加入进去。 型中的最小经济圈所需出行的路径距离就变得有 复杂网络中的交通网络对应图论里一类特殊 意义了。 的图结构，具有与应用相关的很多重要特征。对于 2.2模型的条件 一些网络中出现的复杂的网络，作如下处理。 设有个城市，每个城市看作一个顶点，两个城 1)对于两个顶点之间具有多重边的情况，选择 市之间有路可达时，用一条线相连接，建立城市网 其中权值最小的边。 络图。图中顶点用1,2，…，。表示，组成集合V= 2)当两个顶点之间的权值一样时，任意选择其 {1,2,…,心}。网络图中，之间有路径可达，记 中一条边，固定下来，成为最熟悉的一条道路。 相连接的边为em,将此交通网络图记为G=(V,E), 3)对于带环图的这种情况，因为实际问题考虑 得G为一个有限无向图。出行者从给定的一个顶 的是对于一个工厂的运输，自身运输没有任何实际 点城市，出发去办事，要求路径中必须经过两个顶 的意义。例如：如果是一家超市，自身对于自身运 点城市（除去给定城市顶点以外的其他任意两个顶 输也没有意义，所以不予考虑。 点城市)，再返回到出发城市顶点1。由于出行者 具有重边或有环的图都可以转化为简单图应 走的道路为一个三角形，现在的问题是要选择一个 对出行问题，因此复杂网络图可以转化为简单图， 三角形在距离和花费的时间都少的三角形作为出 用以讨论相应的出行问题。由于在具有n个顶点的 行者的最终出行方案，这就需要找到所有可能的出 简单图中，K图结构最复杂，所以只要解决了K。图 行方法，换句话说，出行者需要出行前找到所有需 的出行问题，其他的简单图的出行问题将会迎刃而 要走过的路径和出行方案，以便从中选择最佳方 解。对于非K的n个顶点的简单图，因为它们是 案，这些方案对决策者综合路径距离、时间、花费决 K的子图，所以可以通过加边，使其成为K图，只 策时有重要的意义，可以帮助其更加直观、快速地 需将新加边的权值定义为0，采用本文的方法，完全 做决定，节约决策时间。 可以解决出行问题。基于以上的讨论，只需解决具 2.3问题的分析 有K,图这样的交通网络的出行问题，因此本文只研 交通城市之间的无向图G进行转化后是顶点 究K图。 为n的完全图，记G为K,图。因K,图对应的关联 现有n个城市，任意两个城市均由交通道路连 矩阵满足二元拟阵M,知定义7的含圈基满足定义 接。一位出行者要从自己所居住的城市去其他n-1 3的拟阵M,即实际生活中人们出行方案里的最小 个城市办事情，要求到达其他任意两个城市后再回 三角形圈。于是在K,图的二元拟阵的标准矩阵表 到自己所居住的城市，现在的问题是：如何找到以3 示如下：在对应组成基本圈的三条边下标记1，没有 个城市为三角形经济圈的一个出行方案。 组成基本圈的边下标记0，然后把得到的矩阵作为 首先建立一个网络模型，构建其关联矩阵。由 含0和1的形式背景。在上面进行概念格的探索和 于关联矩阵是一个0-1矩阵，信息提取中的任一个 证明时发现，在K图中将二元拟阵中的基本圈即定 形式背景可视为一个0-1矩阵，因此依据形式背景 义9的基最小圈，作为对象，每两个顶点之间相连的 的特殊性，建立概念格信息提取方法，进而找到人 边作为属性，建立形式背景，找寻概念会遵循一定 们所需的最适合出行方案。 的数学规律，运用此规律进行建格，速度很快。 2.1问题的提出 2.4模型的解决 在不同城市间构建现代化交通网络，实现城市 2.4.1K。图的建格模型 间交通一体化，将会极大方便交通出行。问题是： 根据定义3给出K图的标准矩阵表示。当顶 如何在众多出行方案中选取合适的方案，成为人们 点n=3时，根据引理1的公式得边数为3，含圈基的 出行前需要解决的问题。交通运输网络错综复杂， 个数为-1=2，与其中一个顶点相连接构成的基最
２ 模型的建立 图论主要研究图的拓扑性质，为任何一个包含 某种二元关系系统提供一种分析和描述模型。 众 所周知，交通网络可以用图表示出来，也可把交通 网络里的距离当作两点之间的权值加入进去。 复杂网络中的交通网络对应图论里一类特殊 的图结构，具有与应用相关的很多重要特征。 对于 一些网络中出现的复杂的网络，作如下处理。 １）对于两个顶点之间具有多重边的情况，选择 其中权值最小的边。 ２） 当两个顶点之间的权值一样时，任意选择其 中一条边，固定下来，成为最熟悉的一条道路。 ３）对于带环图的这种情况，因为实际问题考虑 的是对于一个工厂的运输，自身运输没有任何实际 的意义。 例如：如果是一家超市，自身对于自身运 输也没有意义，所以不予考虑。 具有重边或有环的图都可以转化为简单图应 对出行问题，因此复杂网络图可以转化为简单图， 用以讨论相应的出行问题。 由于在具有 ｎ 个顶点的 简单图中，Ｋｎ 图结构最复杂，所以只要解决了 Ｋｎ 图 的出行问题，其他的简单图的出行问题将会迎刃而 解。 对于非 Ｋｎ 的 ｎ 个顶点的简单图，因为它们是 Ｋｎ 的子图，所以可以通过加边，使其成为 Ｋｎ 图，只 需将新加边的权值定义为 ０，采用本文的方法，完全 可以解决出行问题。 基于以上的讨论，只需解决具 有 Ｋｎ 图这样的交通网络的出行问题，因此本文只研 究 Ｋｎ 图。 现有 ｎ 个城市，任意两个城市均由交通道路连 接。 一位出行者要从自己所居住的城市去其他 ｎ－１ 个城市办事情，要求到达其他任意两个城市后再回 到自己所居住的城市，现在的问题是：如何找到以 ３ 个城市为三角形经济圈的一个出行方案。 首先建立一个网络模型，构建其关联矩阵。 由 于关联矩阵是一个 ０－１ 矩阵，信息提取中的任一个 形式背景可视为一个 ０－１ 矩阵，因此依据形式背景 的特殊性，建立概念格信息提取方法，进而找到人 们所需的最适合出行方案。 ２．１ 问题的提出 在不同城市间构建现代化交通网络，实现城市 间交通一体化，将会极大方便交通出行。 问题是： 如何在众多出行方案中选取合适的方案，成为人们 出行前需要解决的问题。 交通运输网络错综复杂， 很难给人们带来直接帮助，需要对交通运输网络进 行简化和直观化，得到一个简化的网络。 若出行者 需要计算出自己所居住的城市和其他任意两个城 市的距离和，即第 １ 节定义 ９ 中的基最小圈，判断走 哪个基最小圈距离和最短时，探究交通网络 Ｋｎ图模 型中的最小经济圈所需出行的路径距离就变得有 意义了。 ２．２ 模型的条件 设有 ｎ 个城市，每个城市看作一个顶点，两个城 市之间有路可达时，用一条线相连接，建立城市网 络图。 图中顶点用 ｖ１ ，ｖ２ ，…，ｖｎ 表示，组成集合 Ｖ ＝ ｛ｖ１ ，ｖ２ ，…，ｖｎ ｝。 网络图中 ｖｉ，ｖｊ 之间有路径可达，记 相连接的边为 ｅｉｊ，将此交通网络图记为 Ｇ ＝ （Ｖ，Ｅ）， 得 Ｇ 为一个有限无向图。 出行者从给定的一个顶 点城市 ｖ１ 出发去办事，要求路径中必须经过两个顶 点城市（除去给定城市顶点以外的其他任意两个顶 点城市），再返回到出发城市顶点 ｖ１ 。 由于出行者 走的道路为一个三角形，现在的问题是要选择一个 三角形在距离和花费的时间都少的三角形作为出 行者的最终出行方案，这就需要找到所有可能的出 行方法，换句话说，出行者需要出行前找到所有需 要走过的路径和出行方案，以便从中选择最佳方 案， 这些方案对决策者综合路径距离、时间、花费决 策时有重要的意义，可以帮助其更加直观、快速地 做决定，节约决策时间。 ２．３ 问题的分析 交通城市之间的无向图 Ｇ 进行转化后是顶点 为 ｎ 的完全图，记 Ｇ 为 Ｋｎ 图。 因 Ｋｎ 图对应的关联 矩阵满足二元拟阵 Ｍ，知定义 ７ 的含圈基满足定义 ３ 的拟阵 Ｍ，即实际生活中人们出行方案里的最小 三角形圈。 于是在 Ｋｎ 图的二元拟阵的标准矩阵表 示如下：在对应组成基本圈的三条边下标记 １，没有 组成基本圈的边下标记 ０，然后把得到的矩阵作为 含 ０ 和 １ 的形式背景。 在上面进行概念格的探索和 证明时发现，在 Ｋｎ 图中将二元拟阵中的基本圈即定 义 ９ 的基最小圈，作为对象，每两个顶点之间相连的 边作为属性，建立形式背景，找寻概念会遵循一定 的数学规律，运用此规律进行建格，速度很快。 ２．４ 模型的解决 ２．４．１ Ｋｎ 图的建格模型 根据定义 ３ 给出 Ｋｎ 图的标准矩阵表示。 当顶 点 ｎ ＝ ３ 时，根据引理 １ 的公式得边数为 ３，含圈基的 个数为 ｎ－１ ＝ ２，与其中一个顶点相连接构成的基最 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３５·
·336· 智能系统学报 第12卷 小圈个数为边数(-1)减去定义7含圈基数n-1, 义7含圈基个数为n-1时，与定义8基顶点相连接 2 的每个基b1,b2,…,b-1对应的对象个数为n-2个。 以此类推，得到表1。 2)根据定义9含两个基的基最小圈最多有 表1顶点数与基最小圈的规律 条重边。 Table 1 Vertex number and the basis of the smallest circle 证明首先证明第1)条。在表2中，b,对应着 of the law 的对象为n-2个，因为b,≠b2,所以对应的对象就为 顶点 边数 含圈基 基最小圈 n-2个，即b1≠b。其次，证明第2)条。若两个基 3 3 2 1 最小圈含有2个相同的边，根据定义9可知：假设 6 2 3 C1≠C2,b1∈C1,b2∈C2,若(b1Ub2)∈(C,∩C2),则 J 10 4 6 推出C,=C2,与条件中两个基最小圈含有2个相同 6 15 10 的边矛盾，即C,≠C,矛盾。所以含两个基的基最小 1 21 6 15 圈最多有一条重边。 定理1K图对应的形式背景概念格有且仅有 n-1 n(n-1)-(m-1) 2 4层。 证明根据定义4、定义5、定义6及引理3中 将图G=(V,E)对应的拟阵M中定义9基最小 圈集O视为形式背景中的对象集，将图G的边集E 的第1)条的概念。第1层：0={C1,C2,…,Cc,}对 视为属性集P,圈C:中含有某条边e时，记C,e值 应的属性集P={}可以表示为(C,C2Cc1,{})∈ 为1，否则为0，得到形式背景(0，P,I),对象集0= L)。第2层：每个基对应n-2个圈，设为C, {C1,C2,…,Cn},属性P={b,b2,…,bn}。特别地， C2,…,Cn-20证任意基b:∈B={b1,b2,…,bn-1}, 当图G=(V,E)为K,图时，图G=(V,E)对应的形式 (i=1,2,…,n-1),设(C1C2…Cn-2,b:),其中b;'= 背景L(0a,Pm,1n）如表2所示。 CC2…C。-2,根据引理3中第1)条，0nb,=⑦， 表2K.图的形式背景L(On,Pmla) |0|=0,{b:}|=1且☑￠{b:}且不存在任意集合 Table 2 Formal context L(O,PI)of K.diagram A满足☑二A二{b:}。所以它们之间不会产生其他 b b, ba-1 bn(n-1) 的概念。第3层：设(C1C2…Cn-2,b,）与(C,C2… 2 G 10 0 Cn3,b2)eL),所以设(C,…C。3,(b,b2)")=(C1 0 G 0 1 0 C2…Cn-2,b,)A(C1C2…Cn-3,b2),由引理3中第2) 0 条知C,=C2=…=C-3,取代表圈C,由基最小圈定 C3 1 1 0 1 0 义当且仅当存在b3∈C1,则(C1,bbb3)是概念，由 0 任意性知(C:,C,)均为概念，其中C:'为C:包含的3 Ca-D-(-1) 0 0 1 条边。第4层：(C1,b1b2b3)与(C2,b,b,b,)∈L4 定义10在K。图的形式背景L(Oa,Pa,Im) (0,b)。因为存在集合B={b1,b2,b3,…,b}, 对应的概念格L(0,P,)中给出“层”的定义： 满足0二BC{C},即第4层表示为（☑，{b,b2, 设L(0,P,I)最大元为A即第一层，对任意X∈ b3,…,b(a})。 L(O,P,I)|{A},设A到X的距离为n。也就是，当 定理2K,图模型建立的概念格L(K)的第2 区间[X,A]二L(O,P,)最长链的长度为r,(r=1, 层和第3层的Hasse示图组成一个二部图。 2,3,…,n),则设X为第m层，m=r+1,记第m层为 证明根据定义2（二部图）的定义，二部图G= m=L)。设概念格L(O,P,I)的Hasse示图记为 (V,V2,E)由顶点集V,和V及边集ECV,×V2组 H(L)。由表2发现，当n=4时，根据L(Oa,Pn, 成，={x1,x2,…,x},2={y1,y2,…,y},则二部 In)={(P',P)}得对应的概念为(C3C2C1,{})∈ 图G=(V,V2,E)的伴随矩阵为二元矩阵A(a),这 L;(C,C3,b1),(C,C2,b2),(C,C2,b）eL2;(C3, 里a=1,当且仅当(x:,y)∈E。设V1为对象集，V bsbb2),(C1,b,b,b3),(C2,bbb3)∈L):({, 为属性集，则二部图的伴随矩阵就是形式背景。二 bsb,b,bb,b1)∈L。 部图G=(V,V2,E)由两个非交顶点集V,V2组成， 引理31)根据完全图的定义和表1知，当定 且G的每条边的顶点分别在V,V2中。设Y,是第2
小圈个数为边数 ｎ（ｎ－１） ２ 减去定义 ７ 含圈基数 ｎ－１， 以此类推，得到表 １。 表 １ 顶点数与基最小圈的规律 Ｔａｂｌｅ １ Ｖｅｒｔｅｘ ｎｕｍｂｅｒ ａｎｄ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｓｍａｌｌｅｓｔ ｃｉｒｃｌｅ ｏｆ ｔｈｅ ｌａｗ 顶点 边数 含圈基 基最小圈 ３ ３ ２ １ ４ ６ ３ ３ ５ １０ ４ ６ ６ １５ ５ １０ ７ ２１ ６ １５ ︙ ︙ ︙ ︙ ｎ … ｎ－１ ｎ（ｎ－１） ２ －（ｎ－１） 将图 Ｇ ＝ （Ｖ，Ｅ）对应的拟阵 Ｍ 中定义 ９ 基最小 圈集 Ｏ 视为形式背景中的对象集，将图 Ｇ 的边集 Ｅ 视为属性集 Ｐ，圈 Ｃｉ 中含有某条边 ｅｊ 时，记 Ｃｉ ｅｊ 值 为 １，否则为 ０，得到形式背景（Ｏ，Ｐ，Ｉ），对象集 Ｏ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｎ ｝，属性 Ｐ ＝ ｛ｂ１ ，ｂ２ ，…，ｂｎ ｝。 特别地， 当图 Ｇ ＝ （Ｖ，Ｅ）为 Ｋｎ 图时，图 Ｇ ＝ （Ｖ，Ｅ）对应的形式 背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ）如表 ２ 所示。 表 ２ Ｋｎ 图的形式背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） Ｔａｂｌｅ ２ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） ｏｆ Ｋｎ ｄｉａｇｒａｍ Ｉ ｂ１ ｂ２ ｂ３ ｂｎ－１ … ｂｎ（ｎ－１） ２ Ｃ１ １ ０ １ ０ … ０ Ｃ２ ０ １ １ ０ … ０ Ｃ３ １ １ ０ １ … ０ ︙ ︙ ︙ ︙ ︙ ０ Ｃｎ（ｎ－１） ２ －（ｎ－１） ０ ０ … … … １ 定义 １０ 在 Ｋｎ 图的形式背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） 对应的概念格 Ｌ（Ｏ，Ｐ，Ｉ）中给出“层”的定义： 设 Ｌ（Ｏ，Ｐ，Ｉ）最大元为 Ａ 即第一层，对任意 Ｘ∈ Ｌ（Ｏ，Ｐ，Ｉ） ｛Ａ｝，设 Ａ 到 Ｘ 的距离为 ｎ。 也就是，当 区间［Ｘ，Ａ］⊆Ｌ（Ｏ，Ｐ，Ｉ）最长链的长度为 ｒ，（ ｒ ＝ １， ２，３，…，ｎ），则设 Ｘ 为第 ｍ 层，ｍ ＝ ｒ＋１，记第 ｍ 层为 ｍ ＝ Ｌ （ｍ） 。 设概念格 Ｌ （Ｏ，Ｐ，Ｉ） 的 Ｈａｓｓｅ 示图记为 Ｈ（Ｌ）。 由表 ２ 发现，当 ｎ ＝ ４ 时，根据 Ｌ （Ｏｋｎ ，Ｐｋｎ ， Ｉｋｎ ）＝ ｛（Ｐ′，Ｐ）｝ 得对应的概念为（ Ｃ３Ｃ２Ｃ１ ，｛ ｝） ∈ Ｌ （１） ；（Ｃ１Ｃ３ ，ｂ１ ），（Ｃ３Ｃ２ ，ｂ２ ），（Ｃ１Ｃ２ ，ｂ３ ）∈Ｌ （２） ；（Ｃ３ ， ｂ６ ｂ１ ｂ２ ）， （ Ｃ１ ， ｂ４ ｂ１ ｂ３ ）， （ Ｃ２ ， ｂ５ ｂ２ ｂ３ ） ∈ Ｌ （３） ； （｛ ｝， ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ）∈Ｌ （４） 。 引理 ３ １）根据完全图的定义和表 １ 知，当定 义 ７ 含圈基个数为 ｎ－１ 时，与定义 ８ 基顶点相连接 的每个基 ｂ１ ，ｂ２ ，…，ｂｎ－１对应的对象个数为 ｎ－２ 个。 ２）根据定义 ９ 含两个基的基最小圈最多有一 条重边。 证明 首先证明第 １）条。 在表 ２ 中，ｂ１ 对应着 的对象为 ｎ－２ 个，因为 ｂ１≠ｂ２ ，所以对应的对象就为 ｎ－２ 个，即 ｂ１ ′≠ｂ２ ′。 其次，证明第 ２） 条。 若两个基 最小圈含有 ２ 个相同的边，根据定义 ９ 可知：假设 Ｃ１≠Ｃ２ ，ｂ１∈Ｃ１ ，ｂ２∈Ｃ２ ，若（ｂ１∪ｂ２ ）∈（Ｃ１∩Ｃ２ ），则 推出 Ｃ１ ＝Ｃ２ ，与条件中两个基最小圈含有 ２ 个相同 的边矛盾，即 Ｃ１≠Ｃ２ 矛盾。 所以含两个基的基最小 圈最多有一条重边。 定理 １ Ｋｎ图对应的形式背景概念格有且仅有 ４ 层。 证明 根据定义 ４、定义 ５、定义 ６ 及引理 ３ 中 的第 １）条的概念。 第 １ 层：Ｏ＝ ｛Ｃ１ ，Ｃ２ ，…，ＣＣ２ ｎ－１ ｝对 应的属性集 Ｐ ＝ ｛｝可以表示为（Ｃ１Ｃ２…ＣＣ２ ｎ－１ ，｛ ｝）∈ Ｌ （１） 。 第 ２ 层： 每 个 基 对 应 ｎ － ２ 个 圈， 设 为 Ｃ１ ， Ｃ２ ，…，Ｃｎ－２ 。 证任意基 ｂｉ ∈Ｂ ＝ ｛ ｂ１ ， ｂ２ ，…， ｂｎ－１ ｝， （ｉ ＝ １，２，…，ｎ－１），设（Ｃ１ Ｃ２…Ｃｎ－２ ，ｂｉ ），其中 ｂｉ ′ ＝ Ｃ１Ｃ２…Ｃｎ－２ ，根据引理 ３ 中第 １） 条，⌀∩ ｂｉ ＝ ⌀， ⌀ ＝ ０， ｛ｂｉ｝ ＝ １ 且⌀⊄｛ｂｉ｝且不存在任意集合 Ａ 满足⌀⊆Ａ⊆｛ ｂｉ｝。 所以它们之间不会产生其他 的概念。 第 ３ 层：设（ Ｃ１ Ｃ２…Ｃｎ－２ ， ｂ１ ） 与（ Ｃ１Ｃ２ … Ｃｎ－３ ，ｂ２ ） ∈Ｌ （３） ，所以设（ Ｃ１ …Ｃｎ－３ ， （ｂ１ ｂ２ ）″）＝ （ Ｃ１ Ｃ２…Ｃｎ－２ ，ｂ１ ）∧（Ｃ１Ｃ２…Ｃｎ－３ ，ｂ２ ），由引理 ３ 中第 ２） 条知 Ｃ１ ＝Ｃ２ ＝ … ＝ Ｃｎ－３ ，取代表圈 Ｃ１ ，由基最小圈定 义当且仅当存在 ｂ３∈Ｃ１ ，则（Ｃ１ ，ｂ１ ｂ２ ｂ３ ）是概念，由 任意性知（Ｃｉ，Ｃｉ ′）均为概念，其中 Ｃｉ ′为 Ｃｉ 包含的 ３ 条边。 第４ 层：（ Ｃ１ ，ｂ１ ｂ２ ｂ３ ） 与（ Ｃ２ ， ｂ１ ｂ３ ｂ４ ） ∈Ｌ （４） ， （⌀，ｂ１ ）。 因为存在集合 Ｂ ＝ ｛ｂ１ ，ｂ２ ，ｂ３ ，…，ｂｎ（ｎ－１） ２ ｝， 满足⌀⊆Ｂ⊆｛Ｃｉ ｝，即第 ４ 层表示为（⌀，｛ ｂ１ ，ｂ２ ， ｂ３ ，…，ｂｎ（ｎ－１） ２ ｝）。 定理 ２ Ｋｎ 图模型建立的概念格 Ｌ（Ｋｎ ）的第 ２ 层和第 ３ 层的 Ｈａｓｓｅ 示图组成一个二部图。 证明 根据定义 ２（二部图）的定义，二部图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）由顶点集 Ｖ１ 和 Ｖ２ 及边集 Ｅ⊆Ｖ１ ×Ｖ２ 组 成，Ｖ１ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｓ｝，Ｖ２ ＝ ｛ ｙ１ ，ｙ２ ，…， ｙｔ｝，则二部 图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）的伴随矩阵为二元矩阵 Ａ（ａｉｊ），这 里 ａｉｊ ＝ １，当且仅当（ｘｉ，ｙｊ）∈Ｅ。 设 Ｖ１ 为对象集，Ｖ２ 为属性集，则二部图的伴随矩阵就是形式背景。 二 部图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）由两个非交顶点集 Ｖ１ ，Ｖ２ 组成， 且 Ｇ 的每条边的顶点分别在 Ｖ１ ，Ｖ２ 中。 设 Ｖ１ 是第 ２ ·３３６· 智 能 系 统 学 报 第 １２ 卷
第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·337. 层概念的集合，V2是第3层概念的集合，则在K。图 为K.时，顶点数为n,与基顶点相连的边为n-1,即 中概念之间满足定义6，(C1,b1)≤(C2,b2)一C, 第2层的概念为n-1个，根据属性b1,b2,…,bn-找 C(台b,二b,),根据子概念-父概念的关系建立连线 到所对应的基最小圈对象。 是一个二部图，如图1所示。 3)找第3层的概念，根据完全图K的特点，基 (C.C;b (C,C b,) (CCb) 最小圈的个数为(-1)-(n-1),即第3层有概念 2 n(n-1)-(n-1)个，由对象C,C2,…,Cg(-,找 ● (Cbbb) (Cbbb) (C,6bb.) 到所对应的属性。 4)第1层中的元（概念），与且仅与第2层的每 图1K,图的二部图 一个元分别连线，第4层的元与且仅与第3层的每 Fig.1 Bipartite graph of K,diagram 个元分别连线，第2层的元与第3层的元之间的 再把第1层和第4层概念(0，{})和({}，P)加 连线关系可以根据定理2进行。这样就可以得到所 进图1，根据定理1建立概念格得Hasse示图，如图 有应该存在的连线。即根据定义6和引理2的偏序 2所示。Hasse图是利用概念之间的泛化和特化进 关系(C1,b)≤(C2,b2)台C1SC2(台b,≤b,),满足 行绘制的，由于概念格的完备性，概念格确定了，其 概念格子概念-父概念的关系，把第1层的概念(0， Hasse图也唯一确定了。概念格最上层是全概念， {})与第2层的概念建立连线，第4层的概念({}， 最下层是空概念。Hasse图中的边分别连接在直接 P)与第3层概念建立连线加入到步骤2)和3)组成 父概念和直接子概念之间。 的二部图中。 (C.C.C) 2.4.3算法的复杂度 根据形式背景的特殊性，此处得到的概念格有 且仅有4层。 (C.C.b)O ○CC,b,) ○(CCb) 第1层的概念和第四层的概念分别是(O,{}) 和({}，P)。 第2层的概念与基顶点连接的边个数为n-1(n (C..bb.b) ○Cb,b,b) ○(Cb,b,b,) 表示顶点数)。 第3层的概念根据K,图所产生的基最小圈个 数N来决定，N=(n1)-(n-1)。根据第2层的概 (,bbbbbb) 2 图2K,图的概念格 念加入属性，即K。图的边，根据属性b1,b2,…,bn- Fig.2 Concept lattice of K diagram 找到所对应的基最小圈对象，知寻找的次数为W: 第3层加入基最小圈即概念的对象时，即K图里的 根据K,图的格结构，利用数学归纳法分别对 K图、K。图、K图进行建格，得出K图建立概念格 基最小圈，根据对象C,C2,…,C-),找到所 的一个算法过程。 对应的属性，可知寻找的次数为nN。即第2层和第 3层运算次数为nN+nN=2nN,复杂度为0(2nn2), 2.4.2算法过程 也就是0(n3)。 通过对特殊限制K图的规律发现，满足K图 与定义5和定义6找寻概念的方式（即参考文 二元标准矩阵特点的都可以建成一个Hasse示图。 献[22]中13页概念格的生成算法1)相比，本文提 对于具有这种特定形式背景的概念，用上面的建格 出的方法更有效。因为，如果存在1G1个对象，1M 方法进行建格，速度很快。下面给出对象是基最小 个属性，那么相应的概念格将可能包含2G或2m 圈，属性是边的形式背景的建格过程。 个概念，计算量太大。而本文构造的概念的算法方 输入形式背景(0，P,I)。 式，由于具有一定的规律性，大大减少了计算量。 输出集合C,(0,P,I)所有的概念。 1)C:={P',P}初始化属性集合B=☑。 3应用实例 2)找第2层的概念，根据规律知道，当完全图 超市里冷冻猪肉和冷鲜猪肉因储存时间的长
层概念的集合，Ｖ２ 是第 ３ 层概念的集合，则在 Ｋｎ 图 中概念之间满足定义 ６，（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔Ｃ１⊆ Ｃ２（⇔ｂ２⊆ｂ１ ），根据子概念－父概念的关系建立连线 是一个二部图，如图 １ 所示。 图 １ Ｋ４ 图的二部图 Ｆｉｇ．１ Ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｏｆ Ｋ４ ｄｉａｇｒａｍ 再把第 １ 层和第 ４ 层概念（Ｏ，｛｝）和（｛｝，Ｐ）加 进图 １，根据定理 １ 建立概念格得 Ｈａｓｓｅ 示图，如图 ２ 所示。 Ｈａｓｓｅ 图是利用概念之间的泛化和特化进 行绘制的，由于概念格的完备性，概念格确定了，其 Ｈａｓｓｅ 图也唯一确定了。 概念格最上层是全概念， 最下层是空概念。 Ｈａｓｓｅ 图中的边分别连接在直接 父概念和直接子概念之间。 图 ２ Ｋ４ 图的概念格 Ｆｉｇ．２ Ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｏｆ Ｋ４ ｄｉａｇｒａｍ 根据 Ｋ４ 图的格结构，利用数学归纳法分别对 Ｋ５ 图、Ｋ６ 图、Ｋｎ 图进行建格，得出 Ｋｎ 图建立概念格 的一个算法过程。 ２．４．２ 算法过程 通过对特殊限制 Ｋｎ 图的规律发现，满足 Ｋｎ 图 二元标准矩阵特点的都可以建成一个 Ｈａｓｓｅ 示图。 对于具有这种特定形式背景的概念，用上面的建格 方法进行建格，速度很快。 下面给出对象是基最小 圈，属性是边的形式背景的建格过程。 输入 形式背景（Ｏ，Ｐ，Ｉ）。 输出 集合 Ｃ，（Ｏ，Ｐ，Ｉ）所有的概念。 １）Ｃ：＝ ｛Ｐ′，Ｐ｝初始化属性集合 Ｂ ＝⌀。 ２）找第 ２ 层的概念，根据规律知道，当完全图 为 Ｋｎ 时，顶点数为 ｎ，与基顶点相连的边为 ｎ－１，即 第 ２ 层的概念为 ｎ－１ 个，根据属性 ｂ１ ，ｂ２ ，…，ｂｎ－１找 到所对应的基最小圈对象。 ３）找第 ３ 层的概念，根据完全图 Ｋｎ 的特点，基 最小圈的个数为 ｎ（ｎ－１） ２ －（ ｎ－１），即第 ３ 层有概念 ｎ（ｎ－１） ２ －（ｎ－１）个，由对象 Ｃ１ ，Ｃ２ ，…，Ｃｎ（ｎ－１） ２ －（ｎ－１） ，找 到所对应的属性。 ４）第 １ 层中的元（概念），与且仅与第 ２ 层的每 一个元分别连线，第 ４ 层的元与且仅与第 ３ 层的每 一个元分别连线，第 ２ 层的元与第 ３ 层的元之间的 连线关系可以根据定理 ２ 进行。 这样就可以得到所 有应该存在的连线。 即根据定义 ６ 和引理 ２ 的偏序 关系（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔Ｃ１⊆Ｃ２（⇔ｂ２⊆ｂ１ ），满足 概念格子概念－父概念的关系，把第 １ 层的概念（Ｏ， ｛｝）与第 ２ 层的概念建立连线，第 ４ 层的概念（｛ ｝， Ｐ）与第 ３ 层概念建立连线加入到步骤 ２）和 ３）组成 的二部图中。 ２．４．３ 算法的复杂度 根据形式背景的特殊性，此处得到的概念格有 且仅有 ４ 层。 第 １ 层的概念和第四层的概念分别是（Ｏ，｛ ｝） 和（｛｝，Ｐ）。 第 ２ 层的概念与基顶点连接的边个数为 ｎ－１（ｎ 表示顶点数）。 第 ３ 层的概念根据 Ｋｎ 图所产生的基最小圈个 数 Ｎ 来决定，Ｎ＝ ｎ（ｎ－１） ２ －（ｎ－１）。 根据第 ２ 层的概 念加入属性，即 Ｋｎ 图的边，根据属性 ｂ１ ，ｂ２ ，…，ｂｎ－１ 找到所对应的基最小圈对象，知寻找的次数为 ｎＮ； 第 ３ 层加入基最小圈即概念的对象时，即 Ｋｎ 图里的 基最小圈，根据对象 Ｃ１ ，Ｃ２ ，…，Ｃｎ（ｎ＋１） ２ －（ｂ－１） ，找到所 对应的属性，可知寻找的次数为 ｎＮ。 即第 ２ 层和第 ３ 层运算次数为 ｎＮ＋ｎＮ ＝ ２ｎＮ，复杂度为 Ｏ（２ｎｎ ２ ）， 也就是 Ｏ（ｎ ３ ）。 与定义 ５ 和定义 ６ 找寻概念的方式（即参考文 献［２２］中 １３ 页概念格的生成算法 １）相比，本文提 出的方法更有效。 因为，如果存在｜ Ｇ ｜个对象， ｜ Ｍ ｜ 个属性，那么相应的概念格将可能包含 ２ ｜ Ｇ｜ 或 ２ ｜ Ｍ｜ 个概念，计算量太大。 而本文构造的概念的算法方 式，由于具有一定的规律性，大大减少了计算量。 ３ 应用实例 超市里冷冻猪肉和冷鲜猪肉因储存时间的长 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３７·
·338 智能系统学报 第12卷 短不同，价格有很大差别。当决策者需要判断送货 b4,b5},C2={b2,b4,b6}和C3={b3,b4,b},C4={b1, 多少时，也许会出现这家超市里冷鲜猪肉已经卖 b3,bg},C5={b2,b3,bg},C6={b1,b2,bo}。为在最 完，而另一家超市里的冷鲜肉卖不出去，这时由于 短的距离内把货物送完，找出所有的送货路线，提 冷鲜猪肉放置太长时间，变成冷冻猪肉而导致价格 取里面的规则进行建格。 下降，造成亏损。针对这种情况，为了减少亏损，合 理决策冷鲜猪肉配送供给，变得十分重要。 因为供应超市里每个时间段内宰杀猪的数量 定，所以供货量一定：又因为超市分配每辆货车 行走的公里数一定，油费消耗一定。根据以上限制 条件，需要货车从供应超市出发到达其他任意两个 供给城市的连锁超市后，再返回原来的供应超市。 b 为让决策者更快地给出供应超市的货车供给方案， 图3K,图 应对其供货方案和距离进行概念格的可视化建格。 Fig.3 K diagram 货物（冷鲜肉）将从石家庄市超市出发分别运 根据定义3得K,图的二元拟阵的标准 往周边的县市超市。记石家庄市超市为心，正定县 矩阵： 超市记为2，鹿泉市超市记为，新乐市超市记为 Tb:b2 bs ba bsbs b3 bs bo bo 4,藁城市超市记为5。但是货物运输时由于宰杀 C,1001100000 猪数量的限制只能带够发往两个县市超市的货物 C20101010000 量，再回到出发地取货，为了选择出合适的运输方 A·=C4001100100 0 1010000100 案，对其进行建格。 011000001 0 根据货车配送路线，心，超市距2超市的距离为 C61 100000001 b,=15km,1超市距3超市的距离为b2=15km,1 根据概念格的定义4建立形式背景，如表3。 超市距)4超市的距离为b3=38km,1超市距y,超 表3K,图的形式背景 市的距离为b,=31km,2超市到，超市的距离为 Table 3 Formal context of K diagram b,=39km,3超市到v5超市的距离为b6=57km,4 方案b, b2 b3 ba bs b6 ba bs 超市到5超市的距离为b,=52km,2超市到4超 C110 010 0 00 00 市的距离为bg=33km,3超市到)4超市的距离为 C,01 010 1 0 0 00 b,=60km,2超市到，超市的距离为b1o=34km。 C30011001 0 00 根据任意两个超市之间是否有路相连接，得无向图 C41010000100 的关联矩阵（这里的距离是大约值，具体的取值可 C50 11 0 00 0 10 以根据用户的需求来定)： C61 1 0 0 00 0 0 01 「bb2bb4b5b6b,bgbg 利用表3中K,图的形式背景，根据本文所给出 2100010010 1 算法过程，进行概念格Hasse图的建立。 A=3010001001 1 1)C:={P',P}初始化属性集合B=☑。 D40010001110 2)找第2层的概念，根据属性b1、b2、b3、b4、b5、 50001111000 b。找到所对应的基最小圈对象C,C,C6、C,C,C6、 根据出行人员的实际要求，从城市：，出发后要 C3C4C5、CC2C,得到概念(C,CC6,b1)、(C2CsC6, 经过两个城市再返回原城市，符合基最小圈定义。 b2)、(C3C4C5,b3)、(C1C,C3,b4)。 建立数学模型，根据无向图的关联矩阵A得图3所 3)找第3层的概念，根据完全图K,的特点，由 示K图模型。以顶点，为出发地，根据运送货物 对象C1、C2、C3、C4、C5、C6找到所对应的属性 的实际情况，从顶点，出发运送到其他两个顶点经 b1bubs、b2bab6、b3bub,、b1b3bg、b2b3bg、bib2bo得到概念 过的距离，得送货所有可能的方案分别是C,={b, (C1,b1bub5)、(C2,b2bab6)、(C3,bb4b,)、（C4
短不同，价格有很大差别。 当决策者需要判断送货 多少时，也许会出现这家超市里冷鲜猪肉已经卖 完，而另一家超市里的冷鲜肉卖不出去，这时由于 冷鲜猪肉放置太长时间，变成冷冻猪肉而导致价格 下降，造成亏损。 针对这种情况，为了减少亏损，合 理决策冷鲜猪肉配送供给，变得十分重要。 因为供应超市里每个时间段内宰杀猪的数量 一定，所以供货量一定；又因为超市分配每辆货车 行走的公里数一定，油费消耗一定。 根据以上限制 条件，需要货车从供应超市出发到达其他任意两个 供给城市的连锁超市后，再返回原来的供应超市。 为让决策者更快地给出供应超市的货车供给方案， 应对其供货方案和距离进行概念格的可视化建格。 货物（冷鲜肉） 将从石家庄市超市出发分别运 往周边的县市超市。 记石家庄市超市为 ｖ１ ，正定县 超市记为 ｖ２ ，鹿泉市超市记为 ｖ３ ，新乐市超市记为 ｖ４ ，藁城市超市记为 ｖ５ 。 但是货物运输时由于宰杀 猪数量的限制只能带够发往两个县市超市的货物 量，再回到出发地取货，为了选择出合适的运输方 案，对其进行建格。 根据货车配送路线，ｖ１ 超市距 ｖ２ 超市的距离为 ｂ１ ＝ １５ ｋｍ，ｖ１ 超市距 ｖ３ 超市的距离为 ｂ２ ＝ １５ ｋｍ，ｖ１ 超市距 ｖ４ 超市的距离为 ｂ３ ＝ ３８ ｋｍ，ｖ１ 超市距 ｖ５ 超 市的距离为 ｂ４ ＝ ３１ ｋｍ，ｖ２ 超市到 ｖ５ 超市的距离为 ｂ５ ＝ ３９ ｋｍ，ｖ３ 超市到 ｖ５ 超市的距离为 ｂ６ ＝ ５７ ｋｍ，ｖ４ 超市到 ｖ５ 超市的距离为 ｂ７ ＝ ５２ ｋｍ，ｖ２ 超市到 ｖ４ 超 市的距离为 ｂ８ ＝ ３３ ｋｍ，ｖ３ 超市到 ｖ４ 超市的距离为 ｂ９ ＝ ６０ ｋｍ，ｖ２ 超市到 ｖ３ 超市的距离为 ｂ１０ ＝ ３４ ｋｍ。 根据任意两个超市之间是否有路相连接，得无向图 的关联矩阵（这里的距离是大约值，具体的取值可 以根据用户的需求来定）： Ａ ＝ ｖ２ ｖ３ ｖ４ ｖ５ ｂ１ ｂ２ ｂ３ ｂ４ ｂ５ ｂ６ ｂ７ ｂ８ ｂ９ ｂ１０ １ ０ ０ ０ １ ０ ０ １ ０ １ ０ １ ０ ０ ０ １ ０ ０ １ １ ０ ０ １ ０ ０ ０ １ １ １ ０ ０ ０ ０ １ １ １ １ ０ ０ ０ é ë ê ê ê ê ê ê ù û ú ú ú ú ú ú 根据出行人员的实际要求，从城市 ｖ１ 出发后要 经过两个城市再返回原城市，符合基最小圈定义。 建立数学模型，根据无向图的关联矩阵 Ａ 得图 ３ 所 示 Ｋ５ 图模型。 以顶点 ｖ１ 为出发地，根据运送货物 的实际情况，从顶点 ｖ１ 出发运送到其他两个顶点经 过的距离，得送货所有可能的方案分别是 Ｃ１ ＝ ｛ ｂ１ ， ｂ４ ，ｂ５ ｝，Ｃ２ ＝ ｛ｂ２ ，ｂ４ ，ｂ６ ｝和 Ｃ３ ＝ ｛ｂ３ ，ｂ４ ，ｂ７ ｝，Ｃ４ ＝ ｛ｂ１ ， ｂ３ ，ｂ８ ｝，Ｃ５ ＝ ｛ ｂ２ ，ｂ３ ，ｂ９ ｝，Ｃ６ ＝ ｛ ｂ１ ，ｂ２ ，ｂ１０ ｝。 为在最 短的距离内把货物送完，找出所有的送货路线，提 取里面的规则进行建格。 图 ３ Ｋ５ 图 Ｆｉｇ．３ Ｋ５ ｄｉａｇｒａｍ 根据定义 ３ 得 Ｋ５ 图的二元拟阵的标准 矩阵： Ａ ∗ ＝ Ｃ１ Ｃ２ Ｃ３ Ｃ４ Ｃ５ Ｃ６ ｂ１ ｂ２ ｂ３ ｂ４ ｂ５ ｂ６ ｂ７ ｂ８ ｂ９ ｂ１０ １ ０ ０ １ １ ０ ０ ０ ０ ０ ０ １ ０ １ ０ １ ０ ０ ０ ０ ０ ０ １ １ ０ ０ １ ０ ０ ０ １ ０ １ ０ ０ ０ ０ １ ０ ０ ０ １ １ ０ ０ ０ ０ ０ １ ０ １ １ ０ ０ ０ ０ ０ ０ ０ １ é ë ê ê ê ê ê ê ê ê ê ù û ú ú ú ú ú ú ú ú ú 根据概念格的定义 ４ 建立形式背景，如表 ３。 表 ３ Ｋ５ 图的形式背景 Ｔａｂｌｅ ３ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ ｏｆ Ｋ５ ｄｉａｇｒａｍ 方案 ｂ１ ｂ２ ｂ３ ｂ４ ｂ５ ｂ６ ｂ７ ｂ８ ｂ９ ｂ１０ Ｃ１ １ ０ ０ １ ０ ０ ０ ０ ０ ０ Ｃ２ ０ １ ０ １ ０ １ ０ ０ ０ ０ Ｃ３ ０ ０ １ １ ０ ０ １ ０ ０ ０ Ｃ４ １ ０ １ ０ ０ ０ ０ １ ０ ０ Ｃ５ ０ １ １ ０ ０ ０ ０ ０ １ ０ Ｃ６ １ １ ０ ０ ０ ０ ０ ０ ０ １ 利用表 ３ 中 Ｋ５ 图的形式背景，根据本文所给出 算法过程，进行概念格 Ｈａｓｓｅ 图的建立。 １）Ｃ：＝ ｛Ｐ′，Ｐ｝初始化属性集合 Ｂ ＝⌀。 ２）找第 ２ 层的概念，根据属性 ｂ１ 、ｂ２ 、ｂ３ 、ｂ４ 、ｂ５ 、 ｂ６ 找到所对应的基最小圈对象 Ｃ１Ｃ４Ｃ６ 、 Ｃ２Ｃ５Ｃ６ 、 Ｃ３Ｃ４Ｃ５ 、Ｃ１Ｃ２Ｃ３ 得到概念（ Ｃ１Ｃ４Ｃ６ ， ｂ１ ）、 （ Ｃ２Ｃ５Ｃ６ ， ｂ２ ）、（Ｃ３Ｃ４Ｃ５ ，ｂ３ ）、（Ｃ１Ｃ２Ｃ３ ，ｂ４ ）。 ３）找第 ３ 层的概念，根据完全图 Ｋｎ 的特点，由 对象 Ｃ１ 、 Ｃ２ 、 Ｃ３ 、 Ｃ４ 、 Ｃ５ 、 Ｃ６ 找 到 所 对 应 的 属 性 ｂ１ ｂ４ ｂ５ 、ｂ２ ｂ４ ｂ６ 、ｂ３ ｂ４ ｂ７ 、ｂ１ ｂ３ ｂ８ 、ｂ２ ｂ３ ｂ９ 、ｂ１ ｂ２ ｂ１０得到概念 （Ｃ１ ， ｂ１ ｂ４ ｂ５ ）、 （ Ｃ２ ， ｂ２ ｂ４ ｂ６ ）、 （ Ｃ３ ， ｂ３ ｂ４ ｂ７ ）、 （ Ｃ４ ， ·３３８· 智 能 系 统 学 报 第 １２ 卷
第3期 毛华，等：利用二元拟阵K。图的一种建格方法 ·339. b1b3bg)、(C5,b2b3bg)、(C6,b1b2b1o)。 中的一些属性条件的限制，在K。图模型中，根据三 4)把第1层和第4层概念(0，{})和({}，P),根 角形圈的一种特殊性，寻找规律，结果发现，对K图 据定义6和引理2的偏序关系(C,b,)≤(C2,b2)台 拟阵的标准矩阵的形式背景产生4层。根据此规律 C,二C,(台b,二b,),对满足概念格子概念-父概念的 进行建格，提出利用二元拟阵的K图的概念格的建 关系)，把第1层的概念(0，{})与第2层的概念 格方法。相比最基本的建格方法，此方法的计算量 建立连线，第4层的概念({}，P)与第3层概念建立 要少很多。通过实例发现，针对这种特殊的形式背 连线加入到步骤2)和3)组成的二部图中，得到概 景，出行者在提取有用的方案时，会更加快速、方 念格的Hasse示图，如图4。 便。由于研究背景和素材来源于实践，这类事件很 (C.C.C.C.C.C) 多，因此提出的方法具有很好的推广意义和应用前 景。在接下来的研究中，将会在K,图中加人权值， (CC C2.b.) 进行距离和时间等多种属性的研究。 (CC Cb)O D(C.C.C.b) (Csbbb) 参考文献： (C,b,b,b○ OCbbb) (C:.bbb)(C:.b.b b)(C.Bb,b) [1]左锋.经济学视野中大城市经济圈的形成与发展一论中 国三大城市经济圈的现状及其发展[].华东师范大学 学报：哲学社会科学版，2002,34(5)：89-95 ZUO Feng.The formation and development of a metropolitan (13.b b bbb bbbbb) economic circle in the perspec-tive of economics [J]. 图4K,图的概念格 Journal of east cluna normal university:philosophy and Fig.4 Concept lattice of Ks diagram social sciences,2002,34(5):89-95. 从图4中可以看出，满足b,这段距离油耗的货 [2]胡一竑.基于复杂网络的交通网络复杂性研究[D].上 车有且仅有C1、C4、C6方案，满足b2这段距离油耗 海：复旦大学，2008：1-121. 的货车有且仅有C2、C5、C6方案，满足b这段距离 HU Yihong.Analysis of complex transportation networks 油耗的货车有且仅有C3、C4、C,方案，满足b。这段 [D].Shanghai:Fudan University,2008:1-121. 距离油耗的货车有且仅有C,、C2、C,方案，还可以快 [3]刘佳.复杂网络中最短路径问题的优化算法研究[D] 太原：太原科技大学，2007：1-30. 速地计算出每个方案需要走的距离里程。若采用 LIU Jia.Research on the algorithm for shortest path problem 方案C,需走的距离里程为b,+b,+b,=85km;若采 in complicated network[D].Taiyuan:Taiyuan University of 用方案C2,需走的距离里程为b,+b,+b。=103km:若 Science and Technology,2007:1-30. 采用方案C3,需走的距离里程为b,+b。+b,=140km [4]严寒冰，刘迎春.基于GS的城市道路网最短路径算法 若采用方案C4,需走的距离里程为b,+b+bg= 探讨[J].计算机学报，2000,23(2)：210-215. 86km;若采用方案C5,需走的距离里程为b2+b3+ YAN Hanbing,LIU Yingchun.A new algorithm for finding b,=113km;采用方案C6,需要走的距离里程为b,+ shortcut in a city's road net based on GIS technology[J] b2+b1o=64km。从中比较可知，若运送货物途经距 Chinese journal of computers,2000,23(2):210-215. 离最短，可以选择方案C6。 [5]谢政，李建平.网络算法与复杂性理论[.北京：国防 从图4中可快速地筛选出运输最短路径的运输 科技大学出版社，1995：120-140. 方案和最长路径的运输方案，方便出行者对出行方 [6]LAM W H K,LI Zhichun,HUANG Haijun,et al.Modeling 案的选择。在其他复杂网络中，两个顶点之间会出 time-dependent travel choice problems in road networks with 现两条边，比如重边的情况，在寻找哪种方案最优 multiple user classes and multiple parking facilities[J]. 时，可能出现多种方案，而本文开始时就已经删除 Transportation research part B:methodological,2006,40 (5):368-395. 了那些对选择方案无用的边，因此从概念格的 [7]GAO Song,Chabini I.Optimal routing policy problems in Hasse图中很容易看出哪个方案最优，不需要出行 stochastic time-dependent networks J].Transportation 者进行2次或更多次的重新比较。 research parB:methodological,2006,40(2):93-122. 4 结束语 [8]于德新，杨薇，杨兆升.重大灾害条件下基于GS的最 短路径改进算法[J].交通运输工程学报，2011,11(4)： 根据京津冀紧密对接的一体化交通网络。基 123-126. 于出行者对于交通网络路径的选择，根据实际生活 YU Dexin,YANG Wei,YANG Zhaosheng.Shortest path
ｂ１ ｂ３ ｂ８ ）、（Ｃ５ ，ｂ２ ｂ３ ｂ９ ）、（Ｃ６ ，ｂ１ ｂ２ ｂ１０ ）。 ４）把第 １ 层和第 ４ 层概念（Ｏ，｛｝）和（｛｝，Ｐ），根 据定义 ６ 和引理 ２ 的偏序关系（Ｃ１ ，ｂ１ ）≤（Ｃ２ ，ｂ２ ）⇔ Ｃ１⊆Ｃ２（⇔ｂ２⊆ｂ１ ），对满足概念格子概念－父概念的 关系［２３］ ，把第 １ 层的概念（Ｏ，｛ ｝）与第 ２ 层的概念 建立连线，第 ４ 层的概念（｛｝，Ｐ）与第 ３ 层概念建立 连线加入到步骤 ２）和 ３）组成的二部图中，得到概 念格的 Ｈａｓｓｅ 示图，如图 ４。 图 ４ Ｋ５ 图的概念格 Ｆｉｇ．４ Ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｏｆ Ｋ５ ｄｉａｇｒａｍ 从图 ４ 中可以看出，满足 ｂ１ 这段距离油耗的货 车有且仅有 Ｃ１ 、Ｃ４ 、Ｃ６ 方案，满足 ｂ２ 这段距离油耗 的货车有且仅有 Ｃ２ 、Ｃ５ 、Ｃ６ 方案，满足 ｂ３ 这段距离 油耗的货车有且仅有 Ｃ３ 、Ｃ４ 、Ｃ５ 方案，满足 ｂ４ 这段 距离油耗的货车有且仅有 Ｃ１ 、Ｃ２ 、Ｃ３ 方案，还可以快 速地计算出每个方案需要走的距离里程。 若采用 方案 Ｃ１ ，需走的距离里程为 ｂ１ ＋ｂ４ ＋ｂ５ ＝ ８５ ｋｍ；若采 用方案 Ｃ２ ，需走的距离里程为 ｂ２ ＋ｂ４ ＋ｂ６ ＝ １０３ ｋｍ；若 采用方案 Ｃ３ ，需走的距离里程为 ｂ４ ＋ｂ６ ＋ｂ７ ＝ １４０ ｋｍ； 若采用方案 Ｃ４ ， 需走的距离里程为 ｂ１ ＋ ｂ３ ＋ ｂ８ ＝ ８６ ｋｍ；若采用方案 Ｃ５ ，需走的距离里程为 ｂ２ ＋ｂ３ ＋ ｂ９ ＝ １１３ ｋｍ；采用方案 Ｃ６ ，需要走的距离里程为 ｂ１ ＋ ｂ２ ＋ｂ１０ ＝ ６４ ｋｍ。 从中比较可知，若运送货物途经距 离最短，可以选择方案 Ｃ６ 。 从图 ４ 中可快速地筛选出运输最短路径的运输 方案和最长路径的运输方案，方便出行者对出行方 案的选择。 在其他复杂网络中，两个顶点之间会出 现两条边，比如重边的情况，在寻找哪种方案最优 时，可能出现多种方案，而本文开始时就已经删除 了那些 对 选 择 方 案 无 用 的 边， 因 此 从 概 念 格 的 Ｈａｓｓｅ 图中很容易看出哪个方案最优，不需要出行 者进行 ２ 次或更多次的重新比较。 ４ 结束语 根据京津冀紧密对接的一体化交通网络。 基 于出行者对于交通网络路径的选择，根据实际生活 中的一些属性条件的限制，在 Ｋｎ 图模型中，根据三 角形圈的一种特殊性，寻找规律，结果发现，对 Ｋｎ 图 拟阵的标准矩阵的形式背景产生 ４ 层。 根据此规律 进行建格，提出利用二元拟阵的 Ｋｎ 图的概念格的建 格方法。 相比最基本的建格方法，此方法的计算量 要少很多。 通过实例发现，针对这种特殊的形式背 景，出行者在提取有用的方案时，会更加快速、方 便。 由于研究背景和素材来源于实践，这类事件很 多，因此提出的方法具有很好的推广意义和应用前 景。 在接下来的研究中，将会在 Ｋｎ 图中加入权值， 进行距离和时间等多种属性的研究。 参考文献： ［１］左锋． 经济学视野中大城市经济圈的形成与发展—论中 国三大城市经济圈的现状及其发展［ Ｊ］． 华东师范大学 学报：哲学社会科学版， ２００２， ３４（５）： ８９－９５． ＺＵＯ Ｆｅｎｇ． Ｔｈｅ ｆｏｒｍａｔｉｏｎ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ａ ｍｅｔｒｏｐｏｌｉｔａｎ ｅｃｏｎｏｍｉｃ ｃｉｒｃｌｅ ｉｎ ｔｈｅ ｐｅｒｓｐｅｃ⁃ｔｉｖｅ ｏｆ ｅｃｏｎｏｍｉｃｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｅａｓｔ ｃｌｕｎａ ｎｏｒｍａｌ ｕｎｉｖｅｒｓｉｔｙ： ｐｈｉｌｏｓｏｐｈｙ ａｎｄ ｓｏｃｉａｌ ｓｃｉｅｎｃｅｓ， ２００２， ３４（５）： ８９－９５． ［２］胡一竑． 基于复杂网络的交通网络复杂性研究［Ｄ］． 上 海：复旦大学， ２００８： １－１２１． ＨＵ Ｙｉｈｏｎｇ． Ａｎａｌｙｓｉｓ ｏｆ ｃｏｍｐｌｅｘ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｎｅｔｗｏｒｋｓ ［Ｄ］．Ｓｈａｎｇｈａｉ： Ｆｕｄａｎ Ｕｎｉｖｅｒｓｉｔｙ， ２００８： １－１２１． ［３］刘佳． 复杂网络中最短路径问题的优化算法研究［Ｄ］． 太原： 太原科技大学， ２００７： １－３０． ＬＩＵ Ｊｉａ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｓｈｏｒｔｅｓｔ ｐａｔｈ ｐｒｏｂｌｅｍ ｉｎ ｃｏｍｐｌｉｃａｔｅｄ ｎｅｔｗｏｒｋ［Ｄ］． Ｔａｉｙｕａｎ： Ｔａｉｙｕａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００７： １－３０． ［４］严寒冰， 刘迎春． 基于 ＧＩＳ 的城市道路网最短路径算法 探讨［Ｊ］． 计算机学报， ２０００， ２３（２）： ２１０－２１５． ＹＡＮ Ｈａｎｂｉｎｇ， ＬＩＵ Ｙｉｎｇｃｈｕｎ． Ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｆｉｎｄｉｎｇ ｓｈｏｒｔｃｕｔ ｉｎ ａ ｃｉｔｙ’ ｓ ｒｏａｄ ｎｅｔ ｂａｓｅｄ ｏｎ ＧＩＳ ｔｅｃｈｎｏｌｏｇｙ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２０００， ２３（２）： ２１０－２１５． ［５］谢政， 李建平． 网络算法与复杂性理论［Ｍ］． 北京：国防 科技大学出版社， １９９５： １２０－１４０． ［６］ＬＡＭ Ｗ Ｈ Ｋ， ＬＩ Ｚｈｉｃｈｕｎ， ＨＵＡＮＧ Ｈａｉｊｕｎ， ｅｔ ａｌ． Ｍｏｄｅｌｉｎｇ ｔｉｍｅ⁃ｄｅｐｅｎｄｅｎｔ ｔｒａｖｅｌ ｃｈｏｉｃｅ ｐｒｏｂｌｅｍｓ ｉｎ ｒｏａｄ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｕｓｅｒ ｃｌａｓｓｅｓ ａｎｄ ｍｕｌｔｉｐｌｅ ｐａｒｋｉｎｇ ｆａｃｉｌｉｔｉｅｓ ［ Ｊ ］． Ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｒｅｓｅａｒｃｈ ｐａｒｔ Ｂ： ｍｅｔｈｏｄｏｌｏｇｉｃａｌ， ２００６， ４０ （５）： ３６８－３９５． ［７］ＧＡＯ Ｓｏｎｇ， Ｃｈａｂｉｎｉ Ｉ． Ｏｐｔｉｍａｌ ｒｏｕｔｉｎｇ ｐｏｌｉｃｙ ｐｒｏｂｌｅｍｓ ｉｎ ｓｔｏｃｈａｓｔｉｃ ｔｉｍｅ⁃ｄｅｐｅｎｄｅｎｔ ｎｅｔｗｏｒｋｓ ［ Ｊ ］． Ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｒｅｓｅａｒｃｈ ｐａｒＢ： ｍｅｔｈｏｄｏｌｏｇｉｃａｌ， ２００６， ４０（２）： ９３－１２２． ［８］于德新， 杨薇， 杨兆升． 重大灾害条件下基于 ＧＩＳ 的最 短路径改进算法［Ｊ］． 交通运输工程学报， ２０１１， １１（４）： １２３－１２６． ＹＵ Ｄｅｘｉｎ， ＹＡＮＧ Ｗｅｉ， ＹＡＮＧ Ｚｈａｏｓｈｅｎｇ． Ｓｈｏｒｔｅｓｔ ｐａｔｈ 第 ３ 期 毛华，等：利用二元拟阵 Ｋｎ 图的一种建格方法 ·３３９·
·340 智能系统学报 第12卷 improved algorithm based on GIS under large-scale disaster LI Lifeng,LIU Sanyang,LUO Qingjun.Representing [J].Journal of traffic and transportation engineering,2011, chordal bipartite graph using concept lattice theory [J]. 11(4):123-126. Chinese journal of electronics,2013,41(7):1385-1388. [9]陈京荣.交通网络路径选择及应用研究[D].兰州：兰州 [19]李立峰.链图的概念格表示[].计算机科学，2014,41 交通大学，2009：1-43. (2):264-266. CHEN Jingrong.Research on route choice and its LI Lifeng.Chain graph and their concept lattice application in traffic networks D].Lanzhou:Lanzhou representation [J].Computer science,2014,41 (2): Jiaotong University,2009:1-43. 264-266. [10]GANTER B,Wille R.Formal concept analysis:mathematical [20]MAO Hua.A graph-theoretic method to representing a foundations[M].New York:Springer,1999. concept lattice[J].Applied mathematics and information [11]王树禾.图论[M].北京：科学出版社，2009. sciences,2014,8(2):553-561 12 BONDY JA.Graph theory M ]Berlin:Springer [21]MAO Hua.Characterizing trees in property-oriented concept Press,2008. lattices[J].Armenian joumal of mathematics,2016,8(2): [13]刘桂珍，陈庆华.拟阵[M].长沙：国防科技大学出版 86-95. 社，1994. [22]王海英，黄强，李传涛，等.图论算法及其MATLAB实 「141吉庆兵.二元拟阵码及其对偶码「J].重庆师范学院学 现[M1.北京：北京航空航天大学出版社，2010：1-38. 报：自然科学版，2001,18(4)：48-50. [23]李娜.形式概念分析中若干算法的改进与实现[D].北 JI Qingbing.Binary matroid codes and their dual codes 京：中央民族大学，2007：1-15. [J].Journal of Chongqing normal university:natural LI Na.Improvement and implementation of several science edition,2001,18(4):48-50. [15]马对霞，林姿琼，祝峰.拟阵在网络安全中应用J].小 algorithms about formal concept analysis [D].Beijing: 型微型计算机系统，2015,36(8)：1858-1860. Minzu University of China,2007:1-15. MA Duixia,LIN Ziqiong,ZHU Feng.Application of 作者简介： matroids on network security [J].Journal of Chinese 毛华，女，1963年生，教授.博士后. computer systems,2015,36(8):1858-1860. 美国《数学评论》评论员，河北省工业与 [16]毛华.拟阵与概念格的关系[J].数学进展，2006,35 应用数学学会理事，主要研究方向为计 (3):361-365. 算机数学及其应用、拟阵理论、离散数 MAO Hua.The relation between matroid and concept Lattice 学。已发表学术论文90余篇，其中被 [J].Advances in mathematics,2006,35(3):361-365. SCI,EI检索20余篇。 [17]毛华，李斌.等价关系约束属性的形式概念分析[J]. 计算机工程与应用，2010,46(36)：158-160. 史明，女，1989年生，硕士研究生， Mao Hua,LI Bin.Formal concept analysis of attributes by 主要研究方向为网络优化、图论、拟阵 equivalent relation[J].Computer engineering applications, 理论、概念格。已发表学术论文2篇。 2010,46(36)：158-160. [18]李立峰，刘三阳，罗清君.弦二部图的概念格表示[J] 电子学报.2013,41(7)：1385-1388
ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＧＩＳ ｕｎｄｅｒ ｌａｒｇｅ⁃ｓｃａｌｅ ｄｉｓａｓｔｅｒ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｒａｆｆｉｃ ａｎｄ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１１， １１（４）： １２３－１２６． ［９］陈京荣． 交通网络路径选择及应用研究［Ｄ］． 兰州： 兰州 交通大学， ２００９： １－４３． ＣＨＥＮ Ｊｉｎｇｒｏｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｒｏｕｔｅ ｃｈｏｉｃｅ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｔｒａｆｆｉｃ ｎｅｔｗｏｒｋｓ ［ Ｄ ］． Ｌａｎｚｈｏｕ： Ｌａｎｚｈｏｕ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２００９： １－４３． ［１０］ＧＡＮＴＥＲ Ｂ， Ｗｉｌｌｅ Ｒ． Ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ： ｍａｔｈｅｍａｔｉｃａｌ ｆｏｕｎｄａｔｉｏｎｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｓｐｒｉｎｇｅｒ， １９９９． ［１１］王树禾． 图论［Ｍ］． 北京： 科学出版社， ２００９． ［ １２ ］ ＢＯＮＤＹ ＪＡ． Ｇｒａｐｈ ｔｈｅｏｒｙ ［ Ｍ ］． Ｂｅｒｌｉｎ： Ｓｐｒｉｎｇｅｒ Ｐｒｅｓｓ， ２００８． ［１３］刘桂珍，陈庆华． 拟阵［Ｍ］． 长沙： 国防科技大学出版 社， １９９４． ［１４］吉庆兵． 二元拟阵码及其对偶码［ Ｊ］． 重庆师范学院学 报：自然科学版， ２００１， １８（４）： ４８－５０． ＪＩ Ｑｉｎｇｂｉｎｇ． Ｂｉｎａｒｙ ｍａｔｒｏｉｄ ｃｏｄｅｓ ａｎｄ ｔｈｅｉｒ ｄｕａｌ ｃｏｄｅｓ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｏｎｇｑｉｎｇ ｎｏｒｍａｌ ｕｎｉｖｅｒｓｉｔｙ： ｎａｔｕｒａｌ ｓｃｉｅｎｃｅ ｅｄｉｔｉｏｎ， ２００１， １８（４）： ４８－５０． ［１５］马对霞， 林姿琼， 祝峰． 拟阵在网络安全中应用［Ｊ］． 小 型微型计算机系统， ２０１５， ３６（８）： １８５８－１８６０． ＭＡ Ｄｕｉｘｉａ， ＬＩＮ Ｚｉｑｉｏｎｇ， ＺＨＵ Ｆｅｎｇ． Ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｍａｔｒｏｉｄｓ ｏｎ ｎｅｔｗｏｒｋ ｓｅｃｕｒｉｔｙ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎｅｓｅ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０１５， ３６（８）： １８５８－１８６０． ［１６］毛华． 拟阵与概念格的关系［ Ｊ］． 数学进展， ２００６， ３５ （３）： ３６１－３６５． ＭＡＯ Ｈｕａ． Ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｍａｔｒｏｉｄ ａｎｄ ｃｏｎｃｅｐｔ Ｌａｔｔｉｃｅ ［Ｊ］． Ａｄｖａｎｃｅｓ ｉｎ ｍａｔｈｅｍａｔｉｃｓ， ２００６， ３５（３）： ３６１－３６５． ［１７］毛华， 李斌． 等价关系约束属性的形式概念分析［ Ｊ］． 计算机工程与应用， ２０１０， ４６ （３６）： １５８－１６０． Ｍａｏ Ｈｕａ， ＬＩ Ｂｉｎ． Ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ｏｆ ａｔｔｒｉｂｕｔｅｓ ｂｙ ｅｑｕｉｖａｌｅｎｔ ｒｅｌａｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０， ４６（３６）： １５８－１６０． ［１８］李立峰， 刘三阳， 罗清君． 弦二部图的概念格表示［ Ｊ］． 电子学报， ２０１３， ４１（７）： １３８５－１３８８． ＬＩ Ｌｉｆｅｎｇ， ＬＩＵ Ｓａｎｙａｎｇ， ＬＵＯ Ｑｉｎｇｊｕｎ． Ｒｅｐｒｅｓｅｎｔｉｎｇ ｃｈｏｒｄａｌ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｕｓｉｎｇ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｔｈｅｏｒｙ ［ Ｊ］． Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ， ２０１３， ４１（７）： １３８５－１３８８． ［１９］李立峰． 链图的概念格表示［Ｊ］． 计算机科学， ２０１４， ４１ （２）： ２６４－２６６． ＬＩ Ｌｉｆｅｎｇ． Ｃｈａｉｎ ｇｒａｐｈ ａｎｄ ｔｈｅｉｒ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ［ Ｊ ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１４， ４１ （ ２ ）： ２６４－２６６． ［２０］ ＭＡＯ Ｈｕａ． Ａ ｇｒａｐｈ⁃ｔｈｅｏｒｅｔｉｃ ｍｅｔｈｏｄ ｔｏ ｒｅｐｒｅｓｅｎｔｉｎｇ ａ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅ［ Ｊ］． Ａｐｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１４， ８（２）： ５５３－５６１． ［２１］ ＭＡＯ Ｈｕａ． Ｃｈａｒａｃｔｅｒｉｚｉｎｇ ｔｒｅｅｓ ｉｎ ｐｒｏｐｅｒｔｙ⁃ｏｒｉｅｎｔｅｄ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｓ［Ｊ］． Ａｒｍｅｎｉａｎ ｊｏｕｒｎａｌ ｏｆ ｍａｔｈｅｍａｔｉｃｓ， ２０１６， ８（２）： ８６－９５． ［２２］王海英， 黄强， 李传涛， 等． 图论算法及其 ＭＡＴＬＡＢ 实 现［Ｍ］． 北京： 北京航空航天大学出版社， ２０１０： １－３８． ［２３］李娜． 形式概念分析中若干算法的改进与实现［Ｄ］． 北 京：中央民族大学， ２００７： １－１５． ＬＩ Ｎａ． Ｉｍｐｒｏｖｅｍｅｎｔ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｓｅｖｅｒａｌ ａｌｇｏｒｉｔｈｍｓ ａｂｏｕｔ ｆｏｒｍａｌ ｃｏｎｃｅｐｔ ａｎａｌｙｓｉｓ ［ Ｄ］． Ｂｅｉｊｉｎｇ： Ｍｉｎｚｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎａ， ２００７： １－１５． 作者简介： 毛华，女，１９６３ 年生，教授，博士后， 美国《数学评论》评论员，河北省工业与 应用数学学会理事，主要研究方向为计 算机数学及其应用、拟阵理论、离散数 学。 已发表学术论文 ９０ 余篇，其中被 ＳＣＩ、ＥＩ 检索 ２０ 余篇。 史明，女，１９８９ 年生，硕士研究生， 主要研究方向为网络优化、图论、拟阵 理论、概念格。 已发表学术论文 ２ 篇。 ·３４０· 智 能 系 统 学 报 第 １２ 卷