链图的概念格表示

Chain Graph and their Concept Lattice Representation

概念格是基于对象集和属性集之间的二元关系建立的一种层次结构。它与极大二部团存在着一定的联系。将概念格属性约简理论应用于链图,首先给出了链图的概念格表示,其次证明了二部图G=(V1,V2,E)是链图,当且仅当G′=(V1,V2,E)是链图,这里(V1,V2,E)是(V1,V2,E)的约简形式背景。

Concept lattices are an ordering of the maximal rectangles defined by a binary relation. There is a corresponding relationship between concept and maximal biclique. This paper applied the reduction theory of concept lattice to chain graph. Firstly, the representation of chain graph by concept lattice was given. Secondly, it was proved that a bipar-tite graph G= （V1 ,V2 ,E） is a chain graph if and only if G=（V1,V2,E）is such a graph,where （V1 ,V2 ,E） is a re-duced context of the context （V1, V2, E）.