电子学报 ›› 2013, Vol. 41 ›› Issue (7): 1384-1388.DOI: 10.3969/j.issn.0372-2112.2013.07.022

• 学术论文 • 上一篇    下一篇

弦二部图的概念格表示

李立峰1,2, 刘三阳1, 罗清君3   

  1. 1. 西安电子科技大学理学院数学系, 陕西西安 710126;
    2. 西安邮电大学理学院, 陕西西安 710121;
    3. 西安财经学院理学院, 陕西西安 710068
  • 收稿日期:2011-07-27 修回日期:2012-11-20 出版日期:2013-07-25
    • 作者简介:
    • 李立峰 男,1980年生于西安市长安区,西安电子科技大学博士生,西安邮电大学理学院讲师.主要从事概念格理论的研究.E-mail:hlw12-12@sohu.com
    • 基金资助:
    • 中央高校基本科研业务费专项资金 (No.K50511700008); 陕西省教育厅自然科学专项基金 (No.11JK1051,No.2013JK1098,No.2013JK1130,No.2013JK1182)

Representing Chordal Bipartite Graph Using Concept Lattice Theory

LI Li-feng1,2, LIU San-yang1, LUO Qing-jun3   

  1. 1. Department of Mathematics, School of Science, Xidian University, Xi'an, Shaanxi 710126, China;
    2. School of Science, Xi'an University of Posts and Telecommunications, Xi'an, Shaanxi 710121, China;
    3. School of Science, Xi’an University of Finance and Economics, Xi'an, Shaanxi 710068, China
  • Received:2011-07-27 Revised:2012-11-20 Online:2013-07-25 Published:2013-07-25
    • Supported by:
    • Fundamental Research Funds for the Central Universities (No.K50511700008); Natural Science Foundation of Education Department of Shaanxi Province (No.11JK1051, No.2013JK1098, No.2013JK1130, No.2013JK1182)

摘要: 本文首先讨论了二部图中双单纯边与概念格中概念之间的对应关系;其次研究了弦二部图和约简的形式背景的若干性质;最后将概念格中元素的消除理论应用于二部图的研究,给出了弦二部图的概念格刻画.结果表明,一个二部图是弦二部图当且仅当对应的概念格中有一个∨∧—不可约元的完美消除序列.

关键词: 知识推理, 约简形式背景, 概念格, 弦二部图, 边完美消除序列

Abstract: In this paper,the relation between bisimplicial edges in a bipartite graph and their corresponding concepts are discussed,and some properties of reduced contexts and chordal bipartite graphs are investigated.Then,we apply the element elimination for a concept lattice to bipartite graph theory,and obtain a representation of chordal bipartite graphs.More precisely,we show that a bipartite graph is chordal bipartite graph if and only if there is a join and meet irreducible element elimination ordering with respect to its corresponding concept lattice.

Key words: reduced context, concept lattice, chordal bipartite graph, perfect edge without vertex elimination ordering

中图分类号: