·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小圈个数为边数 ｎ（ｎ－１） ２ 减去定义 ７ 含圈基数 ｎ－１， 以此类推，得到表 １。 表 １ 顶点数与基最小圈的规律 Ｔａｂｌｅ １ Ｖｅｒｔｅｘ ｎｕｍｂｅｒ ａｎｄ ｔｈｅ ｂａｓｉｓ ｏｆ ｔｈｅ ｓｍａｌｌｅｓｔ ｃｉｒｃｌｅ ｏｆ ｔｈｅ ｌａｗ 顶点 边数 含圈基 基最小圈 ３ ３ ２ １ ４ ６ ３ ３ ５ １０ ４ ６ ６ １５ ５ １０ ７ ２１ ６ １５ ︙ ︙ ︙ ︙ ｎ … ｎ－１ ｎ（ｎ－１） ２ －（ｎ－１） 将图 Ｇ ＝ （Ｖ，Ｅ）对应的拟阵 Ｍ 中定义 ９ 基最小 圈集 Ｏ 视为形式背景中的对象集，将图 Ｇ 的边集 Ｅ 视为属性集 Ｐ，圈 Ｃｉ 中含有某条边 ｅｊ 时，记 Ｃｉ ｅｊ 值 为 １，否则为 ０，得到形式背景（Ｏ，Ｐ，Ｉ），对象集 Ｏ ＝ ｛Ｃ１ ，Ｃ２ ，…，Ｃｎ ｝，属性 Ｐ ＝ ｛ｂ１ ，ｂ２ ，…，ｂｎ ｝。 特别地， 当图 Ｇ ＝ （Ｖ，Ｅ）为 Ｋｎ 图时，图 Ｇ ＝ （Ｖ，Ｅ）对应的形式 背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ）如表 ２ 所示。 表 ２ Ｋｎ 图的形式背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） Ｔａｂｌｅ ２ Ｆｏｒｍａｌ ｃｏｎｔｅｘｔ Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） ｏｆ Ｋｎ ｄｉａｇｒａｍ Ｉ ｂ１ ｂ２ ｂ３ ｂｎ－１ … ｂｎ（ｎ－１） ２ Ｃ１ １ ０ １ ０ … ０ Ｃ２ ０ １ １ ０ … ０ Ｃ３ １ １ ０ １ … ０ ︙ ︙ ︙ ︙ ︙ ０ Ｃｎ（ｎ－１） ２ －（ｎ－１） ０ ０ … … … １ 定义 １０ 在 Ｋｎ 图的形式背景 Ｌ（Ｏｋｎ ，Ｐｋｎ ，Ｉｋｎ ） 对应的概念格 Ｌ（Ｏ，Ｐ，Ｉ）中给出“层”的定义： 设 Ｌ（Ｏ，Ｐ，Ｉ）最大元为 Ａ 即第一层，对任意 Ｘ∈ Ｌ（Ｏ，Ｐ，Ｉ） ｛Ａ｝，设 Ａ 到 Ｘ 的距离为 ｎ。 也就是，当 区间［Ｘ，Ａ］⊆Ｌ（Ｏ，Ｐ，Ｉ）最长链的长度为 ｒ，（ ｒ ＝ １， ２，３，…，ｎ），则设 Ｘ 为第 ｍ 层，ｍ ＝ ｒ＋１，记第 ｍ 层为 ｍ ＝ Ｌ （ｍ） 。 设概念格 Ｌ （Ｏ，Ｐ，Ｉ） 的 Ｈａｓｓｅ 示图记为 Ｈ（Ｌ）。 由表 ２ 发现，当 ｎ ＝ ４ 时，根据 Ｌ （Ｏｋｎ ，Ｐｋｎ ， Ｉｋｎ ）＝ ｛（Ｐ′，Ｐ）｝ 得对应的概念为（ Ｃ３Ｃ２Ｃ１ ，｛ ｝） ∈ Ｌ （１） ；（Ｃ１Ｃ３ ，ｂ１ ），（Ｃ３Ｃ２ ，ｂ２ ），（Ｃ１Ｃ２ ，ｂ３ ）∈Ｌ （２） ；（Ｃ３ ， ｂ６ ｂ１ ｂ２ ）， （ Ｃ１ ， ｂ４ ｂ１ ｂ３ ）， （ Ｃ２ ， ｂ５ ｂ２ ｂ３ ） ∈ Ｌ （３） ； （｛ ｝， ｂ６ ｂ５ ｂ４ ｂ３ ｂ２ ｂ１ ）∈Ｌ （４） 。 引理 ３ １）根据完全图的定义和表 １ 知，当定 义 ７ 含圈基个数为 ｎ－１ 时，与定义 ８ 基顶点相连接 的每个基 ｂ１ ，ｂ２ ，…，ｂｎ－１对应的对象个数为 ｎ－２ 个。 ２）根据定义 ９ 含两个基的基最小圈最多有一 条重边。 证明 首先证明第 １）条。 在表 ２ 中，ｂ１ 对应着 的对象为 ｎ－２ 个，因为 ｂ１≠ｂ２ ，所以对应的对象就为 ｎ－２ 个，即 ｂ１ ′≠ｂ２ ′。 其次，证明第 ２） 条。 若两个基 最小圈含有 ２ 个相同的边，根据定义 ９ 可知：假设 Ｃ１≠Ｃ２ ，ｂ１∈Ｃ１ ，ｂ２∈Ｃ２ ，若（ｂ１∪ｂ２ ）∈（Ｃ１∩Ｃ２ ），则 推出 Ｃ１ ＝Ｃ２ ，与条件中两个基最小圈含有 ２ 个相同 的边矛盾，即 Ｃ１≠Ｃ２ 矛盾。 所以含两个基的基最小 圈最多有一条重边。 定理 １ Ｋｎ图对应的形式背景概念格有且仅有 ４ 层。 证明 根据定义 ４、定义 ５、定义 ６ 及引理 ３ 中 的第 １）条的概念。 第 １ 层：Ｏ＝ ｛Ｃ１ ，Ｃ２ ，…，ＣＣ２ ｎ－１ ｝对 应的属性集 Ｐ ＝ ｛｝可以表示为（Ｃ１Ｃ２…ＣＣ２ ｎ－１ ，｛ ｝）∈ Ｌ （１） 。 第 ２ 层： 每 个 基 对 应 ｎ － ２ 个 圈， 设 为 Ｃ１ ， Ｃ２ ，…，Ｃｎ－２ 。 证任意基 ｂｉ ∈Ｂ ＝ ｛ ｂ１ ， ｂ２ ，…， ｂｎ－１ ｝， （ｉ ＝ １，２，…，ｎ－１），设（Ｃ１ Ｃ２…Ｃｎ－２ ，ｂｉ ），其中 ｂｉ ′ ＝ Ｃ１Ｃ２…Ｃｎ－２ ，根据引理 ３ 中第 １） 条，⌀∩ ｂｉ ＝ ⌀， ⌀ ＝ ０， ｛ｂｉ｝ ＝ １ 且⌀⊄｛ｂｉ｝且不存在任意集合 Ａ 满足⌀⊆Ａ⊆｛ ｂｉ｝。 所以它们之间不会产生其他 的概念。 第 ３ 层：设（ Ｃ１ Ｃ２…Ｃｎ－２ ， ｂ１ ） 与（ Ｃ１Ｃ２ … Ｃｎ－３ ，ｂ２ ） ∈Ｌ （３） ，所以设（ Ｃ１ …Ｃｎ－３ ， （ｂ１ ｂ２ ）″）＝ （ Ｃ１ Ｃ２…Ｃｎ－２ ，ｂ１ ）∧（Ｃ１Ｃ２…Ｃｎ－３ ，ｂ２ ），由引理 ３ 中第 ２） 条知 Ｃ１ ＝Ｃ２ ＝ … ＝ Ｃｎ－３ ，取代表圈 Ｃ１ ，由基最小圈定 义当且仅当存在 ｂ３∈Ｃ１ ，则（Ｃ１ ，ｂ１ ｂ２ ｂ３ ）是概念，由 任意性知（Ｃｉ，Ｃｉ ′）均为概念，其中 Ｃｉ ′为 Ｃｉ 包含的 ３ 条边。 第４ 层：（ Ｃ１ ，ｂ１ ｂ２ ｂ３ ） 与（ Ｃ２ ， ｂ１ ｂ３ ｂ４ ） ∈Ｌ （４） ， （⌀，ｂ１ ）。 因为存在集合 Ｂ ＝ ｛ｂ１ ，ｂ２ ，ｂ３ ，…，ｂｎ（ｎ－１） ２ ｝， 满足⌀⊆Ｂ⊆｛Ｃｉ ｝，即第 ４ 层表示为（⌀，｛ ｂ１ ，ｂ２ ， ｂ３ ，…，ｂｎ（ｎ－１） ２ ｝）。 定理 ２ Ｋｎ 图模型建立的概念格 Ｌ（Ｋｎ ）的第 ２ 层和第 ３ 层的 Ｈａｓｓｅ 示图组成一个二部图。 证明 根据定义 ２（二部图）的定义，二部图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）由顶点集 Ｖ１ 和 Ｖ２ 及边集 Ｅ⊆Ｖ１ ×Ｖ２ 组 成，Ｖ１ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｓ｝，Ｖ２ ＝ ｛ ｙ１ ，ｙ２ ，…， ｙｔ｝，则二部 图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）的伴随矩阵为二元矩阵 Ａ（ａｉｊ），这 里 ａｉｊ ＝ １，当且仅当（ｘｉ，ｙｊ）∈Ｅ。 设 Ｖ１ 为对象集，Ｖ２ 为属性集，则二部图的伴随矩阵就是形式背景。 二 部图 Ｇ ＝ （Ｖ１ ，Ｖ２ ，Ｅ）由两个非交顶点集 Ｖ１ ，Ｖ２ 组成， 且 Ｇ 的每条边的顶点分别在 Ｖ１ ，Ｖ２ 中。 设 Ｖ１ 是第 ２ ·３３６· 智 能 系 统 学 报 第 １２ 卷